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 .

@article{paperbot3034,
  title = {Pushing the Information-Theoretic Limits of Random Access Lists: Traversing Cons Lists in (1 + 1/𝜎 ) ⌊lg 𝑛⌋ + 𝜎 + 9 Steps},
  author = {Edward Peters and Yong Qi Foo and Michael D. Adams},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {9},
  number = {ICFP},
  year = {2025},
  doi = {10.1145/3747536}
}