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

List append

Consider appending a node to a list. In the mutation world, we traverse the list until we reach the end and then change the last node to point to the new node. This is costly when the list is long and has a complexity of O(n).

For a persistent list (immutable and structurally shared) appending a new value, we need to traverse until the end of the list, copying all the elements on the way.

However, as noted, appending to a list is anyway a slow operation. When we need to append values, we need to ask ourselves whether lists are the right fit for the problem.

Whenever we want to grow a list by appending to the end, we should instead use a vector. When we are done with all of the appending, we could convert the vector into a list, if needed. ...

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