Clojure Data Structures and Algorithms Cookbook

Chapter 2. Alternative Linked Lists

In this chapter, we will discuss the following recipes, related to linked lists:

• Building a doubly linked XOR list
• Speeding up access to linked list elements
• Building a simple shift-reduce parser
• Implementing a skew binary random-access list

Building a doubly linked XOR list

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 ...