Learning Functional Data Structures and Algorithms

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