The right way to remove an item from a linked list

Question

In this Slashdot interview Linus Torvalds is quoted as saying:

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 a "*pp = entry->next".

As a PHP developer I have not touched pointers since Introduction to C in university a decade ago. However, I feel that this is a type of situation that I should at least be familiar with. What is Linus talking about? To be honest, if I were asked to implement a linked list and to remove an item, the above 'wrong' way is the way that I would go about it. What do I need to know to code as Linus says best?

I am asking here rather than on Stack Overflow as I'm not actually having an issue with this in production code.

Answer 1

Using my L331 MS Paint skills:

The original solution is to point to Nodes via curr. In that case you check if the next node after curr has the delete value, and if so reset the curr node next pointer. The problem is that there is no node that points to the head of the list. That means there has to be a special case to check it.

What Linus (likely) proposes instead is not to save the pointer to the current examined node, but rather the pointer to the pointer to the current node (labelled pp). The operation is the same - if the pp pointer points to a node with the right value, you reset the pp pointer.

The difference comes in the very beginning of the list. While there is no Node that points to the head of the list, there is, in fact, a pointer to the head of the list. And it is just the same a pointer to a node, just as another nodes next pointer. Hence there is no need for a special clause for the beginning of the list.

Answer 2

Code Example

// ------------------------------------------------------------------
// Start by pointing to the head pointer.
// ------------------------------------------------------------------
//    (next_ptr)
//         |
//         v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[....]
Node** next_ptr = &list->head;

// ------------------------------------------------------------------
// Search the list for the matching entry.
// After searching:
// ------------------------------------------------------------------
//                                  (next_ptr)
//                                       |
//                                       v
// [head]----->[..]----->[..]----->[..]----->[to_remove]----->[next]
while (*next_ptr != to_remove) // or (*next_ptr)->val != to_remove->val
{
    Node* next_node = *next_ptr
    next_ptr = &next_node->next;
}

// ------------------------------------------------------------------
// Dereference the next pointer and set it to the next node's next
// pointer.
// ------------------------------------------------------------------
//                                           (next_ptr)
//                                                |
//                                                v
// [head]----->[..]----->[..]----->[..]---------------------->[next]
*next_ptr = to_remove->next;

If we need some logic to destroy the node, then we can just add a line of code at the end:

// Deallocate the node which is now stranded from the list.
free(to_remove);