Using pointers to remove item from singly-linked list

In a recent Slashdot Interview Linus Torvalds gave an example of how some people use pointers in a way that indicates they don't really understand how to use them correctly.

Unfortunately, since I'm one of the people he's talking about, I also failed to understand his example:

> I've seen too many people who delete a singly-linked list entry by keeping track of the "prev" entry, and then to delete the entry, doing > something like > > if (prev) > prev->next = entry->next; > else > list_head = entry->next; > > > and whenever I see code like that, I just go "This person doesn't > understand pointers". And it's sadly quite common. People who > understand pointers just use a "pointer to the entry pointer", and > initialize that with the address of the list_head. And then as they > traverse the list, they can remove the entry without using any > conditionals, by just doing > > *pp = entry->next

Can someone provide a bit more explanation about why this approach is better, and how it can work without a conditional statement?

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.

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:

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."

In the first approach, you delete a node by unlink it from the list.

In the second approach, you replace the to-be-deleted node with the next node.

Apparently, the second approach simplifies the code in an elegant way. Definitely, the second approach requires better understanding of the linked list and the underlying computation model.

Note: Here is a very relevant but slightly different coding question. Good for testing one's understanding: https://leetcode.com/problems/delete-node-in-a-linked-list/

I prefer the Dummy node approach, an example layout:

|Dummy|->|node1|->|node2|->|node3|->|node4|->|node5|->NULL
                     ^        ^
                     |        |
                    curr   curr->next // << toDel

and then, you traverse to the node to delete (toDel = curr>next)

tmp = curr->next;
curr->next = curr->next->next;
free(tmp);

That way, you don't need to check if it's the first element, because the first element is always Dummy and never gets deleted.

Here's a complete code example, using a function-call to remove matching elements:

• rem() removes matching elements, using prev

• rem2() removes matching elements, using pointer-to-pointer

// code.c

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


typedef struct list_entry {
    int val;
    struct list_entry *next;
} list_entry;


list_entry *new_node(list_entry *curr, int val)
{
    list_entry *new_n = malloc(sizeof(list_entry));
    if (new_n == NULL) {
        fputs("Error in malloc\n", stderr);
        exit(1);
    }
    new_n->val  = val;
    new_n->next = NULL;

    if (curr) {
        curr->next = new_n;
    }
    return new_n;
}


#define ARR_LEN(arr) (sizeof(arr)/sizeof((arr)[0]))

#define     CREATE_LIST(arr) create_list((arr), ARR_LEN(arr))

list_entry *create_list(const int arr[], size_t len)
{
    if (len == 0) {
        return NULL;
    }

    list_entry *node = NULL;
    list_entry *head = node = new_node(node, arr[0]);
    for (size_t i = 1; i < len; ++i) {
        node = new_node(node, arr[i]);
    }
    return head;
}


void rem(list_entry **head_p, int match_val)
// remove and free all entries with match_val
{
    list_entry *prev = NULL;
    for (list_entry *entry = *head_p; entry; ) {
        if (entry->val == match_val) {
            list_entry *del_entry = entry;
            entry = entry->next;
            if (prev) {
                prev->next = entry;
            } else {
                *head_p    = entry;
            }
            free(del_entry);
        } else {
            prev = entry;
            entry = entry->next;
        }
    }
}


void rem2(list_entry **pp, int match_val)
// remove and free all entries with match_val
{
    list_entry *entry;
    while ((entry = *pp)) { // assignment, not equality
        if (entry->val == match_val) {
            *pp =   entry->next;
            free(entry);
        } else {
            pp  =  &entry->next;
        }
    }
}


void print_and_free_list(list_entry *entry)
{
    list_entry *node;
    // iterate through, printing entries, and then freeing them
    for (;     entry != NULL;      node = entry, /* lag behind to free */
                                   entry = entry->next,
                                   free(node))           {
        printf("%d ", entry->val);
    }
    putchar('\n');
}


#define CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val) createList_removeMatchElems_print((arr), ARR_LEN(arr), (match_val))

void    createList_removeMatchElems_print(const int arr[], size_t len, int match_val)
{
    list_entry *head = create_list(arr, len);
    rem2(&head, match_val);
    print_and_free_list(head);
}


int main()
{
    const int match_val = 2; // the value to remove
    {
        const int arr[] = {0, 1, 2, 3};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {0, 2, 2, 3};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {2, 7, 8, 2};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {2, 2, 3, 3};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {0, 0, 2, 2};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {2, 2, 2, 2};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }
    {
        const int arr[] = {};
        CREATELIST_REMOVEMATCHELEMS_PRINT(arr, match_val);
    }

    return 0;
}

See the code in action here:

• gcc https://wandbox.org/permlink/LxgMddqCZWyj7lMI
• clang https://wandbox.org/permlink/5aEkxh24sGfAecwF

If compiling and using valgrind (a memory-leak checker) like this:
gcc -std=c11 -Wall -Wextra -Werror -o go code.c && valgrind ./go
we see that all is good.

@glglgl:

I wrote following simple example. Hope you can have a look why it works.
In function void delete_node(LinkedList *list, void *data), I use *pp = (*pp)->next; and it works. To be honest, I don't understand why it works. I even draw the diagram of pointers but still not understand it. Hope you can clarify it.

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

