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.
prev
, instead of storing the entire node, you can just store the location ofprev.next
, since that' the only thing you're interested in. A pointer to a pointer. And if you do that, you avoid the sillyif
, since now you don't have the awkward case oflist_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