Pushing the Information-Theoretic Limits of Random Access Lists: Traversing Cons Lists in (1 + 1/𝜎 ) ⌊lg 𝑛⌋ + 𝜎 + 9 Steps

Abstract

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⌈lgn⌉−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/σ)⌊lgn⌋+σ+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.