Functional linked lists in Python
Linked lists are fundamental data structures that every programmer should know. This article explains how to implement a simple linked list data type in Python using a functional programming style.
Inspiration
The excellent book Programming in Scala inspired me to play around with functional programming concepts in Python. I ended up implementing a basic linked list data structure using a Lisplike functional style and I’d like to share it with you.
I wrote most of this using Pythonista on my iPad. Pythonista is a Python IDEslashscratchpad and surprisingly fun to work with. I recommend it very much if you’re ever stuck without a laptop and want to explore some CS fundamentals :)
So without further ado, let’s dig into the implementation.
Constructing linked lists
Our linked list data structure consists of two fundamental building blocks: Nil
and cons
. Nil
represents the empty list and serves as a sentinel for more complex lists. The cons
operation extends a list at the front by inserting a new value.
The lists we construct using this method consist of nested 2tuples. For example, the list [1, 2, 3]
is represented by the expression cons(1, cons(2, cons(3, Nil)))
which evaluates to the nested tuples (1, (2, (3, Nil)))
.
Nil = None def cons(x, xs=Nil): return (x, xs) assert cons(0) == (0, Nil) assert cons(0, (1, (2, Nil))) == (0, (1, (2, Nil)))
Why should we use this structure, you say?
First, the cons operation is deeply rooted in the history of functional programming. From Lisp’s cons cells to ML’s and Scala’s ::
operator, cons is everywhere – you can even use it as a verb. Can’t be bad to stand on the shoulders of these functional giants, can it?
Second, tuples are a convenient way to define simple data structures. For something as simple as our list building blocks we don’t necessarily have to define a proper class. Plus it keeps this tutorial / thought experiment short and sweet.
Third, tuples are immutable in Python which means their state cannot be modified after creation. Immutability is often a desired property because it helps you write simpler and more threadsafe code. I like this article by John Carmack where he gives a pragmatic view on functional programming / immutability.
Abstracting away the tuple construction using the cons
function gives us a lot of flexibility on how lists are represented internally as Python objects. For example, instead of using 2tuples we could store our elements in a chain of anonymous functions using Python’s lambda
keyword.
def cons(x, xs=Nil): return lambda i: x if i == 0 else xs
To make the tests for the following list operations slightly simpler to write we’ll introduce the helper function lst
. That allows us to define list instances using a more convenient syntax and without deeply nested cons
calls.
def lst(*xs): if not xs: return Nil else: return cons(xs[0], lst(*xs[1:])) assert lst() == Nil assert lst(1) == (1, Nil) assert lst(1, 2, 3, 4) == (1, (2, (3, (4, Nil))))
Basic operations
All operations on linked lists can be expressed in terms of the three fundamental operations head
, tail
, and is_empty
. You’ll see later that these three operations are enough to implement a simple sorting algorithm like insertion sort.

