Pushing the Information-Theoretic Limits of Random Access Lists: Traversing Cons Lists in (1 + 1/๐ ) โlg ๐โ + ๐ + 9 Steps
Edward Peters, Yong Qi Foo, Michael D. Adams ยท Proceedings of the ACM on Programming Languages ยท 2025
Accessing an arbitrary element of a singly linked list or cons list requires traversing up to a linear number of pointers. The applicative random-access list is a data structure that behaves like a cons list except that accessing an arbitrary element traverses only a logarithmic number of pointers. Specifically, in a list of length n , an arbitrary element can be accessed by traversing at most 3 โ lg n โ โ 5 pointers. In this paper, we present a simple variation on random-access lists that improves this bound and requires traversing at most 2 โ lg ( n + 1 ) โ โ 3 pointers. We then present a more complicated variation that improves this bound to ( 1 + 1 ฯ ) โ lg n โ + ฯ + 9 for any ฯ โฅ 1 . This shows that it is possible to get asymptotically close to the information-theoretically optimal bound of โ lg ( n + 1 ) โ โ 1 .