Hacker News Reader

Comment by userbinator | Hacker News Reader

There's a third alternative, which I've heard of as "virtual head", that removes the extra indirections in the loop and removal:

    while(p->next != entry)
     p = p->next;
    p->next = entry->next;

I've deliberately not shown the initialisation of p, because it's a bit tricky in C (but trivial in Asm); p is not initialised to the head, nor the address of the head, but to a "virtual" node centered around the head, such that p->next will initially access the head. If the next field is at the beginning of the structure, p does point to the head; else p points to a location before the head. It would be something like (char*)&head - offsetof(Node, next);

View on HN

For those curious how to create the "virtual head" in C:

    struct entry { int value; entry * next; };

    entry * head = NULL;
    void remove_entry(entry *target) {
        long offset = (long)&((entry*)0)->next;
        entry * curr = (entry*)((long)&head - offset);

        while (curr->next != target)
            curr = curr->next;

        curr->next = target->next;
    }

But I'm not sure how portable that is. It is portable if the next pointer is the first member of the struct though. From 6.7.2.1.13 in the C99 standard:

>A pointer to a structure object, suitably converted, points to its initial member

    struct entry { entry * next; int value; };
    ...
        // virtual entry where &(curr->next) = &head
        entry * curr = (entry*)&head;

Note that it's exactly the same logic as the grandparent since

    *curr = curr->next

    indirect = curr
    *indirect = *curr
    *indirect = curr->next
    indirect = &(curr->next)

But, I think that the virtual head entry is an easier mental model.

C99 standard: http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf

You can get the same effect by using a “dummy” node. The dummy node has a next pointer, but no data, and the dummy node always exists at the front of the list. The list structure contains the dummy, instead of using a pointer to the front of the list.

    struct Node
    {
        struct Node* next;
    };

    struct DataNode
    {
        struct Node* next;
        struct Value value;
    };

    struct List
    {
        struct Node dummy;
        // You can also add length, etc.
    };

    // entry must be in list
    void remove_list_entry(struct List* list, struct Node* entry)
    {
        Node *prev = &list->dummy;

        while (prev->next != entry) {
            prev = prev->next;
            assert(prev != NULL);
        }
    
        prev->next = entry->next;
        free(entry);
    }

Reply on news.ycombinator.com