Random-access list

A persistent list representation supporting positional lookup more efficiently than a conventional linked list. Different implementations trade lookup, insertion and deletion costs; “random-access” does not itself guarantee constant-time indexing. A skew-binary random-access list supports worst-case constant-time front insertion and removal with logarithmic worst-case lookup.

Represent a finite list by a forest of value-bearing perfect binary trees of sizes $1,3,7,\dots$, in nondecreasing order, using the greedy largest sizes and allowing a repeated size only in the first two positions. Concatenated preorder traversals recover the list. Cached tree sizes guide indexing.

Front insertion merges the first two equal-size trees beneath a new root, or adds a singleton if they differ. Removing the first root either discards a singleton or splits its two children into the initial equal-size pair. Both operations inspect and allocate only a bounded number of constructors, taking worst-case constant time and sharing the remaining representation. A positional query skips whole cached tree sizes and then descends through one tree, taking $O(\log (n+1))$ time. Conversion in either direction takes linear time on finite input.

The duplicate-size restriction follows directly from greediness. If two size-$w$ trees had any preceding nonempty portion, there would be at least $2w+1$ elements available, enough for the next larger perfect binary tree. Three equal-size trees would likewise suffice for that larger tree. Both contradict the greedy representation.