O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required