5 min read
On this page

Linked Lists

A linked list stores elements in nodes scattered throughout memory, connected by pointers. Each node contains data and a reference to the next (and possibly previous) node.

Singly Linked List

Each node points to the next node. The last node points to null.

head → [10|→] → [20|→] → [30|→] → [40|∅]

STRUCTURE Node
    data : element
    next : pointer to Node (or NULL)

STRUCTURE SinglyLinkedList
    head : pointer to Node (or NULL)

Operations

| Operation | Time | Notes | |---|---|---| | Access by index | O(n) | Must traverse from head | | Insert at head | O(1) | Update head pointer | | Insert at tail | O(n) | Must traverse to end (O(1) with tail pointer) | | Insert after a node | O(1) | Given a reference to the node | | Delete head | O(1) | Update head pointer | | Delete a specific node | O(n) | Must find predecessor | | Search | O(n) | Linear traversal |

Advantages vs Arrays

  • O(1) insert/delete at known position (no shifting)
  • Dynamic size (no reallocation needed)
  • No wasted space (exact memory usage per element)

Disadvantages vs Arrays

  • No random access (O(n) to access element k)
  • Poor cache locality (nodes scattered in memory)
  • Extra memory per element (pointer overhead: 8 bytes on 64-bit)
  • Slower traversal in practice (cache misses dominate)

In modern systems, arrays (Vec) almost always outperform linked lists due to cache effects. Linked lists are valuable when frequent insertion/deletion at arbitrary positions is needed and the nodes are already located via another data structure (e.g., LRU cache with hash map).

Doubly Linked List

Each node has pointers to both next and previous nodes.

∅ ← [10|←→] ↔ [20|←→] ↔ [30|←→] ↔ [40|→∅]

Additional Operations

| Operation | Time | |---|---| | Delete a given node | O(1) — can access predecessor via prev pointer | | Insert before a given node | O(1) | | Traverse backward | O(n) |

Trade-off: One extra pointer per node (8 bytes on 64-bit). But O(1) deletion of a known node (vs O(n) for singly linked).

Used in: std::collections::LinkedList in Rust, java.util.LinkedList, LRU cache implementation, OS process/thread lists.

Circular Linked List

The last node points back to the first node (instead of null).

→ [10|→] → [20|→] → [30|→] → [10|→] → ...

Singly circular: Last node's next = head. Doubly circular: Additionally, head's prev = last node.

Applications: Round-robin scheduling, circular buffers, repeating playlists, Josephus problem.

Josephus Problem

n people in a circle, every k-th person is eliminated. Solved with a circular linked list simulation or the recurrence:

J(1) = 0
J(n) = (J(n-1) + k) mod n

XOR Linked List

A memory-efficient doubly linked list using XOR of next and prev pointers:

node.link = prev_addr XOR next_addr

Given one neighbor's address, compute the other: next = node.link XOR prev.

Advantage: One pointer per node instead of two (half the overhead of doubly linked). Disadvantage: Cannot access a node in isolation (need one neighbor). Incompatible with garbage collectors. Rarely used in practice.

Skip List

A probabilistic data structure providing O(log n) search, insert, and delete — a practical alternative to balanced BSTs.

Structure

Multiple levels of linked lists. Each higher level "skips" over more elements.

Level 3: head ─────────────────────────→ 50 ─────→ ∅
Level 2: head ───→ 20 ─────────────────→ 50 ─────→ ∅
Level 1: head ───→ 20 ───→ 30 ─────────→ 50 ───→ 70 → ∅
Level 0: head → 10 → 20 → 30 → 40 → 50 → 60 → 70 → ∅

Start at the top level. Move right while the next element is less than the target. Drop down a level when the next element is too large or the level ends. Repeat until found or at level 0.

Insert

  1. Search for the position (recording the path down through levels).
  2. Insert the new node at level 0.
  3. Flip a coin repeatedly to decide how many levels to promote: promote to level k with probability p^k (typically p = 1/2).

Analysis

Expected height: O(log n). Expected search/insert/delete: O(log n). Expected space: O(n).

Advantages over balanced BSTs:

  • Simpler implementation (no rotations)
  • Lock-free concurrent versions are easier to implement
  • Good cache behavior for sequential scans (level 0 is a sorted linked list)

Used in: Redis sorted sets, LevelDB/RocksDB memtable, Lucene.

Unrolled Linked List

Each node stores an array of elements instead of a single element.

head → [10,20,30,40 | next→] → [50,60,70,80 | next→] → ∅

Advantages: Better cache locality (array within node). Less pointer overhead per element. B-tree-like performance for sequential access.

Typical node size: Fits in one or two cache lines (64-128 bytes).

Self-Organizing Lists

Rearrange elements based on access patterns to improve average search time.

Move-to-Front (MTF)

On access, move the accessed element to the head. Frequently accessed elements stay near the front.

Analysis: MTF is within a factor of 2 of the optimal static ordering (competitive ratio 2).

Used in: Compression algorithms (MTF transform in BWT/bzip2), LRU cache approximation, adaptive algorithms.

Transpose

On access, swap the accessed element with its predecessor. Slower adaptation than MTF but more stable.

Frequency Count

Maintain access counts. Keep the list sorted by count. Optimal but requires more bookkeeping.

Sentinel Nodes

A sentinel (dummy) node simplifies boundary conditions by eliminating null checks.

// Without sentinel: must check for null head
fn insert(head: &mut Option<Box<Node>>, val: i32) {
    match head {
        None => *head = Some(Box::new(Node::new(val))),
        Some(node) => { /* ... */ }
    }
}

// With sentinel: head always points to sentinel
// sentinel.next is the first real element
fn insert(sentinel: &mut Node, val: i32) {
    let new_node = Box::new(Node { data: val, next: sentinel.next.take() });
    sentinel.next = Some(new_node);
}

Doubly linked list with sentinel: One sentinel node where sentinel.next = first and sentinel.prev = last. Circular: first.prev = sentinel, last.next = sentinel.

Linked Lists in Rust

Linked lists are notoriously difficult in Rust due to ownership rules:

  • Box: Singly linked (owned). Natural fit.
  • Rc<RefCell>: Shared ownership. Needed for doubly linked (cycles).
  • Raw pointers: Unsafe. Used in std LinkedList.

The canonical resource: "Learning Rust With Entirely Too Many Linked Lists" (https://rust-unofficial.github.io/too-many-lists/).

Applications in CS

  • OS kernel: Process lists, scheduler queues, free memory lists. Linux kernel uses intrusive linked lists (list_head).
  • LRU cache: Doubly linked list + hash map. O(1) access, insertion, and eviction. Used in every caching layer.
  • Memory allocators: Free lists (linked lists of available memory blocks). Malloc implementations use various list strategies.
  • Undo/Redo: Doubly linked list of states or operations.
  • Hash table chaining: Each bucket is a linked list of entries with the same hash.
  • Polynomial representation: Sparse polynomial as a linked list of (coefficient, exponent) pairs.
  • Graph adjacency lists: Each vertex has a linked list of neighbors (though arrays are often used in practice).
  • Garbage collection: Free lists, mark-sweep uses linked lists to track objects.