Clojure Data Structures and Algorithms Cookbook

Implementing a skew binary random access list

Linked lists are traversed sequentially. To access an element, we need to begin at the top of the list and keep looking for references to the next cell and accessing it until we reach the item of our interest. In big O notation speak, access to an element in plain linked lists is a worst-case O(N) operation, which is quite expensive.

If we want to implement efficient random access to the data that a linked list contains, that is, if we want to specify an index and get to it efficiently—just as in an array, we can consider arranging the same data in a binary search tree, providing for efficient lookup and insertion operations.

If you represent the subscripts of your nodes in a binary format, you'd have ...