True lists in python?

[Arnaud Delobelle]

Duncan Booth <duncan.booth at invalid.invalid> writes:

> I guess you might be able to do it with a double-linked list provided 
> that when traversing the list you always keep two nodes around to 
> determine the direction. e.g. instead of asking for node6.nextNode() you 
> ask for node6.nextNode(previous=node1) and then the code can return 
> whichever sibling wasn't given. That would make reversal (assuming you 
> have both nodes) O(1), but would make traversing the list slower.

There used to be a trick to implement doubly linked lists with the same
memory footprint as singly linked ones: instead of each node storing two
pointers (one to the next node, one to the previous one), you just store
one value:

    (previous node) xor (next node)

This means that when traversing the list, you need to always remember
which node you are coming from.  But it also makes these lists
kind of symmetrical.

-- 
Arnaud