Accessing an arbitrary element of a singly linked list
or \emph{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\left\lceil \lg n\right\rceil -5$ pointers.

In this paper, we present a simple variation on random-access lists that improves
this bound and requires traversing at most $2\left\lceil \lg\left(n+1\right)\right\rceil - 3$
pointers. We then present a more complicated variation that improves
this bound to $(1+\frac{1}{\sigma})\left\lfloor \lg n\right\rfloor +\sigma+9$
for any $\sigma\ge 1$. This shows that it is possible to get asymptotically
close to the information-theoretically optimal bound of $\left\lceil \lg\left(n+1\right)\right\rceil -1$.