Re: Double linked list with one pointer

Gaetano Mendola <mendola(at)bigfoot(dot)com> writes:
> If I'm not wrong Neil Conway is working on
> reimplement a double linked list.

No, he's working on keeping track of the list tail element (and length,
but the tail element is the important part). There was nothing about
double linking.

> In particular, a motivation behind two-way pointers is that you
> can have a more space-efficient doubly linked list if you store only one
> (not two) pointer's worth of storage in each node. But how can the list
> still be traversable in both directions? The idea is that each node
> stores, not a pointer to one other node, but a pointer to the previous
> node XOR'd with a pointer to the next node.

This is way too weird for my taste. We do not need two-way list
traversal in 99.9% of the backend code (note the near complete lack of
use of Dllist). Also, the described scheme is slower to traverse than a
standard list since you have to remember two words of state (prev and
cur pointer not just cur) to traverse the list; that bookkeeping, plus
the cost of the XOR itself, adds up. Another cost that would be
significant from my point of view is loss of readability of list
structures in the debugger. I don't want to pay that cost to buy a
feature we don't need.

regards, tom lane