Warm tip: This article is reproduced from serverfault.com, please click

Using pointers to remove item from singly-linked list

发布于 2012-10-16 12:38:33

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?

Questioner
codebox
Viewed
0
3,870 2014-04-03 17:42:44

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.