Linked List Basics

A linked list earns its place when you already have a handle to the node you want to change—insert or delete right there in constant time, no shifting required. The cost: give up random access entirely.

Difficulty: Beginner | Prerequisites: Arrays and Strings | CF Rating Range: 1100–1800

Intuition

You have an array a = [10, 20, 30, 40, 50]. You need to insert 25 at index 2 (between 20 and 30), then delete the element at index 4, then insert 5 at index 0. Watch the cost:

Operation 1: Insert 25 at index 2.

text

Before: [10, 20, 30, 40, 50]
                 ^--- shift 30, 40, 50 right by one
After:  [10, 20, 25, 30, 40, 50]

Elements shifted: 3.

Delete element at index 4 (value 40):

text

Before: [10, 20, 25, 30, 40, 50]
                          ^--- shift 50 left by one
After:  [10, 20, 25, 30, 50]

Elements shifted: 1.

Insert 5 at index 0:

text

Before: [10, 20, 25, 30, 50]
         ^--- shift ALL five elements right
After:  [5, 10, 20, 25, 30, 50]

Elements shifted: 5.

Total element moves across three operations: 9. In general, each insert or delete on an array of $n$ elements costs $O (n)$ in the worst case. Do $q$ such operations and you pay $O (n q)$ . For $n = q = 10^{5}$ that is $10^{10}$ moves—far too slow.

The pattern is the same every time: the values themselves don't change, but we pay to drag the suffix out of the way. If the structure remembered neighbors instead of forcing contiguity, the work could stay purely local.

If each element remembers where the next one lives, inserting or removing a link never requires moving anything else.

Think of a scavenger hunt where each card says "go to location X for the next clue." To add a clue between clue 3 and clue 4, you write a new card, point it to location 4, then update clue 3 to point to the new card. Nobody else moves. To remove a clue, you update its predecessor to skip over it. The chain stays intact.

Or imagine paper clips in a chain: to insert one in the middle, unhook one connection, clip the new one in, and reconnect. The clips on either side stay exactly where they are.

But the analogy hides the tradeoff. You cannot jump directly to the 47th clue—you must follow every link from the start. Random access is $O (n)$ , not $O (1)$ .

Visual Walkthrough

Use the same example, but think in pointers instead of array shifts: start with [10, 20, 30, 40, 50], insert 25 after 20, delete 40, then insert 5 at the front.

Step 1: Build the list from [10, 20, 30, 40, 50].

text

  head
   |
   v
  [10]->[20]->[30]->[40]->[50]->null

Each box is a node. The arrow is the next pointer.

Step 2: Insert 25 after the node containing 20.

Find the node with value 20 (traverse from head: 1 hop). Create [25]. Set new->next = node20->next (which is [30]), then node20->next = new.

text

  head
   |
   v
  [10]->[20]->[25]->[30]->[40]->[50]->null
                ^
               new

Pointer rewires: 2. Elements moved: 0.

Step 3: Delete the node containing 40.

We need [40]'s predecessor, which is [30]. Set node30->next = node40->next, then free [40].

text

  head
   |
   v
  [10]->[20]->[25]->[30]->[50]->null

                    [40] freed

Pointer rewires: 1. Elements moved: 0.

Step 4: Insert 5 at the front.

Create [5]. Set new->next = head, then head = new.

text

  head
   |
   v
  [5]->[10]->[20]->[25]->[30]->[50]->null
   ^
  new

Pointer rewires: 1. Elements moved: 0.

Operation	Array (shifts)	Linked List (pointer ops)
Insert 25 after 20	3	2
Delete 40	1	1
Insert 5 at front	5	1
Total	9	4

The linked list does zero data movement. The cost is the traversal to find the right node—but once there, surgery is instant. That is the fundamental tradeoff: you walk the chain to find your spot, then act in $O (1)$ .

Invariants

text

+----------------------------------------------------------+
| SINGLY LINKED LIST INVARIANT                             |
|                                                          |
| 1. Each node's next pointer points to its logical        |
|    successor, or null if it is the last node.            |
| 2. Following next from head visits every element exactly |
|    once and terminates at null.                          |
| 3. No node is the successor of more than one node.       |
+----------------------------------------------------------+

For a doubly linked list, add:

text

+----------------------------------------------------------+
| DOUBLY LINKED LIST INVARIANT                             |
|                                                          |
| For every pair of adjacent nodes A and B:                |
|   A->next == B  <==>  B->prev == A                       |
|                                                          |
| head->prev == null  and  tail->next == null              |
+----------------------------------------------------------+

