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 nodes connected to the subtrees that contain the elements that are next to them. Using such subscripts, you could navigate from a parent node to one of its children by simply adding a bit to its subscript at the least weight position...
