Using pointers to remove item from singly-linked list

Solution 1:

At the beginning, you do

pp = &list_head;

and, as you traverse the list, you advance this "cursor" with

pp = &(*pp)->next;

This way, you always keep track of the point where "you come from" and can modify the pointer living there.

So when you find the entry to be deleted, you can just do

*pp = entry->next

This way, you take care of all 3 cases Afaq mentions in another answer, effectively eliminating the NULL check on prev.

Solution 2:

If you like learning from examples, I prepared one. Let's say that we have the following single-linked list:

that is represented as follows (click to enlarge):

We want to delete the node with the value = 8.

Code

Here is the simple code that do this:

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

struct node_t {
    int value;
    node_t *next;
};

node_t* create_list() {
    int test_values[] = { 28, 1, 8, 70, 56 };
    node_t *new_node, *head = NULL;
    int i;

    for (i = 0; i < 5; i++) {
        new_node = malloc(sizeof(struct node_t));
        assert(new_node);
        new_node->value = test_values[i];
        new_node->next = head;
        head = new_node;
    }

    return head;
}

void print_list(const node_t *head) {
    for (; head; head = head->next)
        printf("%d ", head->value);
    printf("\n");
}

void destroy_list(node_t **head) {
    node_t *next;

    while (*head) {
        next = (*head)->next;
        free(*head);
        *head = next;
    }
}

void remove_from_list(int val, node_t **head) {
    node_t *del, **p = head;

    while (*p && (**p).value != val)
        p = &(*p)->next;  // alternatively: p = &(**p).next

    if (p) {  // non-empty list and value was found
        del = *p;
        *p = del->next;
        del->next = NULL;  // not necessary in this case
        free(del);
    }
}

int main(int argc, char **argv) {
    node_t *head;

    head = create_list();
    print_list(head);

    remove_from_list(8, &head);
    print_list(head);

    destroy_list(&head);
    assert (head == NULL);

    return EXIT_SUCCESS;
}

If you compile and run this code you'll get:

56 70 8 1 28 
56 70 1 28

Explanation of the code

Let's create **p 'double' pointer to *head pointer:

Now let's analyze how void remove_from_list(int val, node_t **head) works. It iterates over the list pointed by head as long as *p && (**p).value != val.

In this example given list contains value that we want to delete (which is 8). After second iteration of the while (*p && (**p).value != val) loop (**p).value becomes 8, so we stop iterating.

Note that *p points to the variable node_t *next within node_t that is before the node_t that we want to delete (which is **p). This is crucial because it allows us to change the *next pointer of the node_t that is in front of the node_t that we want to delete, effectively removing it from the list.

Now let's assign the address of the element that we want to remove (del->value == 8) to the *del pointer.

We need to fix the *p pointer so that **p was pointing to the one element after *del element that we are going to delete:

In the code above we call free(del), thus it's not necessary to set del->next to NULL, but if we would like to return the pointer to the element 'detached' from the list instead of the completely removing it, we would set del->next = NULL:

Solution 3:

Reconnecting the list once a node is to be removed is more interesting. Let's consider at least 3 cases:

1.Removing a node from the beginning.

2.Removing a node from the middle.

3.Removing a node from the end.

Removing from the beginning

When removing the node at the beginning of the list, there is no relinking of nodes to be performed, since the first node has no preceding node. For example, removing node with a:

link
 |
 v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------

However, we must fix the pointer to the beginning of the list:

link
 |
 +-------------+
               |
               v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------

Removing from the middle

Removing a node from the middle requires that the preceding node skips over the node being removed. For example, removing the node with b:

link
 |
 v
---------     ---------     ---------
| a | --+--+  | b | --+---> | c | 0 |
---------  |  ---------     ---------
           |                ^
           +----------------+

This means that we need some way to refer to the node before the one we want to remove.

Removing from the end

Removing a node from the end requires that the preceding node becomes the new end of the list (i.e., points to nothing after it). For example, removing the node with c:

link
 |
 v
---------     ---------     ---------
| a | --+---> | b | 0 |     | c | 0 |
---------     ---------     ---------

Note that the last two cases (middle and end) can be combined by saying that "the node preceding the one to be removed must point where the one to be removed does."