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 look at some more exciting algorithms. Stay tuned!