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 cons operations.
Understanding the binary numerical representation is the key.
Earlier, we saw how we could model binary numbers as lists. We looked at the addition and multiplication of such lists. We will briefly look at the binary operations again...