Every operation must restore these invariants before it returns. After Step 2 above, the correct state is node20->next == node25, node25->next == node30, and the chain from head reaching all six nodes and terminating at null.

What the Code Won't Teach You

The useful lesson is not "linked lists are fast"—it is "linked lists are fast only when you already hold the node you want." In contest code, that usually means the list is one component of a larger trick, not the whole answer.

In CP, "linked list problems" rarely use actual linked lists. Most problems that feel like list manipulation—reorder, splice, remove elements—are solved with arrays, deques, or index tricks. Pointer-based linked lists are interview tools, not contest tools.
The array-as-linked-list idiom is faster and cache-friendlier. Instead of Node* pointers scattered across the heap, use nxt[] and prv[] arrays. Nodes live in contiguous memory, the CPU prefetcher stays happy, and allocator overhead disappears entirely.

text

Pointer-based:                    Array-based:
heap addr 0x3A -> Node{val,next}   pool[0] pool[1] pool[2] pool[3] ...
heap addr 0x91 -> Node{val,next}   +------+------+------+------+
heap addr 0x17 -> Node{val,next}   | val  | val  | val  | val  |  contiguous
(scattered, random addresses)     | nxt  | nxt  | nxt  | nxt  |  in memory
                                  +------+------+------+------+

Cache performance can outweigh asymptotic complexity. A vector with $O (n)$ shifts can beat a linked list with $O (1)$ inserts because sequential memory access is 10–100× faster than random pointer chasing. Measure the constant factor before committing to a linked list.
The genuine use cases are narrow: LRU cache (doubly linked list + hash map), dancing links / Algorithm X (exact cover), and any problem where you already hold a handle to the node and need $O (1)$ removal. Without that direct reference, the $O (n)$ find cost cancels the $O (1)$ insert/delete advantage entirely.

When to Reach for This

The best linked-list problems give you a handle, a splice, or an undo step instead of a search problem.

Trigger phrases in problem statements:

"Insert or delete at arbitrary positions frequently"
"Splice one sequence into another"
"Maintain an ordered collection with fast removal"
"Implement LRU / LFU cache"
"Exact cover / dancing links"

Counter-examples—looks like linked list, but isn't:

"Access the $k$ -th element repeatedly"—use array or balanced BST
"Need fast lookup by value"—use hash set/map
"Sorted insert + sorted access"—use std::set or sorted vector

Honest assessment for competitive programming: linked lists are rarely the direct answer. Arrays with index tricks, deques, or policy-based trees almost always win on cache locality and code simplicity. But the concept is foundational—linked lists appear inside hash maps (chaining), adjacency lists, memory allocators, and advanced structures like dancing links (DLX). Expect them on LeetCode-style problems and occasionally in CF problems involving explicit list manipulation.

C++ STL Reference

`std::list<T>`—Doubly Linked List

Operation	Method	Time
Push front	`push_front(x)`	$O (1)$
Push back	`push_back(x)`	$O (1)$
Pop front	`pop_front()`	$O (1)$
Pop back	`pop_back()`	$O (1)$
Insert before iter	`insert(it, x)`	$O (1)$
Erase at iter	`erase(it)`	$O (1)$
Splice	`splice(pos, other)`	$O (1)$
Sort	`sort()`	$O (n \log n)$
Reverse	`reverse()`	$O (n)$
Merge sorted	`merge(other)`	$O (n)$
Size	`size()`	$O (1)$

`std::forward_list<T>`—Singly Linked List

Operation	Method	Time
Push front	`push_front(x)`	$O (1)$
Insert after iter	`insert_after(it, x)`	$O (1)$
Erase after iter	`erase_after(it)`	$O (1)$
Sort	`sort()`	$O (n \log n)$
Reverse	`reverse()`	$O (n)$
Merge sorted	`merge(other)`	$O (n)$

Note: forward_list has no size()—call std::distance(fl.begin(), fl.end()) for $O (n)$ . In CP, a manual node struct is almost always preferable to either STL container.

Implementation

Singly Linked List (Pointer-Based)

cpp

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node* next;
    Node(int v, Node* n = nullptr) : val(v), next(n) {}
};

Node* head = nullptr;

void push_front(int v) {
    head = new Node(v, head);
}

// Insert value v after node p. Caller guarantees p != nullptr.
void insert_after(Node* p, int v) {
    p->next = new Node(v, p->next);
}

// Delete the node after p. Does nothing if p->next is null.
void delete_after(Node* p) {
    if (!p->next) return;
    Node* tmp = p->next;
    p->next = tmp->next;
    delete tmp;
}

void traverse(Node* h) {
    for (Node* cur = h; cur; cur = cur->next)
        cout << cur->val << " ";
    cout << "\n";
}

