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 the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
