Random Access List

An interesting persistent data structure that combines the singly linked list with the binary tree is Random-Access List. This data structure allows for random access of its items as well as adding and removing items from the beginning of the list. 

                  It is structured as a Singly Linked List of Completely Balanced Binary Trees. The advantage of this data structure is that it allows access, insertion, and removal of the head of the list in O(1) time as well as provides logarithmic performance in randomly accessing its items. Following is a Random-Access list with 13 items --

Insertion: When a node is added to the list, the first two root nodes (if they exist) are checked to see if they both have the same height. If so, the new node is made the parent of the first two nodes; the current head of the list is made the left child of the new node, and the second root node is made the right child. If the first two root nodes do not have the same height, the new node is simply placed at the beginning of the list and linked to the next tree in the list.

Removal: To remove the head of the list, the root node at the beginning of the list is removed, with its left child becoming the new head and its right child becoming the root of the second tree in the list. The new head of the list is right linked with the next root node in the list. Just see the following figure to get clear picture --

Random Access: The algorithm for finding a node at a specific index is in two parts: in the first part, we find the tree in the list that contains the node we're looking for. In the second part, we descend into the tree to find the node itself. The following algorithm is used to find a node in the list at a specific index:

1. Let I be the index of the node we're looking for. Set T to the head of the list where T will be our reference to the root node of the current tree in the list we're examining.
2. If I is equal to 0, we've found the node we're looking for; terminate algorithm. Else if I is greater than or equal to the number of nodes in T, subtract the number of nodes in T from I and set T to the root of the next tree in the list and repeat step 2. Else if I is less than the number of nodes in T, go to step 3.
3. Set S to the number of nodes in T divided by 2 (the fractional part of the division is ignored. For example, if the number of nodes in the current subtree is 3, S will be 1).
4. If I is less than S, subtract 1 from I and set T to T's left child. Else subtract (S + 1) from I and set T to T's right child.
5. If I is equal to 0, we've found the node we're looking for; terminate algorithm. Else go to step 3.

Following image illustrates how to find the 10^th item in the list --

Algorithm for rest of the operations are straight forward. I don't think, we need to discuss.

______________________________________