A fun party trick not mentioned here is reducing storage in a doubly linked-ish list: Normally each node stores 2 pointers: struct Node {void * prev;void * next}
The trick is to use only 1 'pointer', storing prev XOR next: struct Node {void* xored;}
While traversing, you remember not only the current position, but also where you came from. So forward traversal goes: next= current.xored XOR previous. Backwards also works: Node
* previous=(Node * )current.xored XOR (Node * ) next.
The first and last node can use 0 as previous or next node, or you make a circular list. You do have to store a pointer to the first and last node, as usual.
I've never seen this used in the real world, which is probably a good thing. It also plays hell with garbage collectors like Boehm, as they can't derive the 2 used adresses.
UPDATE: And of course wikipedia knows everything: https://en.wikipedia.org/wiki/XOR_linked_list
The trick is to use only 1 'pointer', storing prev XOR next: struct Node {void* xored;}
While traversing, you remember not only the current position, but also where you came from. So forward traversal goes: next= current.xored XOR previous. Backwards also works: Node * previous=(Node * )current.xored XOR (Node * ) next.
The first and last node can use 0 as previous or next node, or you make a circular list. You do have to store a pointer to the first and last node, as usual.
I've never seen this used in the real world, which is probably a good thing. It also plays hell with garbage collectors like Boehm, as they can't derive the 2 used adresses.
UPDATE: And of course wikipedia knows everything: https://en.wikipedia.org/wiki/XOR_linked_list