How can I understand linked lists?

Question

I'm trying to understand how they work, but I have a lot of difficulties. Does anyone want to explain them intuitively or offer resources that, in their opinion, work well for those who are just starting a topic?

So let's say I have this:

struct node { int nodeNum; nodes *next; } 

To create a "head" node, I would do the following: node *head = new node; so that the linked list now looks like . After the appointment:

 head->nodeNum = 10; head->next = NULL; 

we have . Now, if I wanted to write a function that inserts a node, can I write:

 void insert(node *previousNode, int num) { previousNode = new node; previousNode->nodeNum = num; previousNode->next = NULL; } 

So, if I did, say, insert(head, 20); my new list looks like ?

If everything is correct, how can I use this information to search and / or remove nodes from the list? For example, moving through nodes is not intuitive, as described, for example, head = head->next; . How it works?

Any advice you can offer to facilitate understanding of this topic would be great. Thanks for helping everyone!

Answer 1

The insert function does not work properly; it just creates a new node without adding it to the list, and loses it (giving a memory leak) when the function returns:

 head -> 10 -> NULL becomes head -> 10 -> NULL (lost) 20 -> NULL 

Instead, it should link the old tail of the list with the new node and insert the new node after the old:

 void insert(node * prev, int num) { node * new_node = new node; new_node->nodeNum = num; new_node->next = prev->next; // add the old tail after the new node prev->next = new_node; // add the new node after the old node } insert(head, 20); // insert 20 after the head // head -> 10 -> NULL becomes head -> 20 -> 10 -> NULL 

How can I use this information to search and / or remove nodes from the list?

To continue, you save your own pointer to the element you are looking at; this starts with head , and then the next pointer follows until it reaches the end (i.e. next is null):

 for (node * n = head; n; n = n->next) { if (n->nodeNum == 20) { std::cout << "Found node 20!\n"; break; } } 

To remove a node from a singly linked list, you need to point to a node pointer to update its next pointer:

 void remove_next(node * prev) { if (prev->next) { node * next = prev->next->next; // Get the tail after the removed node delete prev->next; prev->next = next; // Add the tail after the remaining node } } remove_next(head); // head -> 20 -> 10 -> NULL becomes head -> 10 -> NULL 

Answer 2

Your problem is here:

 void insert(node *previousNode, int num) { previousNode = new node; previousNode->nodeNum = num; previousNode->next = NULL; } insert(head, 20); 

Here is what this bit of code does: previousNode = new node; makes a pointer to node and assigns this pointer to the previousNode. PreviousNode started as a copy, now it points to something new. Now you are assigning values ​​to the new node. In other words, this implementation of the insert is not inserted.

What you want to do is something more:

 void better_insert(node *previousNode, int num) { node *post_node = new node; #create a brand new pointer to a brand new node post_node->nodeNum = num; #give it a number post_node->next = previousNode->next; #we want previousNode to be behind new node previousNode->next = post_node; } 

What it is: after creating a new node and pointing to it with a new pointer, we give it a number. The next thing is to figure out where the pointers point ...

let it pretend that we are waving some nodes in a linked list. All lowercase letters are pointers, ok?

 a->next = b 

now let's say that we want node x to come after a and have the number 10 ... we call `better_insert (a, 10)

post_node points to a new node (our node x) and is assigned 10. cool ...

we want:

 a->next = x x->next = b 

we have:

 a->next = b x->next = null 

the last two lines of the function just shuffle the material until it fits the bill

So in more detail ...

we have:

 a->next = b x->next = null 

therefore we call:

 post_node->next = previousNode->next; #we want previousNode to be behind new node 

now we have: a-> next = b x-> next = b

now we call:

 previousNode->next = post_node; 

and in the end we get:

 a->next = x x->next = b 

or in other words:

 a->next = x a->next->next = b 

Answer 3

You need to use more variables in the code. The insert operation modifies two nodes. The previous node needs to be changed to point to the new node, and a new node must be created and made to point to the node after the previous node (which may or may not be NULL).

 void insert(node *previousNode, int num) { node *newnode = new node; newnode->nodeNum = num; newnode->next = previousNode->next; previousNode->next = newnode; } 

To go through the list, you track the “current node”, which you can change from one node to the following:

 while (currentNode != 0) { do_something_with(currentNode); currentNode = currentNode->next; } 

Of course, if do_something_with removes the node, then you cannot go further from it. In addition, to remove a node from a singly linked list, you need to point to a node pointer. Therefore, in this case, your cycle will most likely track two nodes: the current and the previous, and not just one.

Answer 4

The terminology you use is confusing. I hope this analogy no longer bothers you. Essentially, imagine a linked list, like this terrifying set of doorways, where when you enter one doorway, it closes behind you, and you can only see what is in this room or go to the next room. From the outside of this corridor you only know where the entrance is, and not what is inside.

So, due to the structure of the linked list, you know that this is an input, some kind of pointer ll_node *head; . Inside the head there is some data and a pointer to the next node in your linked list. Moving this linked list is as simple as starting at the entrance to the corridor, head and entering one corridor at a time until you find the node you are looking for.

 ll_node *current_location = head; while (current_location != NULL) { // if we are at the node that you were hoping to reach, exit. if (current_location->nodeNum == target_data_im_looking_for) { break; } // this isn't the node you're looking for, go to the next one. current_location = current_location->next; } 

Similarly, insertion of a node should go to the end of the linked list (until current_location->next == NULL ) and replace the last element of the next pointer with the memory location of the newly created ll_node . I will not realize this for you, so you have a chance to learn, but here is enough to get to where you want to be.

Answer 5

Usually a linked list node does not contain its number. It usually consists of data and a pointer to the next node. You should also get the code without typos.

 typedef Data int; struct node { Data data; // some Data node *next; // pointer to the next node } 

In general, you also do not want a new node after the specified, but rather a list. The signature void insert(node *previousNode, int num) offers you a new node after some previous specified.

Technically, you can add a new node to the list in three ways. To the top or bottom of the list or somewhere in between. Adding to the beginning is the fastest and easiest.

 void insert(Data num) { node* tmp = new node; //make a new node tmp->data = num; //fill in data tmp->next = head; //set the next element of new one to be the current head head = tmp; //set new element as the head } 

This way you put a new item in front of the list. You always move the one-way linked list from head to end.

 void print_all() { node* current = head; // start at head while(current != NULL){ // while element exists cout << current->data << ' '; //print its data current = current->next; //move to the next one } } 

It is very easy to understand when you have images with cells for data and arrows for node* next .

This is for a start. You need to change the insert function to handle a special case when the list is initially empty. That is, head == NULL .

I also highly recommend that you try to implement it in an object oriented way. Write a class List that uses a struct node .

 class List { private: node* head; public: List(); void insert(data); void print_all(); } 

Try to implement these features. In my experience, this helps organize your thinking about data structures and the container when you do something like that, and it is more like C ++ - a way to do something like this.

Answer 6

In the above list, you have very little information, such as nodeNum. you must keep more ionic images in it. For example, on a Node with a value of nodeNum = 10, there must be some other information that you want to get from this Node. So when the user calls

 node* search(node *head,int num){ node *temp = head;//copy node reference into temp variable while (temp != NULL){ if (temp->nodeNum == num){ return temp; } temp = temp->next; } } 

you can get data in Node with node

  res = search(head,10); 

For removing

 bool delete(node *head,int num){ node *temp = head;//copy node reference into template node *prev = NULL; bool isDelete = false; while (temp != NULL){ if (temp->nodeNum == num){ break; }else prev = temp; temp = temp->next; } } if (temp != NULL){ prev-> next = temp->next;//maintain list delete temp; isDelete = true; } return isDelete; }