12

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.

Improve this question
  • 2
    What he's saying is that when you need to store the location of the prev, instead of storing the entire node, you can just store the location of prev.next, since that' the only thing you're interested in. A pointer to a pointer. And if you do that, you avoid the silly if, since now you don't have the awkward case of list_head being a pointer from outside a node. The pointer to the head of the list is then semantically the same as the pointer to the next node. – Ordous Feb 18 '15 at 19:58
  • 1
    @Ordous: I see, thanks. Why a comment? That is a concise, clear, and illuminating answer. – dotancohen Feb 18 '15 at 20:05
  • 1
    @Ordous Everything involved in that code snippet is a pointer, so his point can't have anything to do with storing the entire node vs storing a pointer to it. – Doval Feb 18 '15 at 20:05
12

Using my L331 MS Paint skills:

enter image description here

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.

Improve this answer
  • 1
    Ah I see now....you learn something new every day. – Lawrence Aiello Feb 18 '15 at 20:32
  • 2
    I think you describe things correctly, but I would suggest that the proper solution is to have list_head point to something with a next node that points to the first real data item (and have prev initialized to that same dummy object). I don't like the idea of having prev point to something of different type, since such tricks may introduce Undefined Behavior via aliasing, and make code needlessly sensitive to structure layout. – supercat Feb 18 '15 at 21:41
  • 1
    @supercat That's exactly the point. Instead of having prev pointing to Nodes, it points to pointers. It always points to something of the same type, namely a pointer to a Node. Your suggestion is essentially the same - have prev point to something "with a next node". If you discard the shell you just get the initial list_head pointer. Or in other words - something that is defined only by having a pointer to the next node, is semantically equivalent to a pointer to a node. – Ordous Feb 18 '15 at 22:49
  • 1
    @Ordous: That makes sense, though it presupposes that list_head and next will hold the same "kind" of pointer. Not an issue in C, perhaps, but perhaps problematic in C++. – supercat Feb 18 '15 at 22:56
  • 1
    @supercat I always assumed that's the "canonical" representation of a linked list, language-agnostic. But I'm not proficient enough to judge whether it makes a difference between C and C++ really, and what are the standard implementations there. – Ordous Feb 18 '15 at 23:16
12

enter image description here enter image description here enter image description here enter image description here enter image description here

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);
Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.