Here's an incredibly ancient hack, which still isn't known well enough. A linked list is a venerable data structure; every node on the list contains a next pointer, allowing us to advance one position in the list in O(1) time. On a doubly linked list, we also keep a prev pointer, to we can go back. But we're using twice as much space for our pointers! A doubly-linked list of 1-byte chars, when every pointer is another 4-byte word, will require at least 9 bytes for every 1 byte usefully stored (and often 12 bytes, assuming today's usual memory alignment restrictions).
Can we have a doubly-linked list with just the (singly-) linked list overhead? Surely not!
It turns out that we can. On each node, keep the XOR of the next and prev pointers in the single link field. When traversing the list, keep an iterator <cur,prev>, consisting of a pointer to the current element and a pointer to the previous element. Then (abusing C notation) next = cur->link ^ prev, so we know how to advance our iterator. All of these operations are also easy:
- Reversing the direction of the iterator:
- Just do
prev = cur->link ^ prev.
- Checking for end-of-list:
- Assuming we use the special address 0 to mark the ends, we just check that
next->link == prev (similar expressions exist for any other sentinel value you may pick for the ends, of course).
- Passing iteration starting points to a function:
- Just pass an appropriately-initialised iterator pointing to the starting point and its predecessor.
And an unexpected bonus is that now all functions work equally well on the list and the reversed list!
Unfortunately, there is no portable way of implementing such a list in C or C++: neither language allows you to XOR two pointers (what could the type of the result be?), and while you could cast a pointer to a large-enough integer type, you are not guaranteed even to have such a large-enough int, and you are not guaranteed that these XORs will work. However, it appears that the C++ STL list<> templated type could be implemented in such a way, assuming sufficient cooperation between the writers of the compiler and the library. I'm not aware of any implementation which actually does this, though.
Agthorr below is not quite right. Of course if all I have is a pointer into the list, I cannot traverse it. But the thing to realise is that the correct object to store is an iterator -- a pointer to two adjacent nodes of the list (depending on the application you might also need to know the iterator's direction, ``forwards'' or ``backwards''). For this data structure, typically you'd have many nodes in the list, and only a few such iterators from outside it, so the savings remain.
| 