Reversing a Singly Linked List

The classic three-pointer technique. The critical invariant: before advancing cur, its next pointer must already be rewired to prev.

cpp

// Iterative reverse. Returns new head.
Node* reverse(Node* h) {
    Node* prev = nullptr;
    while (h) {
        Node* nxt = h->next;
        h->next = prev;
        prev = h;
        h = nxt;
    }
    return prev;
}

Trace prev, cur (h), and nxt through each iteration:

text

Initial:   prev=null   cur=[A]->[B]->[C]->[D]->null

Step 1:    save nxt=[B]
           [A]->null           (cur->next = prev)
           prev=[A]  cur=[B]->[C]->[D]->null

           null<-[A]  [B]->[C]->[D]->null
                  ^    ^
                prev  cur

Step 2:    save nxt=[C]
           [B]->[A]->null      (cur->next = prev)
           prev=[B]  cur=[C]->[D]->null

           null<-[A]<-[B]  [C]->[D]->null
                       ^    ^
                     prev  cur

Step 3:    save nxt=[D]
           [C]->[B]->[A]->null (cur->next = prev)
           prev=[C]  cur=[D]->null

           null<-[A]<-[B]<-[C]  [D]->null
                            ^    ^
                          prev  cur

Step 4:    save nxt=null
           [D]->[C]->[B]->[A]->null  (cur->next = prev)
           prev=[D]  cur=null -> STOP

           null<-[A]<-[B]<-[C]<-[D]
                                  ^
                           prev = new head

Classic bug: losing the head pointer. If you forget Node* nxt = h->next before overwriting h->next = prev, you sever the list and lose all remaining nodes.

Pointer-Based Doubly Linked List

cpp

#include <bits/stdc++.h>
using namespace std;

struct DNode {
    int val;
    DNode *prev, *next;
    DNode(int v) : val(v), prev(nullptr), next(nullptr) {}
};

DNode *head = nullptr, *tail = nullptr;

void push_front(int v) {
    DNode* nd = new DNode(v);
    nd->next = head;
    if (head) head->prev = nd;
    head = nd;
    if (!tail) tail = nd;
}

void push_back(int v) {
    DNode* nd = new DNode(v);
    nd->prev = tail;
    if (tail) tail->next = nd;
    tail = nd;
    if (!head) head = nd;
}

// Insert v after node p.
void insert_after(DNode* p, int v) {
    DNode* nd = new DNode(v);
    nd->next = p->next;
    nd->prev = p;
    if (p->next) p->next->prev = nd;
    else tail = nd;
    p->next = nd;
}

// Delete node p from the list. O(1) -- no traversal needed.
void delete_node(DNode* p) {
    if (p->prev) p->prev->next = p->next;
    else head = p->next;
    if (p->next) p->next->prev = p->prev;
    else tail = p->prev;
    delete p;
}

Deleting node B from A <-> B <-> C requires updating both next and prev on both neighbors—missing any one corrupts traversal in one direction:

text

Before deletion of B:

   +-------+    +-------+    +-------+
   |   A   |--->|   B   |--->|   C   |--> null
   |       |<---| (del) |<---|       |
   +-------+    +-------+    +-------+
   A.next=B     B.prev=A     C.prev=B
                B.next=C

Step 1: A.next = B.next (= C)       // skip B going forward
Step 2: C.prev = B.prev (= A)       // skip B going backward

After deletion of B:

   +-------+                 +-------+
   |   A   |---------------->|   C   |--> null
   |       |<----------------|       |
   +-------+                 +-------+
   A.next=C                  C.prev=A

Edge cases:
  * B is head (B.prev == null):  set head = B.next
  * B is tail (B.next == null):  set tail = B.prev
  * B is the only node:         set head = tail = null

Doubly linked list rule: every operation must update BOTH prev and next. If you only rewire one direction, traversal in the other direction will be corrupt.

Array-Based Linked List

No new/delete, no cache misses from scattered heap pointers—just a pre-allocated fixed-size pool:

cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 5;

struct Node {
    int val, next;  // next is an index, not a pointer
} pool[MAXN];

int head = -1;  // -1 means null
int pool_sz = 0;

int new_node(int v) {
    pool[pool_sz] = {v, -1};
    return pool_sz++;
}

void push_front(int v) {
    int nd = new_node(v);
    pool[nd].next = head;
    head = nd;
}

void insert_after(int p, int v) {
    int nd = new_node(v);
    pool[nd].next = pool[p].next;
    pool[p].next = nd;
}

