Linked lists and doubly linked lists are the first data structure anybody learns about formally. They let you insert and delete arbitrarily long subsections of a list just by fiddling with a few links at the very ends, so you can perform large splicing operations in constant time.
This algorithm describes an unusual form of doubly linked list which is reversible. What that means is that, if you're given a list, you can turn it backwards in constant time, just by fiddling with links at the ends, just like the other linked list operations.
A node in a reversible list looks very like a node in a doubly linked list. You have two pointers to other nodes, and also some unspecified payload data stored in the node.
The difference is that it's not fixed which of the two pointers points which way. You could follow pointer number one to get to another node, and then find that in the new node, pointer number one pointed back the way you'd come. So if you loop along the list following a fixed one of the two pointers, you will end up going in smaller circles than you want!
To move along a reversible list, you have to keep track of where you've just come from. After you follow a link, you examine both pointers in the node you arrive in, to find out which of them points back to the node you just left. Then you follow the other one.
This means that, in order to pass a whole reversible list around your program, it isn't sufficient just to supply a pointer to the first node in the list - because the recipient will need to know which of the two links to follow from that node. To solve this, you can either specify a link selection flag alongside the pointer, or arrange that the link to follow in the first node is always the first of the two. (The structure of a reversible list implies that you can swap the two pointers in a node without affecting the topology of the list!) Which you do is up to you; the latter saves space but might have thread-safety problems...
(Knuth suggests a space-saving optimisation for doubly linked lists which also naturally causes the list to be reversible: instead of storing both pointers separately, store their bitwise XOR. That way you can always deduce either pointer given the other one, but they only take up one word of space.)
In order to reverse a list, then, you must start with a pointer to the head of the list and end up with a pointer to the tail. To do this in constant time, the list must be circularly linked.
If you never need to reverse a whole list given only the head, but only ever need to reverse subsections of the list given pointers to both ends, you don't need to link the list circularly. Instead, you can simply have one of the two pointers in each end node be null. This also makes it possible to pass a whole list around using only a pointer to the head: it's obvious which of the links to follow from the head, because you choose the one that isn't null. And once you've followed the list all the way to the tail, you can pass a pointer to the tail node and you have the list in reverse order!
This is all a bit disjointed; I haven't described a coherent set of algorithms, but instead a wide range of ideas and approaches. Somewhere within this should be a form of reversible list suitable for anybody.
As a worked example, however, here's a piece of pseudo-code which follows a reversible list until it finds a node A and a node B, and then reverses the section of list in between them in constant time.
function reverse-a-to-b(head, linkref):
node = head
while not (is-node-A(node)):
newnode = node.links[linkref]
if newnode.links[0] == node:
linkref = 1 # link 0 points the way we came, so use link 1
else:
linkref = 0 # link 1 points the way we came, so use link 0
end if
end while
nodeA = node
linkrefA = linkref
# Now "nodeA" points to node A, and "linkrefA" describes which link
# goes "forwards" from there.
while not (is-node-B(node)):
newnode = node.links[linkref]
if newnode.links[0] == node:
linkref = 1 # link 0 points the way we came, so use link 1
else:
linkref = 0 # link 1 points the way we came, so use link 0
end if
end while
nodeB = node
linkrefB = linkref
# Now "nodeB" points to node B, and "linkrefB" describes which
# link goes "forwards" from there. So (1-linkrefB) gives the link
# that goes backwards, i.e. towards the section of list we want
# to reverse.
temp = nodeA.links[linkrefA]
nodeA.links[linkrefA] = nodeB.links[1-linkrefB]
nodeB.links[1-linkrefB] = temp
# That's swapped the links _into_ the section. Now we need to
# swap the links back out.
node = nodeA.links[linkrefA] # the node at the A end, formerly at B end
if node.links[0] == nodeB:
node.links[0] = nodeA # link 0 pointed back at B; point it at A
else:
node.links[1] = nodeA # link 1 pointed back at B; point it at A
end if
node = nodeB.links[1-linkrefB] # the node at the B end, formerly at A end
if node.links[0] == nodeA:
node.links[0] = nodeB # link 0 pointed back at A; point it at B
else:
node.links[1] = nodeB # link 1 pointed back at A; point it at B
end if
end functionThe usual linked list operations (inserting a subsection, deleting a subsection, and so on) still complete in constant time.
The new operation, of reversing a list or a list segment, also completes in constant time.
I can't remember the application I invented this for. I did have a specific problem I was trying to solve, which inspired me to invent reversible lists; but the problem turned out to be easily solved by more conventional means, and also I've forgotten what it was.
The only concrete application I can think of for reversible lists is in implementing the extremely old computer game Qix, in which you draw an arbitrarily shaped line across the screen and one side of the line gets filled in. One algorithm for area filling is the winding number rule, which requires you to make a loop along the perimeter of the area, and therefore is well suited to having the perimeter stored as a linked list of line segments.
So you would have the existing screen perimeter as a list, and you would have the new line drawn by the player as another list. You would divide the perimeter into two parts at the start and end points of the user's line. Then you would join the user's line on to one part of the original perimeter to obtain the boundary of the area to be filled. Once you had filled it, you could then unlink the user's line from that list and link it to the other half of the original perimeter, to be used as the new perimeter of the playable screen. The only trouble is, you need the list to be linked in the opposite order for the two uses, so you either have to construct a second copy pointing the other way, or use reversible lists.
In summary: I can't think of any reason this algorithm might be seriously useful. But it's very cute.
On 2004-11-23 I received mail from one Colin Osterman at the University of Mississippi, who has also invented a similar but more efficient data structure and (in conjunction with César Rego) has actually published papers on it.
His version is called a "satellite list", and involves conceptually
having two linked list nodes per item of real data. Each
node has a link to its sibling, and a link to one of the nodes in
the next item along the list. The clever bit is that each node's
next-item link links to whichever of the nodes in the next item
doesn't link back to this item; so you can traverse the
list very efficiently in either direction just by following
next-item links. To turn round and go back the way you came, you
simply follow one sibling link, which effectively makes a U-turn.
The advantage of this representation is that you need no
if statements to traverse the list, so it's
significantly faster. The additional storage cost is mostly
mitigated by keeping the two sibling nodes side by side in a way
that allows you to get from one to the other by doing bitwise
operations on the node address, which means you still only need to
store two actual pointers per data item, not four.
Here's a link to Osterman and Rego's paper.