typedef struct _employee {
    char name[32];
    unsigned char age;
} Employee;

int compare_employee(Employee *e1, Employee *e2)
{
    return strcmp(e1->name, e2->name);
}
typedef int (*COMPARE)(void *, void *);

void display_employee(Employee *e)
{
    printf("%s\t%d\n", e->name, e->age);
}
typedef void (*DISPLAY)(void *);

typedef struct _node {
    void *data;
    struct _node *next;
} NODE;

typedef struct _linkedlist {
    NODE *head;
    NODE *tail;
    NODE *current;
} LinkedList;

void init_list(LinkedList *list)
{
    list->head = NULL;
    list->tail = NULL;
    list->current = NULL;
}

void add_head(LinkedList *list, void *data)
{
    NODE *node = malloc(sizeof(NODE));
    node->data = data;
    if (list->head == NULL) {
        list->tail = node;
        node->next = NULL;
    } else {
        node->next = list->head;
    }
    list->head = node;
}

void add_tail(LinkedList *list, void *data)
{
    NODE *node = malloc(sizeof(NODE));
    node->data = data;
    node->next = NULL;
    if (list->head == NULL) {
        list->head = node;
    } else {
        list->tail->next = node;
    }
    list->tail = node;
}

NODE *get_node(LinkedList *list, COMPARE compare, void *data)
{
    NODE *n = list->head;
    while (n != NULL) {
        if (compare(n->data, data) == 0) {
            return n;
        }
        n = n->next;
    }
    return NULL;
}

void display_list(LinkedList *list, DISPLAY display)
{
    printf("Linked List\n");
    NODE *current = list->head;
    while (current != NULL) {
        display(current->data);
        current = current->next;
    }
}

void delete_node(LinkedList *list, void *data)
{
	/* Linus says who use this block of code doesn't understand pointer.	
	NODE *prev = NULL;
	NODE *walk = list->head;

	while (((Employee *)walk->data)->age != ((Employee *)data)->age) {
		prev = walk;
		walk = walk->next;
	}

	if (!prev)
		list->head = walk->next;
	else
		prev->next = walk->next; */

	NODE **pp = &list->head;

	while (((Employee *)(*pp)->data)->age != ((Employee *)data)->age) {
		pp = &(*pp)->next;
	}

	*pp = (*pp)->next;
}

int main () 
{
    LinkedList list;

    init_list(&list);

    Employee *samuel = malloc(sizeof(Employee));
    strcpy(samuel->name, "Samuel");
    samuel->age = 23;

    Employee *sally = malloc(sizeof(Employee));
    strcpy(sally->name, "Sally");
    sally->age = 19;

    Employee *susan = malloc(sizeof(Employee));
    strcpy(susan->name, "Susan");
    susan->age = 14;

    Employee *jessie = malloc(sizeof(Employee));
    strcpy(jessie->name, "Jessie");
    jessie->age = 18;

    add_head(&list, samuel);
    add_head(&list, sally);
    add_head(&list, susan);

    add_tail(&list, jessie);

    display_list(&list, (DISPLAY) display_employee);

    NODE *n = get_node(&list, (COMPARE) compare_employee, sally);
    printf("name is %s, age is %d.\n",
            ((Employee *)n->data)->name, ((Employee *)n->data)->age);
    printf("\n");
    
    delete_node(&list, samuel);
    display_list(&list, (DISPLAY) display_employee);

    return 0;
}

output:

Linked List
Susan   14
Sally   19
Samuel  23
Jessie  18
name is Sally, age is 19.

Linked List
Susan   14
Sally   19
Jessie  18

Here's my take, I found it easier to understand this way.

Example of deleting a node in a linked list, using pointers to pointers.

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

    void delete_from_list(struct node **list, int n)
    {
        struct node *entry = *list;

        while (entry && entry->value != n) {
            // store the address of current->next value (1)
            list = &entry->next;
            // list now stores the address of previous->next value
            entry = entry->next;
        }
        if (entry) {
            // here we change the previous->next value
            *list = entry->next;
            free(entry);
        }
    }

Assuming we create a list with these values:

*node 	value 	next
----------------------------------------
a 	    1 	    null
b 	    2 	    a
c 	    3 	    b
d 	    4 	    c
e 	    5 	    d

If we want to delete the node with value 3:

entry = e

while (entry && entry->value != 3) iterations:

    e->value != 3
        list = &e->next
        entry = d

    d->value != 3
        list = &d->next
        entry = c

    c->value == 3
        STOP

if (entry)
        d->next = b         (what was 'list' is dereferenced)
        free(entry)

After if (entry) we have:

    d->next = b

So the list becomes:

*node 	value 	next
----------------------------------------
a 	    1 	    null
b 	    2 	    a
c 	    3 	    b
d 	    4 	    b
e 	    5 	    d

And finally:

    free(entry)

And the list becomes:

*node 	value 	next
----------------------------------------
a 	    1 	    null
b 	    2 	    a
d 	    4 	    b
e 	    5 	    d

If we want to delete the first node, it will still work, because initially

*list == entry

therefore with:

*list = entry->next;

*list will point to the second element.

---

(1) Note that saying:

list = &entry->next;

Is the same as saying:

list = &(entry->next);