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

Let's start looking at the first fundamental data structure: lists.

Lists permeate the functional world. LISP is one of the earliest programming languages. The name LISP means list processor.

The imperative world also uses lists. In an algorithmic sense, lists are great for growing incrementally, for example, when we append elements to an existing list. List append is an O(1) operation in the imperative world. Deleting and inserting nodes anywhere in the list is an O(1) operation too. When we insert or delete a node, its predecessor and successor (if any) are the only nodes affected-a few pointers are juggled and the insertion or deletion is done.

For example, in the preceding list, when we insert node K, the algorithm is pretty ...

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