What In The Hell Are Linked Lists?

Singly-Linked Lists

This is the first in a series of articles describing programming concepts. This series assumes you have some basic experience in programming, but attempts to describe these concepts as simplistically as possible. This series will mainly use Python as the language of choice for examples. This is not because of any perceived superiority of Python over other languages, rather Python is basically executable psudo-code so we can express the concepts simply and give you a chance to play with them inside an interpreter.

A linked list is one of the simplest data structures, at its heart it is simply a two element node (or cell). The first slot contains the data and the second slot contains a pointer to the next node. A simple illustration demonstrates this concept more concretely...

The graphic above represents the list (1, 2, 3). Each node in the list has two parts, data and pointer. The last node has a special symbol 'Nil' to tell both us and the computer that we have reached the end of the list. The python code for each node in the list is below...

class Node:

def __init__(self, data=None, next=None):
self.data = data
self.next = next


def __repr__(self):
return repr(self.data)

To make a list out of these nodes we would need to make a node for each element in the list (1, 2 and 3) and link them together.

>>> a = Node(1, Node(2, Node(3, None)))
>>> print a
1
>>> print a.next
2
>>> print a.next.next
3
>>> print a.next.next.next
None

Notice the nesting of the calls to Node above. Linked lists are an inherently nested data structure. To construct the list without having to nest the calls to Node we would have to work backwards. We have to do this because if we try to create the first node (1) there is not currently a second node to which we can point to.

c = Node(3, None)
b = Node(2, c)
a = Node(1, b)

The graphic below shows another way to look at Nodes that reflects their nested nature.

Programming languages like Lisp and Scheme make heavy use of linked lists. Consequently they have a rich library of functions for dealing with them. The code below shows how you create a linked list in Scheme using the 'cons' function. 'cons' is short for construct and the nodes are called 'cons cells'.

> (define a (cons 1 (cons 2 (cons 3 '()))))
> a
(1 2 3)

Now that we have created a list with cons (note its similarity to the Python example of Node) we can use the built-in procedures car and cdr to access elements of that list.

> (car a)
1
> (cdr a)
(2 3)
> (car (cdr a))
2
> (cdr (cdr a))
(3)
> (car (cdr (cdr a)))
3
> (cdr (cdr (cdr a)))
()

Most Scheme implementations usually define shorthand functions for performing these operations, like cadr and caddr (and many more). Many also provide more descriptive names such as first, rest, second, third...

> (cadr a)
2
> (caddr a)
3
> (cddr a)
(3)
> (first a)
1
> (rest a)
(2 3)
> (second a)
2
> (third a)
3

Constructing linked lists and accessing their elements is usually most elegantly accomplished using recursion. The Scheme code below shows how we would recursively construct a list of integers, we have to do it backward to avoid a call to (reverse).

> (define (make-list-of-integers start stop)
(let loop ((s stop) (aList '()))
(if (< s start)
aList
(loop (- s 1) (cons s aList)))))
> (make-list-of-integers 0 5)
(0 1 2 3 4 5)

Circular Linked Lists

A circular list is a linked-list where the last element's pointer is set to the first element of the list. There are many uses for circular lists (EDIT: list some uses).

The graphic below shows the nodes of a circular list.

Using the Node class that we defined above we can create a circular list in Python as follows...

> a = Node(1)
> a.next = Node(2, Node(3, a))
> a.next
2
> a.next.next
3
> a.next.next.next
1
> a.next.next.next.next
2

The Scheme code for defining a circular list is below...

> (define a (cons 1 (cons 2 (cons 3 '()))))
> (set-cdr! (cddr a) (car a))
> a
(1 2 3 . 1)

Doubly-Linked Lists

Usually the term linked list refers to singly-linked lists as we have implemented them above. However there are other ways of implementing linked lists as well. The next most common form of linked list is the doubly-linked list. This is very similar to singly-linked lists except that each node in the list also contains a pointer to the previous node as shown in the graphic below.

Below is the Python code to implement doubly-linked lists.

class dNode:
def __init__(self, prev=None, data=None, next=None):
self.prev = prev
self.data = data
self.next = next

def __repr__(self):
return str(self.data)

> a = dNode(data=1)
> b = dNode(data=2)
> c = dNode(data=3)
> d = dNode(data=4)
> a.next = b
> b.prev, b.next = a, c
> c.prev, c.next = b, d
> d.prev = c

> a
1
> a.next
2
> a.next.next
3
> a.next.next.prev
2
> a.next.next.next.prev
3

To make the doubly-linked list easier to use we would have to add some helper functions. As you can see it is fairly difficult to create a doubly-linked list, so we'll define an append function here that will make creating one a little easier.

def dAppend(dLinkedList, nodeToAppend):
if dLinkedList.next == None:
dLinkedList.next = nodeToAppend
nodeToAppend.prev = dLinkedList
else:
dAppend(dLinkedList.next, nodeToAppend)

> a = dNode(data=1)
> dAppend(a, dNode(data=2)
> dAppend(a, dNode(data=3)
> a
1
> a.next
2
> a.next.next
3
> a.next.next.prev
2
> a.next.prev
1

The simplest way to achieve this is through a recursive function as defined above. However Python does not perform tail-call optimization and will either run out of memory or reach its recursion limit (default is 1000) on large lists. Below is a non-recursive version of the same function.

def dNodeAppend(dLinkedList, nodeToAppend):
node = dLinkedList
while True:
if node.next == None:
node.next = nodeToAppend
nodeToAppend.prev = node
break
else:
node = node.next

>>> a = dNode(data=1)
>>> dNodeAppend(a, dNode(data=2))
>>> dNodeAppend(a, dNode(data=3))
>>> dNodeAppend(a, dNode(data=4))
>>> a
1
>>> a.next
2
>>> a.next.next
3
>>> a.next.next.next
4
>>> a.next.next.next.prev
3
>>> a.next.next.prev
2
>>> a.next.prev
1






Links

How to Think Like A Computer Scientist - Chapter 17 - Linked Lists
This chapter describes a way of implementing linked lists in Python. It also covers circular lists.
http://greenteapress.com/thinkpython/html/chap17.html

An Introduction to Scheme and its Implementation - Lists
http://www-pu.informatik.uni-tuebingen.de/users/sperber/pfg-2001/scheme/schintro-v14/schintro_93.html

Wikipedia Article on Linked Lists
http://en.wikipedia.org/wiki/Linked_list