void delete_after(int p) {
    if (pool[p].next == -1) return;
    pool[p].next = pool[pool[p].next].next;
    // No actual deallocation -- memory stays in pool. Fine for CP.
}

void traverse() {
    for (int i = head; i != -1; i = pool[i].next)
        cout << pool[i].val << " ";
    cout << "\n";
}

Advantages: contiguous memory (cache-friendly), no allocator overhead, trivially resettable between test cases with pool_sz = 0; head = -1;.

text

POINTER-BASED (heap-allocated nodes):

  Memory address:  0x08   0x3A   0x17   0x91   0xC4
                   ...    ...    ...    ...    ...
                  +-----+      +-----+      +-----+
  head ---------->| 10  |      | 30  |      | 50  |
                  | 0x91|      | 0xC4|      | nil |
                  +--+--+      +--+--+      +-----+
                     |   +-----+  |
                     +-->| 20  |  |   Nodes scattered across heap.
                         | 0x17+--+   Each access = potential cache miss.
                         +-----+      CPU prefetcher cannot help.

ARRAY-BASED (pool allocation):

  pool[]:  index:   0       1       2       3       4
                  +------+------+------+------+------+
           val:   |  10  |  20  |  30  |  40  |  50  |  contiguous
           nxt:   |   1  |   2  |   3  |   4  |  -1  |  in memory
                  +------+------+------+------+------+
                     ^
                   head=0

  Same logical linked list, but nodes sit side by side in memory.
  Sequential pool access -> cache lines pre-loaded -> 5-10x faster.

Sentinel-Guarded Doubly Linked List

The full contest-grade implementation. Sentinel nodes eliminate every null/head/tail edge case; include a free list for node recycling and a complete reset for multi-test-case problems.

cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e6 + 5;
const int HEAD = 0;  // sentinel: before all real nodes
const int TAIL = 1;  // sentinel: after all real nodes

int val[MAXN], nxt[MAXN], prv[MAXN];
int pool_sz;
int free_head;  // head of the free list (-1 if empty)

void init() {
    pool_sz = 2;        // slots 0 and 1 are sentinels
    free_head = -1;
    nxt[HEAD] = TAIL;   // empty list: HEAD <-> TAIL
    prv[HEAD] = -1;
    nxt[TAIL] = -1;
    prv[TAIL] = HEAD;
}

int alloc_node(int v) {
    int nd;
    if (free_head != -1) {
        nd = free_head;
        free_head = nxt[free_head];
    } else {
        nd = pool_sz++;
    }
    val[nd] = v;
    nxt[nd] = prv[nd] = -1;
    return nd;
}

void free_node(int nd) {
    nxt[nd] = free_head;
    free_head = nd;
}

// Insert node with value v after node p. Returns new node index.
int insert_after(int p, int v) {
    int nd = alloc_node(v);
    int q = nxt[p];
    nxt[p] = nd; prv[nd] = p;
    nxt[nd] = q;  prv[q] = nd;
    return nd;
}

void push_front(int v) { insert_after(HEAD, v); }
void push_back(int v)  { insert_after(prv[TAIL], v); }

// Erase node x (must not be a sentinel). O(1).
void erase(int x) {
    nxt[prv[x]] = nxt[x];
    prv[nxt[x]] = prv[x];
    free_node(x);
}

// Traverse and print all values from front to back.
void traverse() {
    for (int i = nxt[HEAD]; i != TAIL; i = nxt[i])
        cout << val[i] << " ";
    cout << "\n";
}

// Example: multi-test-case usage
int main() {
    int T;
    cin >> T;
    while (T--) {
        init();  // full reset -- sentinels reinitialized, pool reclaimed
        int n;
        cin >> n;
        for (int i = 0; i < n; i++) {
            int v; cin >> v;
            push_back(v);
        }
        traverse();
    }
}

Compare erase with the pointer-based version above—sentinels cut four branches to zero:

text

Without sentinels (4 branches):          With sentinels (0 branches):

void erase(DNode* p) {                   void erase(int x) {
    if (p->prev) p->prev->next=p->next;     nxt[prv[x]] = nxt[x];
    else head = p->next;                    prv[nxt[x]] = prv[x];
    if (p->next) p->next->prev=p->prev;     free_node(x);
    else tail = p->prev;                 }
    delete p;
}

Sentinels guarantee prv[x] and nxt[x] are always valid indices.
HEAD is always before the first real node. TAIL is always after.
No special cases. No bugs.

Pool reset between test cases is $O (1)$ : init() sets pool_sz back to 2, clears the free list, and re-links the sentinels—regardless of how many nodes the previous test case used.

Floyd's Cycle Detection

