2 ms·
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)
by userbinator 8y ago
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);
- DerekL 8y agoYou 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); }
- rovolo 8y agoFor 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 http://www.open-std.org/jtc1/sc22/WG14/www/docs/n1256.pdf