head
returns the first element of a list. 
tail
returns a list containing all elements except the first. 
is_empty
returnsTrue
if the list contains zero elements.
def head(xs): return xs[0] assert head(lst(1, 2, 3)) == 1
def tail(xs): return xs[1] assert tail(lst(1, 2, 3, 4)) == lst(2, 3, 4)
def is_empty(xs): return xs is Nil assert is_empty(Nil) assert not is_empty(lst(1, 2, 3))
Length and concatenation
The length
operation returns the number of elements in a given list. To find the length of a list we need to scan all of its n elements, thus leading to a time complexity of O(n).
def length(xs): if is_empty(xs): return 0 else: return 1 + length(tail(xs)) assert length(lst(1, 2, 3, 4)) == 4 assert length(Nil) == 0
concat
takes two lists as arguments and concatenates them. The result of contact(xs, ys)
is a new list that contains all elements in xs
followed by all elements in ys
. We implement list concatenation with a simple divide and conquer algorithm.
def concat(xs, ys): if is_empty(xs): return ys else: return cons(head(xs), concat(tail(xs), ys)) assert concat(lst(1, 2), lst(3, 4)) == lst(1, 2, 3, 4)
Last, init, and list reversal
The basic operations head
and tail
have corresponding operations last
and init
. Calling last
returns the last element of a nonempty list and init
returns all elements except the last one (the initial elements).
def last(xs): if is_empty(tail(xs)): return head(xs) else: return last(tail(xs)) assert last(lst(1, 3, 3, 4)) == 4
def init(xs): if is_empty(tail(tail(xs))): return cons(head(xs)) else: return cons(head(xs), init(tail(xs))) assert init(lst(1, 2, 3, 4)) == lst(1, 2, 3)
Both operations need O(n) time to compute their result. Therefore it makes sense to reverse the list if you frequently use last
or init
to access list elements. The reverse
function below implements list reversal, albeit in a slow way that takes O(n²) time.
def reverse(xs): if is_empty(xs): return xs else: return append(reverse(tail(xs)), cons(head(xs), Nil)) assert reverse(Nil) == Nil assert reverse(cons(0, Nil)) == (0, Nil) assert reverse(lst(1, 2, 3, 4)) == lst(4, 3, 2, 1) assert reverse(reverse(lst(1, 2, 3, 4))) == lst(1, 2, 3, 4)
Prefixes and suffixes
The following operations take
and drop
generalize head
and tail
by returning arbitrary prefixes and suffixes of a list. For example, take(2, xs)
returns the first two elements of the list xs
whereas drop(3, xs)
returns everything except the last three elements in xs
.
def take(n, xs): if n == 0: return Nil else: return cons(head(xs), take(n1, tail(xs))) assert take(2, lst(1, 2, 3, 4)) == lst(1, 2)
def drop(n, xs): if n == 0: return xs else: return drop(n1, tail(xs)) assert drop(1, lst(1, 2, 3)) == lst(2, 3) assert drop(2, lst(1, 2, 3, 4)) == lst(3, 4)
Element selection
Random element selection on linked lists does not really make sense in terms of time complexity, as accessing an element at index n requires O(n) time. Nevertheless, the element access operation apply
is simple to implement using the head
and drop
operations.
def apply(i, xs): return head(drop(i, xs)) assert apply(0, lst(1, 2, 3, 4)) == 1 assert apply(2, lst(1, 2, 3, 4)) == 3
More complex examples
The three basic operations head
, tail
, and is_empty
are enough to implement a simple (and slow) sorting algorithm like insertion sort.
def insert(x, xs): if is_empty(xs) or x <= head(xs): return cons(x, xs) else: return cons(head(xs), insert(x, tail(xs))) assert insert(0, lst(1, 2, 3, 4)) == lst(0, 1, 2, 3, 4) assert insert(99, lst(1, 2, 3, 4)) == lst(1, 2, 3, 4, 99) assert insert(3, lst(1, 2, 4)) == lst(1, 2, 3, 4) def isort(xs): if is_empty(xs): return xs else: return insert(head(xs), isort(tail(xs))) assert isort(lst(1, 2, 3, 4)) == lst(1, 2, 3, 4) assert isort(lst(3, 1, 2, 4)) == lst(1, 2, 3, 4)
The following to_string
operation flattens the recursive structure of a given list and returns a Pythonstyle string representation of its elements. This is useful for debugging and makes for a nice little programming exercise.
def to_string(xs, prefix="[", sep=", ", postfix="]"): def _to_string(xs): if is_empty(xs): return "" elif is_empty(tail(xs)): return str(head(xs)) else: return str(head(xs)) + sep + _to_string(tail(xs)) return prefix + _to_string(xs) + postfix assert to_string(lst(1, 2, 3, 4)) == "[1, 2, 3, 4]"
Where to go from here
This article is more of a thought experiment than a guide on how to implement a useful linked list in Python. Keep in mind that the above code has severe restrictions and is not fit for real life use. For example, if you use this linked list implementation with larger example lists you’ll quickly hit recursion depth limits (CPython doesn’t optimize tail recursion).
I spent a few fun hours playing around with functional programming concepts in Python and I recommend you do the same. If you want to explore functional programming in “real life” Python, I suggest you try the following resources: