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

We looked at lists again, but in a different light. We revisited the list prepending and appending techniques and saw that prepending a node to a list has O(1) complexity. It is a very fast operation, sharing most of the existing list.

Appending to a list is very costly though, as we end up copying the entire existing list. We looked at list reversal and saw how we could express the list reversal algorithm in terms of list prepending.

Next, we saw how extensively list prepending is used. We looked at directed graphs, modeling them as a list of pairs.

We also implemented common graph algorithms, such as getting successors of a node and a depth-first traversal.

Incrementally tweaking the depth-first traversal, we came up with topological sorting, ...

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