@viraptor said:
@Ancient_Hacker said:This is triply silly. If the Guru had read just a teensy bit of linked list literature, surely he would have seen Nick Wirths way to link both ways with just one pointer.
It's only been around since, like 1972
??? Link please....
I don't know which variant was Wirth's, but the standard trick is the delta-linked list:
struct node {
void *obj;
int delta;
};
If you have struct node* a, b, c, d, and the list order is a, b, c, d, then:
a->delta = NULL
b->delta = c - a
c->delta = d - b
d->delta = NULL
To walk the list, you need pointers to the first two elements, the next element is x + y->delta, and the previous element is y - x->delta.
The neat trick about this structure is that the whole thing is relocatable - you can copy it to any point in memory, and the pointers are still valid, since they only store the distance between nodes.
Other variants include addition and xor, but those aren't relocatable.