How can I understand linked lists?

Question

I'm trying to understand how they work, but I'm having a lot of difficulties. Does anyone care to explain them intuitively, or offer resources they think work well for those who are just beginning with the topic?

So let's say I have this:

struct node
{
   int nodeNum;
   nodes *next;
}

To create the "head" node I'd do the following: node *head = new node; so that my linked list now looks like . After assignment:

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 that if I were to do, 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? Traversing through the nodes isn't really intuitive as described head = head->next;, for example. How does this work?

Any advice you can offer to make this topic easier to understand would be great. Thanks for the help everyone!

Answer 1

Your insert function doesn't 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 to the new node, and insert the new node after the old one:

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 iterate, you maintain your own pointer to the element you're looking at; this begins at head, and then follows the next pointer 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 a pointer to the node before it in order 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