Linked Lists

Overview

A linked list is a sequence of nodes, each containing data and one or more pointers to neighbouring nodes. Lists provide dynamic sizing (no pre-allocation needed) and constant-time insertion/deletion at known positions, at the cost of $O(n)$ random access.

Singly Linked Lists

Each node has a value field and a next pointer. The list is accessed via a head pointer (and optionally a tail pointer for constant-time append).

Operations

Operation	Without tail	With tail
INSERT-HEAD	$\Theta(1)$	$\Theta(1)$
INSERT-TAIL	$\Theta(n)$	$\Theta(1)$
DELETE-HEAD	$\Theta(1)$	$\Theta(1)$
DELETE(x) given node $x$	$\Theta(n)$ (need predecessor)	$\Theta(n)$
DELETE(x) given predecessor	$\Theta(1)$	$\Theta(1)$
SEARCH(k)	$\Theta(n)$	$\Theta(n)$

Insertion at head: create a new node, point its next to the current head, update head to the new node. This is $\Theta(1)$.

Deletion of a node $x$ in a singly linked list requires finding the predecessor of $x$ (to update its next pointer), which takes $\Theta(n)$ in the worst case via a linear scan from head. If the predecessor is already known (e.g. when iterating), deletion is $\Theta(1)$.

Doubly Linked Lists

Each node has prev, value, and next pointers. The list maintains head and optionally tail.

The key advantage: given a pointer to a node $x$, deletion is $\Theta(1)$ — we can reach its predecessor via $x.\!prev$ without a scan.

DELETE(x):                    # x is a node in a doubly linked list
    if x.prev != NIL:
        x.prev.next = x.next
    else:
        L.head = x.next       # x was head
    if x.next != NIL:
        x.next.prev = x.prev

Insertion at head or after a known node is also $\Theta(1)$:

INSERT-HEAD(L, k):
    x = new Node(prev=NIL, key=k, next=L.head)
    if L.head != NIL: L.head.prev = x
    L.head = x

Circular Variants

A circular linked list connects the last node back to the first (and optionally the first’s prev to the last in the doubly linked case). A sentinel node can be used as both head and tail, simplifying boundary checks.

Circular singly linked lists with tail pointer enable $\Theta(1)$ insertion at both ends and $\Theta(1)$ deletion at the front.

Comparison with Arrays

Aspect	Array	Linked List
Random access ($i$-th element)	$\Theta(1)$	$\Theta(n)$
Insert/delete at head	$\Theta(n)$ (shift elements)	$\Theta(1)$
Insert/delete at tail	$\Theta(1)$ amortised or $\Theta(n)$	$\Theta(1)$ with tail pointer
Insert/delete in middle	$\Theta(n)$ (shift)	$\Theta(1)$ if position known, $\Theta(n)$ to find
Search	$\Theta(n)$ linear, $O(\log n)$ if sorted	$\Theta(n)$
Space overhead	None beyond array itself	1–2 pointers per element
Cache locality	Excellent (contiguous memory)	Poor (scattered allocations)

Space Overhead

Type	Pointers per node	Notes
Singly linked	1 (next)	Forward traversal only
Doubly linked	2 (next, prev)	Bidirectional; enables $\Theta(1)$ deletion at known node
Circular	Same as linear variant	Extra pointer logic but no extra fields

Usage in Doug Lea’s Malloc

The classic malloc implementation uses a doubly linked list to track free memory chunks in the heap. Each chunk is preceded by a list node containing the chunk size and free/busy status. Free chunks are linked together; when a chunk is freed, it is coalesced with adjacent free chunks. This is a real-world application of doubly linked lists at massive scale.

Summary

Property	Singly Linked	Doubly Linked
Head insert	$\Theta(1)$	$\Theta(1)$
Tail insert	$\Theta(n)$ (or $\Theta(1)$ with tail)	$\Theta(1)$ with tail
Delete given node	$\Theta(n)$ (need predecessor)	$\Theta(1)$
Search	$\Theta(n)$	$\Theta(n)$
Space per node	1 pointer	2 pointers
Traversal	Forward only	Bidirectional