Linked list visualization

A singly linked list is a sequence of nodes. Each node holds a value and a link to the next node, and the last node's link is null. The list itself only remembers its first node, called head. Unlike an array, the nodes are not side by side: the only way from one to the next is to follow a link.

How it works

There are four operations. They change links; no value moves.

1. insertHead(x) makes a node whose link points at the old first node, then moves head to it.
2. insertTail(x) has no tail pointer to use, so it starts at head and follows links until it reaches a node whose link is null. That node's link is then pointed at the new node.
3. search(x) starts at head and follows links until it finds x or reaches null.
4. remove(x) walks the same way but keeps prev, the node just behind cur. When cur holds x, prev's link skips over it. If cur is the first node, head skips over it instead.

Time and space complexity

• Insert at the head, O(1): it makes one node and changes two links, however long the list is.
• Search, tail insert and remove, O(n): they walk from the head, and a list gives no way to jump ahead. The best case is a target in the first node.
• Space, O(n): one node per value, plus one link each.

A worked example

Insert 4, 8, 1, 6 and 3, alternately at the head and at the tail, as the lesson's run does. Then search for 8, remove it, and search for it again. The table lists the nodes from head, and how many links the operation followed to get there.

The list ends as 3, 1, 4, 6, and only links changed along the way. The head inserts followed no links, while insertTail(6) had to follow two to find the last node: this is the cost of having no tail pointer, and it grows with the length. remove(8) stopped with prev at the node 4 and made 4's link skip over 8. The run records 6 writes: one link changed by each of the five inserts and one by the removal.

Pseudocode

L.head is the first node, x.value and x.next are a node's value and link, and NIL stands for null.

INSERT-HEAD(L, v)
    x = a new node with value v
    x.next = L.head
    L.head = x

INSERT-TAIL(L, v)
    x = a new node with value v, x.next = NIL
    if L.head == NIL
        L.head = x
        return
    cur = L.head
    while cur.next != NIL
        cur = cur.next
    cur.next = x

SEARCH(L, v)
    cur = L.head
    while cur != NIL and cur.value != v
        cur = cur.next
    return cur                // NIL if absent

REMOVE(L, v)
    prev = NIL
    cur = L.head
    while cur != NIL and cur.value != v
        prev = cur
        cur = cur.next
    if cur == NIL
        return false
    if prev == NIL
        L.head = cur.next
    else
        prev.next = cur.next
    return true

In INSERT-HEAD, the line x.next = L.head comes first, so the old list is never unreachable. The three functions that walk have the same loop, and each round of it follows one link.

When to use it, and when not to

• Use it when you add or remove at the front often and never need "the item at position k".
• It is a building block: the hash table keeps one list in each bucket.
• Avoid it when you need to jump to the k-th item, or search the same data many times. An array reaches any position in O(1), and a sorted array can use binary search.

Where it is used

• Adjacency lists for graphs. A graph stores, for each vertex, a list of its neighbors. Adding an edge is an insert at the head, O(1), and a traversal such as breadth-first search walks one list per vertex. The total space is proportional to the number of vertices plus edges (CLRS, section 22.1).
• Free lists in memory allocators. An allocator can keep its unused blocks linked together, using the free block's own memory for the link. Allocating takes the block at the head and freeing puts a block back at the head, each in O(1), and the blocks do not have to be next to each other.
• Caches and hash buckets. A least-recently-used (LRU) cache pairs a hash table with a doubly linked list ordered by use. The table finds a node at once, and the list moves it to the front by changing a few links, with no shifting. The buckets of the hash table lesson are linked lists too.

Common mistake and edge cases

Variations and related ideas

A doubly linked list adds a link to the previous node, so a node that you already hold can be removed in O(1) without searching for prev. A tail pointer makes insertTail O(1), and it is what lets a list serve as a queue. A circular list points the last node back at the first. Inserting and removing only at the head gives a stack. Compared with an array, a list never shifts elements, but it cannot jump to the k-th item, which is why a sorted array with binary search beats it for repeated searches.