Linked lists

A linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (aka link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that access time is linear

Linked lists are about the simplest data structure beyond arrays. They aren’t very efficient for many purposes, but have very good performance for certain specialized applications and they are used as building blocks to implement several other common abstract data types, including lists, stacks, queues, associative arrays.

We’ll use linked lists to build these data structures in the subsequent chapters. This chapter provides a high-level overview of linked lists.

The basic idea is that instead of storing n items in one big array, we store each item in its own struct, and each of these structs includes a pointer to the next struct in the list (with a null pointer to indicate that there are no more elements). If we follow the pointers we can eventually reach all of the elements.

For example, if we declare the struct holding each element like this:

struct elt {
    struct elt *next;  /* pointer to next element in the list */
    int contents;      /* contents of this element */
};

We can build a structure like this:

The box on the far left is not a struct elt, but a struct elt *; in order to keep track of the list we need a pointer to the first element. As usual in C, we will have to do all the work of allocating these elements and assigning the right pointer values in the right places ourselves.

Looping over a linked list

Looping over a linked list is not hard if you have access to the next pointers. (For a more abstract way to do this look up iterators.)

Let’s imagine somebody gave us a pointer to the first struct stack in a list; call this pointer first. Then we can write a loop like this that prints the contents of the stack:

void
stackPrint(struct stack *first)
{
    struct stack *elt;

    for(elt = first; elt != 0; elt = elt->next) {
        puts(elt->book);
    }
}

There’s not a whole lot to notice here except that for is perfectly happy to iterate over something that isn’t a range of integers. The running time is linear in the length of the list (O(n)).

Looping over a linked list backwards

What if we want to loop over a linked list backwards? The next pointers all go the wrong way, so we have to save a trail of breadcrumbs to get back. The safest way to do this is to reverse the original list into an auxiliary list:

void
stackPrintReversed(struct stack *first)
{
    struct stack *elt;
    Stack s2;                   /* uses imperative implementation */

    s2 = stackCreate();

    for(elt = first; elt != 0; elt = elt->next) {
        s2 = stackPush(s2, elt->book);
    }

    stackPrint(s2);
    stackDestroy(s2);
}

Pushing all the elements from the first list onto s2 puts the first element on the bottom, so when we print s2 out, it’s in the reverse order of the original stack.

We can also write a recursive function that prints the elements backwards. This function effectively uses the function call stack in place of the extra stack s2 above.

void
stackPrintReversedRecursive(struct stack *first)
{
    if(first != 0) {
        /* print the rest of the stack */
        stackPrintReversedRecursive(first->next);

        /* then print the first element */
        puts(first->book);
    }
}

The code in stackPrintReversedRecursive is shorter than the code in stackPrintReversed, and it is likely to be faster since it doesn’t require allocating a second stack and copying all the elements. But it will only work for small stacks: because the function call stack is really a fixed-size array, if the input to stackPrintReversedRecursive is too big the recursion will go too deep cause a stack overflow.

What linked lists are and are not good for

Linked lists are good for any task that involves inserting or deleting elements next to an element you already have a pointer to; such operations can usually be done in O(1) time. They generally beat arrays (even resizable arrays) if you need to insert or delete in the middle of a list, since an array has to copy any elements above the insertion point to make room; if inserts or deletes always happen at the end, an array may be better.

Linked lists are not good for any operation that requires random access, since reaching an arbitrary element of a linked list takes as much as O(n) time. For such applications, arrays are better if you don’t need to insert in the middle; if you do, you should use some sort of tree.

Linked lists are often the primary data structure in functional programming languages. The reason of this is that the functional programming style tries to avoid modifying data, which makes arrays expensive since changing one value might mean creating a new copy of the entire array. With linked lists, it may be possible for some operations to create a new list that shares most of its structure with the old list; an example would be pushing or popping the top of a stack. This kind of sharing is awkward in languages like C because it means that a struct implementing part of a list might have multiple pointers to it, making it tricky to detect when it is safe to free the struct.