In a linked list, we chain elements to the next occurring item by storing a reference in each element. Hence, you can only walk linked lists in a single direction, accessing at each step the information about where to look for the next cell. Take the example of Clojure, where seq is implemented as a linked list. Here, to walk this data structure, you can only call rest to access tail elements, and you have no means of moving backwards.

One way to add backward-moving capability to linked lists is to turn them into doubly linked lists. Just as you store the information in each cell about the next one, you would also have to store a reference to the previous element. However, you'd have to store two references in each cell, doubling your needs in memory to store pointers to elements.

When you cannot afford to bear this memory overhead, but require the ability to traverse a list in both directions, a doubly linked XOR list can be used. Such a list is constructed...