3 ms·
The advantage is that, supposing the a pointer to the head of the list is stored in some other container, like struct Container { struct Foo *first
by comex 5y ago
The advantage is that, supposing the a pointer to the head of the list is stored in some other container, like
struct Container {
struct Foo *first_foo;
...probably more stuff...
};
then the first entry can have its `prev` field simply be `&container->first_foo`. (Each subsequent entry, as the OP said, has its `prev` field be `&previous_entry->next`.)
That way, you can have a function that removes an entry from the list, given only a pointer to the entry:
void foo_remove(struct Foo *foo) {
*foo->prev = foo->next;
if (foo->next != NULL)
foo->next->prev = foo->prev;
}
No need to keep separate track of which container you belong to, and no need to special case the first entry of the list.
The FreeBSD sys/queue.h macros use this pattern for the LIST type.
(The disadvantage of this scheme is that despite it being a mostly doubly linked list, you can only iterate forwards.)
- phkahler 5y agoYou get it exactly. I gave a more detailed explanation of the specific use-case in response to a sibling comment. It's one piece of a very complex data structure that does exactly what was needed efficiently - a dynamically updatable spatial index for geometric primitives.
- Akronymus 5y agoRelated https://www.youtube.com/watch?v=0ZEX_l0DFK0 https://www.youtube.com/watch?v=0ZEX_l0DFK0