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

Summary

Lists are good for operations at the head. However, for randomly accessing an element by its index, the complexity is O(n).

We looked at an alternative list implementation, a list allowing fast random element access. The data structure was really a list of binary trees. The implementation mirrors binary number algorithms.

We saw how all the operations, such as insertion, update, lookup, head, and tail, perform at O(log(n)). We first locate the right tree quickly and then perform a binary search on it.

All these operations are immutable of course. We saw how the process of structural sharing and copying just enough help with the implementation.

Hopefully, this has made you hungrier for more functional data structures and algorithms. So let's ...

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