Detects a cycle and finds its entry point. $O (n)$ time, $O (1)$ space.

cpp

// Returns the start node of the cycle, or nullptr if no cycle.
Node* find_cycle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            // Cycle detected. Find entry point.
            slow = head;
            while (slow != fast) {
                slow = slow->next;
                fast = fast->next;
            }
            return slow;
        }
    }
    return nullptr;  // no cycle
}

When slow enters the cycle, fast is already some distance ahead inside it. They close the gap by 1 each step, so they must meet. After the meeting, reset one pointer to head and advance both at speed 1; they meet again exactly at the cycle entry. The argument is a modular-arithmetic identity: $2 \cdot d_{slow} = d_{fast}$ modulo cycle length forces the distances to align at the entry node.

The technique generalizes beyond linked lists—it applies to any sequence defined by $x_{i + 1} = f (x_{i})$ , including iterated-function graphs.

Merge Two Sorted Lists

Maintain two pointers and always append the smaller head. This is the core of merge sort on linked lists; in CP the same pointer technique appears on arrays, but it's worth knowing in list form.

cpp

Node* merge(Node* a, Node* b) {
    Node dummy(0);
    Node* tail = &dummy;
    while (a && b) {
        if (a->val <= b->val) { tail->next = a; a = a->next; }
        else                  { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

Operations Reference

Operation	Singly	Doubly	Array (vector)
Access $i$ -th element	$O (n)$	$O (n)$	$O (1)$
Search by value	$O (n)$	$O (n)$	$O (n)$
Insert after known node	$O (1)$	$O (1)$	$O (n)$
Delete known node	$O (n)$ *	$O (1)$	$O (n)$
Push front	$O (1)$	$O (1)$	$O (n)$
Push back	$O (1)$ **	$O (1)$	$O (1)$ amort.
Splice / concatenate	$O (1)$	$O (1)$	$O (n)$
Reverse	$O (n)$	$O (n)$	$O (n)$
Sort	$O (n \log n)$	$O (n \log n)$	$O (n \log n)$

* Singly: deleting a known node requires its predecessor, which means $O (n)$ traversal unless you already hold it. Trick: copy the successor's value into the current node and delete the successor instead— $O (1)$ , but fails on the last node.

** With a tail pointer.

std::list is a doubly linked list; std::forward_list is singly linked and has no size() (use std::distance in $O (n)$ ). In contests, a manual array-based implementation is almost always preferable to either STL container.

Benchmarks

Rough timings on a typical CP judge (~2 GHz, 256 MB)—ballpark numbers to build intuition, not precise benchmarks.

text

Operation (n = 10^5)         | std::list | Array LL  | std::vector
-----------------------------+-----------+-----------+------------
Insert-at-front x n          |   ~12 ms  |   ~3 ms   |   ~35 ms
Random-delete x n (by ptr)   |   ~15 ms  |   ~4 ms   |   ~50 ms
Sequential traverse x 10     |    ~8 ms  |   ~2 ms   |    ~1 ms
Random insert (mid) x n      |   ~18 ms  |   ~5 ms   |   ~45 ms

Array-based LL wins insert/delete against both. No allocator overhead, no cache misses from pointer chasing, no $O (n)$ shifts.
std::vector wins sequential traversal. Contiguous memory lets the prefetcher load entire cache lines ahead. The array-based LL is also contiguous, but traversal follows nxt[] indices rather than sequential addresses—still much better than std::list, but can't match a flat scan.
std::list loses everywhere. Each new fragments memory; each pointer dereference risks a cache miss (~100 CPU cycles stall). Its one real advantage is $O (1)$ splice(), which the other two cannot match.

Cache effects dominate. An L1 miss costs ~4 ns, L2 ~12 ns, LLC ~40–80 ns. A std::list traversal of $10^{5}$ nodes can accumulate ~ $10^{5}$ cache misses × ~50 ns ≈ 5 ms in memory stalls alone. The array-based LL keeps nodes in a contiguous pool, so traversal usually stays in L2/L3 cache.

text

Memory access pattern:

Array (sequential -- cache-friendly):
  +----+----+----+----+----+----+----+----+
  | a0 | a1 | a2 | a3 | a4 | a5 | a6 | a7 |  one cache line
  +----+----+----+----+----+----+----+----+
  Access: -> -> -> -> -> -> -> ->   (prefetcher loads ahead)

Linked list (random jumps -- cache-hostile):
  Memory:  [??][a2][??][??][a5][??][a0][??][a3][??][a1][??][a4]
  Access:   ^         ^              ^         ^         ^
            a0------->a1------------>a2-->a3-->a4------>a5
            miss!     miss!         miss! hit  miss!    miss!

  Each arrow = pointer chase = potential cache miss (~100 cycles).
  Array scans the same data ~10-100x faster on modern hardware.

Problem Patterns & Tricks

Reversing a Linked List

The classic three-pointer technique (shown in the Implementation section above). Appears constantly in interviews, rarely in CP. Maintain prev, cur, nxt and rewire one link per step.

Practice: LeetCode 206 (Reverse Linked List).

Cycle Detection (Floyd's Algorithm)

Reach for this when a problem involves detecting repetition in a sequence defined by $x_{i + 1} = f (x_{i})$ —not just literal linked lists, but functional graphs generally.

Practice: LeetCode 142 (Linked List Cycle II), CF 131D.

Merging Two Sorted Lists

Maintain two pointers and always append the smaller head. Basis of merge sort on linked lists; in CP usually done on arrays, but the technique transfers directly.

Practice: LeetCode 21 (Merge Two Sorted Lists).

The Find-Cost Trap

"Linked lists are faster for insertion" is half-true. $O (1)$ insert/delete requires already having a pointer to the node. If you need to find the insertion point first, that search is $O (n)$ —the same as shifting an array.

text

Task: insert X after the element with value 42.

Array:   find 42 -> O(n) scan -> shift right -> O(n)    Total: O(n)
List:    find 42 -> O(n) scan -> rewire pointer -> O(1)  Total: O(n)
                   ^^^^^^^^^^^^
                   This cost is the same.

Linked lists only win when you ALREADY HAVE a pointer/iterator
to the node (e.g., stored in a hash map, passed from a previous
operation, or maintained during traversal).

Lazy Deletion—the Usual Contest Answer

Many problems ask you to repeatedly remove elements satisfying some condition. Before reaching for a linked list, consider lazy deletion: mark elements dead and skip them during iteration.

text

alive[]: [T] [T] [T] [T] [T]
Remove index 2:
alive[]: [T] [T] [F] [T] [T]    <- O(1), no pointer surgery

For ordered traversal, just skip dead entries:
  for (int i = 0; i < n; i++)
      if (alive[i]) process(a[i]);

For most problems that look list-shaped, lazy deletion is simpler and faster.

Dancing Links (DLX) for Exact Cover

Knuth's technique for exact cover. Given a binary matrix, find a subset of rows such that every column has exactly one 1. Algorithm X solves this recursively: pick a column, try each row that covers it, remove all conflicting rows and columns (the "cover" step), recurse, then backtrack.

DLX represents only the 1-entries as nodes in a doubly-linked grid—each node links left/right within its row and up/down within its column. The key insight: unlinking a node from a doubly-linked list does not erase its stored neighbor pointers. To undo the removal during backtracking, just re-link it—hence "dancing." The trick works only if you uncover in strict reverse order of covering (LIFO), because each uncover assumes the node's L/R/U/D pointers still point to valid neighbors.

cpp

void cover(int c) {
    R[L[c]] = R[c]; L[R[c]] = L[c];          // unlink column header
    for (int i = D[c]; i != c; i = D[i])      // each row in this column
        for (int j = R[i]; j != i; j = R[j])  // each node in this row
            D[U[j]] = D[j], U[D[j]] = U[j], sz[col[j]]--;
}

void uncover(int c) {
    for (int i = U[c]; i != c; i = U[i])      // REVERSE order (up, not down)
        for (int j = L[i]; j != i; j = L[j])  // REVERSE order (left, not right)
            D[U[j]] = j, U[D[j]] = j, sz[col[j]]++;
    R[L[c]] = c; L[R[c]] = c;                 // re-link column header
}

Small example—covering column B:

text

Matrix:           Columns:  A  B  C  D
  Row 0:                    1  0  0  1
  Row 1:                    0  1  1  0
  Row 2:                    1  1  0  1
  Row 3:                    0  1  0  0

Column B header links: B <-> Row1 <-> Row2 <-> Row3 (vertical DLL)

cover(B):
  1. Unlink B from column header list: A <-> C <-> D
  2. For Row 1 (has B=1): unlink all nodes in Row 1 from their columns
     -> C loses Row 1 from its vertical list
  3. For Row 2 (has B=1): unlink all nodes in Row 2
     -> A loses Row 2, D loses Row 2
  4. For Row 3 (has B=1): unlink all nodes in Row 3
     (Row 3 only has B, so no other columns affected)

After cover(B): remaining matrix is just Row 0 with columns A, C, D.

uncover(B): restores everything in reverse -- Row 3 first, then Row 2, then Row 1,
then re-link column B header. All pointers restored perfectly.

Full treatment in Linked Lists in Contests.

Gotchas

Dangling pointers after deletion. If you delete a node while another variable still points to it, you get undefined behavior. In doubly linked lists, always update both prev and next of neighbors before freeing.
Forgetting to update head/tail. Inserting at front? Update head. Deleting the last node? Update tail. These edge cases are the #1 source of segfaults in contest.
Memory leaks. With pool allocation this is a non-issue—you never free individual nodes. With new/delete in interviews, be careful.
Off-by-one in traversal. while (cur) visits all nodes including the last. while (cur->next) stops at the last node—useful when you need the predecessor of null. Know which one you need.
Using std::list when vector would be faster. Each node access is a potential cache miss. For $n < 10^{5}$ , a vector with $O (n)$ shifts often beats a list with $O (1)$ pointer ops due to hardware prefetching. Profile before committing.
Circular list: infinite loop on traversal. If you use a circular list, the loop condition must check for returning to the start node, not for null.

Mental Traps

Trap 1: "Linked lists are faster for insertion."

Only half true. $O (1)$ insert/delete requires already having a pointer to the node. If you need to find the insertion point first, that search is $O (n)$ —the same as shifting an array. (See the Find-Cost Trap diagram in Problem Patterns above.)

Trap 2: "I should use a linked list for remove-element problems."

Before reaching for a linked list, try lazy deletion: mark elements as deleted and skip them during iteration. Usually simpler and faster. (See Lazy Deletion above.)

Trap 3: "Asymptotic complexity is all that matters."

Cache misses dominate real performance. Each pointer dereference in a std::list can miss the L1/L2 cache, stalling the CPU for ~100 cycles. Arrays prefetch sequentially. (See the Memory Access Pattern diagram in Benchmarks above.)

LRU Cache Pattern

The canonical use case for a doubly linked list: pair it with a hash map. The list maintains access order; the map gives $O (1)$ lookup. On access, move the node to the front. On eviction, remove from the back.

Practice: LeetCode 146 (LRU Cache).

Contest Cheat Sheet

text

+----------------------------------------------------------+
| LINKED LIST CHEAT SHEET                                  |
|                                                          |
| Singly linked:                                           |
|   struct Node { int val, next; } pool[MAXN];             |
|   push_front: pool[nd].next = head; head = nd;           |
|   insert_after(p, v): rewire p->next                     |
|   delete: need predecessor (or copy trick)               |
|   reverse: three pointers (prev, cur, nxt)               |
|                                                          |
| Doubly linked:                                           |
|   int nxt[N], prv[N];                                    |
|   remove(x): nxt[prv[x]]=nxt[x]; prv[nxt[x]]=prv[x];   |
|   insert_after(x,y): 4 assignments                       |
|                                                          |
| Floyd's cycle detection:                                 |
|   slow = fast = head;                                    |
|   while(fast && fast->next)                              |
|     slow=slow->next; fast=fast->next->next;              |
|   if(slow==fast) -> cycle found                          |
|                                                          |
| When to use: frequent insert/delete at known positions,  |
|   splicing, DLX, LRU cache.                              |
| When NOT to use: random access, small n, cache matters.  |
+----------------------------------------------------------+

When NOT to Use This

Random access needed: If you ever index by position (a[k]), a linked list is wrong—use a vector or order-statistics tree.
Small n (< 10^4): Vector with O(n) shifts is faster due to cache locality.
Sorted collection: Use std::set or std::multiset—they give O(log n) insert + search.
Only push/pop at ends: Use std::deque—it's cache-friendlier.
Need to count elements in a range: Linked lists can't do range queries—use a Fenwick tree or segment tree.

Debug This

Find the bug in each snippet.

Bug 1: Doubly linked list deletion

cpp

void erase(int x) {
    nxt[prv[x]] = nxt[x];
    // prv[nxt[x]] = prv[x];  // BUG: this line is commented out!
}

Fix: Both pointer updates are required. Without the second line, backward traversal is broken—prv[nxt[x]] still points to the deleted node.

Bug 2: Inserting after node p

cpp

void insert_after(int p, int v) {
    int nd = new_node(v);
    nxt[nd] = nxt[p];
    prv[nd] = p;
    nxt[p] = nd;
    prv[nxt[nd]] = nd;  // BUG: nxt[p] was already changed!
}

Fix: The line nxt[p] = nd must come AFTER prv[nxt[p]] = nd. Or equivalently, save nxt[p] before modifying it. Correct order: set prv[nxt[p]] = nd, then nxt[p] = nd.

Bug 3: Pool reset between test cases

cpp

int pool_sz = 0;
void reset() {
    pool_sz = 0;
    // BUG: head and sentinel pointers are not reset!
}

Fix: Reset must also reinitialize head, tail (or sentinel nodes). Otherwise the first test case's sentinel pointers remain, pointing into stale pool positions.

Bug 4: Traversal of circular list

cpp

int cur = head;
while (cur != -1) {  // BUG: circular list never has -1!
    process(cur);
    cur = nxt[cur];
}

Fix: For circular lists, use do { ... cur = nxt[cur]; } while (cur != head); The termination condition must check for returning to the start node, not for a null sentinel.

Self-Test

Before moving on, make sure you can answer these without looking at the notes:

[ ] Given a singly linked list, reverse it iteratively using prev/cur/nxt. What happens if you forget to save nxt before overwriting cur->next?
[ ] Delete a node from a doubly linked list. How many pointer assignments are needed? What are the edge cases (head, tail, only node)?
[ ] Explain why std::list is almost always slower than std::vector in practice, even for insert-heavy workloads with small $n$ .
[ ] Implement Floyd's cycle detection. Why does resetting one pointer to head after the first meeting find the cycle entry?
[ ] Write an array-based linked list using nxt[] and prv[]. Insert a node after index $p$ , then remove index $q$ . Reset the pool between test cases.
[ ] You need to repeatedly remove arbitrary elements from a sequence. Compare three approaches: linked list, lazy deletion (boolean array), and std::set. When does each win?
[ ] What is the "copy trick" for deleting a node in a singly linked list without its predecessor? When does it fail?

Practice Problems

#	Problem	Source	Key Technique
1	Reverse Linked List	LeetCode 206	Three-pointer reverse
2	Linked List Cycle II	LeetCode 142	Floyd's algorithm
3	LRU Cache	LeetCode 146	Doubly linked list + hash map
4	Merge K Sorted Lists	LeetCode 23	Merge + priority queue
5	Josephus Problem I	CSES 2162	Circular list simulation
6	Josephus Problem II	CSES 2163	Indexed set or list trick
7	Copy List with Random Pointer	LeetCode 138	Node interleaving trick
8	CF 863E—Turn Off The TV	CF 863E	Coordinate compression + sweep (list-like)

Linked list problems are more common in interviews than in competitive programming. The CSES Josephus problems and CF problems involving permutation manipulation are the closest you will find to pure list problems in a contest setting.

Linked List Basics ​

Intuition ​

Visual Walkthrough ​

Invariants ​

What the Code Won't Teach You ​

When to Reach for This ​

C++ STL Reference ​

std::list<T>—Doubly Linked List ​

std::forward_list<T>—Singly Linked List ​

Implementation ​

Singly Linked List (Pointer-Based) ​

Reversing a Singly Linked List ​

Pointer-Based Doubly Linked List ​

Array-Based Linked List ​

Sentinel-Guarded Doubly Linked List ​

Floyd's Cycle Detection ​

Merge Two Sorted Lists ​

Operations Reference ​

Benchmarks ​

Problem Patterns & Tricks ​

Reversing a Linked List ​

Cycle Detection (Floyd's Algorithm) ​

Merging Two Sorted Lists ​

The Find-Cost Trap ​

Lazy Deletion—the Usual Contest Answer ​

Dancing Links (DLX) for Exact Cover ​

Gotchas ​

Mental Traps ​

LRU Cache Pattern ​

Contest Cheat Sheet ​

When NOT to Use This ​

Debug This ​

Self-Test ​

Practice Problems ​

Further Reading ​

Related Techniques ​

Linked List Basics

Intuition

Visual Walkthrough

Invariants

What the Code Won't Teach You

When to Reach for This

C++ STL Reference

`std::list<T>`—Doubly Linked List

`std::forward_list<T>`—Singly Linked List

Implementation

Singly Linked List (Pointer-Based)

Reversing a Singly Linked List

Pointer-Based Doubly Linked List

Array-Based Linked List

Sentinel-Guarded Doubly Linked List

Floyd's Cycle Detection

Merge Two Sorted Lists

Operations Reference

Benchmarks

Problem Patterns & Tricks

Reversing a Linked List

Cycle Detection (Floyd's Algorithm)

Merging Two Sorted Lists

The Find-Cost Trap

Lazy Deletion—the Usual Contest Answer

Dancing Links (DLX) for Exact Cover

Gotchas

Mental Traps

LRU Cache Pattern

Contest Cheat Sheet

When NOT to Use This

Debug This

Self-Test

Practice Problems

Further Reading

Related Techniques