Blog

I want you to understand that sometimes you can see a problem in a different way and rewrite it so that a special case goes away and becomes the normal case, and that’s good code.

— Linus Torvalds

Here’s the textbook way to remove an item from a singly linked list:

void remove_cs101(list *l, list_item *target) {
        list_item *cur = l->head,
                  *prev = NULL;

        while (cur != target) {
                prev = cur;
                cur = cur->next;
        }

        if (prev)
                prev->next = cur->next;
        else
                l->head = cur->next;
}

And here’s the one Linus calls good taste:

void remove_elegant(list *l, list_item *target) {
        list_item **p = &l->head;

        while (*p != target)
                p = &(*p)->next;

        *p = target->next;
}

The first version walks the list and then asks “was it the head?”. The second one asks a different question: which pointer has to change? Once you think about the result instead of the walk, the head stops being special.