Chapter 7. Random Access Lists

Lists are great when we are prepending or matching at the head, having O(1) complexity. However, as we saw, lists don't perform well when it comes to random element access. Accessing an element at the nth index has O(n) complexity.

Starting at the head, we have to traverse (and skip) all the intervening list elements until we reach the nth element.

Arrays are another fundamental data structure; they allow you to have random access to any element without incurring any additional runtime cost.

Can we tweak our list implementations so random access to elements could be faster? In this chapter, we will see a list implementation that provides efficient lookup and update operations in addition to the usual head, tail, and ...

Get Learning Functional Data Structures and Algorithms now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.