Linked Lists in Contests

Contest linked-list problems are rarely about the container itself. They appear in three situations: neighbor relationships must be maintained under deletions, deletions need to be reflected immediately in $O(1)$, or the cleanest approach is to run the queries backwards and turn deletions into insertions.

Difficulty: Beginner | Prerequisites: Linked List Basics | CF Rating Range: 1400–2100

---

Intuition

You have six players standing in a line, identified by jersey numbers:

Position:  0    1    2    3    4    5
Value:    [3]  [7]  [1]  [9]  [5]  [8]

Players leave one at a time. After each departure you must report who was standing immediately to their left. Departure order: player 1 (pos 2), player 9 (pos 3), player 7 (pos 1), player 5 (pos 4).

Naive approach—mark-and-scan with a boolean array:

alive = [T, T, T, T, T, T]

Delete 1 (pos 2): alive[2] = F
  Left neighbor? Scan left from pos 1 ... alive -> 7.           (1 step)
  alive = [T, T, F, T, T, T]

Delete 9 (pos 3): alive[3] = F
  Left neighbor? Scan left from pos 2 ... dead.
                            pos 1 ... alive -> 7.               (2 steps)
  alive = [T, T, F, F, T, T]

Delete 7 (pos 1): alive[1] = F
  Left neighbor? Scan left from pos 0 ... alive -> 3.           (1 step)
  alive = [T, F, F, F, T, T]

Delete 5 (pos 4): alive[4] = F
  Left neighbor? Scan left from pos 3 ... dead.
                            pos 2 ... dead.
                            pos 1 ... dead.
                            pos 0 ... alive -> 3.               (4 steps)
  alive = [T, F, F, F, F, T]

Total scan steps: $1+2+1+4=$ 8 steps for just 4 deletions on 6 elements. As dead-element gaps grow, each scan gets longer. With $n={10}^5$ elements and $n$ deletions the worst case is $O(n^2)$—too slow for a 1-second limit.

The problem is not the deletions themselves. It is the repeated searching through positions that have already been proven dead.

If every node remembers its nearest surviving neighbors, deletion becomes pointer rewiring and neighbor lookups stay $O(1)$.

Think of a conga line. Each person has their hands on the shoulders of the person ahead, and the person behind grips theirs. When someone steps out, the person behind simply reaches forward and grabs the next person's shoulders. Nobody else moves. You always know exactly who is in front of you and behind you—no scanning required.

The mapping is direct: "hands on shoulders" = prev/next pointers, "step out" = delete node, "grab next person" = pointer rewiring. Where the analogy breaks: in a real conga line the departing person loses contact with the line, but in a linked list you can preserve the deleted node's old pointers—which is exactly what enables dancing links (cover/uncover) and backtracking undo.

Visual Walkthrough

Use the same 6 elements and the same 4 deletions, but now keep left (L) and right (R) pointer arrays so every step is just local rewiring.

Initial state:

  L[i]:  -    0    1    2    3    4
  R[i]:  1    2    3    4    5    -

         +----+    +----+    +----+    +----+    +----+    +----+
HEAD --> | 3  |--->| 7  |--->| 1  |--->| 9  |--->| 5  |--->| 8  |--> NULL
         +----+    +----+    +----+    +----+    +----+    +----+
         pos 0     pos 1     pos 2     pos 3     pos 4     pos 5

Step 1—Delete pos 2 (val 1): R[L[2]]=R[2], L[R[2]]=L[2] => R[1]=3, L[3]=1

Left neighbor = val[L[2]] = val[1] = 7. One pointer lookup.

         +----+    +----+               +----+    +----+    +----+
HEAD --> | 3  |--->| 7  |-------------->| 9  |--->| 5  |--->| 8  |--> NULL
         +----+    +----+               +----+    +----+    +----+
         pos 0     pos 1                pos 3     pos 4     pos 5

Step 2—Delete pos 3 (val 9): R[1]=4, L[4]=1

Left neighbor = val[L[3]] = val[1] = 7. One pointer lookup.

         +----+    +----+                         +----+    +----+
HEAD --> | 3  |--->| 7  |------------------------>| 5  |--->| 8  |--> NULL
         +----+    +----+                         +----+    +----+
         pos 0     pos 1                          pos 4     pos 5

Step 3—Delete pos 1 (val 7): R[0]=4, L[4]=0

Left neighbor = val[L[1]] = val[0] = 3. One pointer lookup.

         +----+                                   +----+    +----+
HEAD --> | 3  |---------------------------------->| 5  |--->| 8  |--> NULL
         +----+                                   +----+    +----+
         pos 0                                    pos 4     pos 5

Step 4—Delete pos 4 (val 5): R[0]=5, L[5]=0

Left neighbor = val[L[4]] = val[0] = 3. One pointer lookup.

         +----+                                              +----+
HEAD --> | 3  |--------------------------------------------->| 8  |--> NULL
         +----+                                              +----+
         pos 0                                               pos 5

Approach	Work per deletion	Total (4 deletions)	Scales to $n$ deletions
Mark-and-scan	up to $O(n)$ scan	8 scan steps	$O(n^2)$
Linked list	$O(1)$ pointer ops	4 lookups + 8 writes	$O(n)$

INVARIANT: For every surviving node x,
  L[x] = nearest surviving node to the left of x
  R[x] = nearest surviving node to the right of x

When we delete node d, executing R[L[d]] = R[d]; L[R[d]] = L[d]; makes L[d] and R[d]—both surviving—point to each other while skipping d. No other node's pointers change. Since L[d] was already the nearest survivor to the left (by the invariant before deletion), the invariant is preserved for all remaining nodes.

To see this in the walkthrough: after Step 2, node at pos 1 (val 7) has R[1] = 4 (val 5)—the nearest survivor to its right, correctly skipping the deleted positions 2 and 3.

Dancing-links bonus: because the deleted node's own L[d] and R[d] fields are never touched, you can restore it later with:

R[L[d]] = d;
L[R[d]] = d;

This only works in LIFO (stack) order—uncover the most-recently-covered node first. This is the foundation of Knuth's Algorithm X / DLX.

What the Code Won't Teach You

The linked list itself is rarely the whole answer. In contests, it is usually paired with a map, a reverse-processing trick, or a backtracking invariant that makes the pointer structure useful.

The hash map pairing pattern is the real contest skill.

The linked list alone gives $O(1)$ deletion at a known position. But contest problems give you a value to delete, not a position. The real skill is pairing a hash map (value → node) with a linked list (node → neighbors) so that value-based lookup and positional deletion are both $O(1)$.

  Hash Map                     Doubly Linked List
  +-----------+-------+
  | key: "A"  | idx 2 |--+     +---+    +---+    +---+    +---+
  | key: "B"  | idx 0 |--+---->| B |<-->| C |<-->| A |<-->| D |
  | key: "C"  | idx 1 |--+     +---+    +---+    +---+    +---+
  | key: "D"  | idx 3 |--+     idx 0    idx 1    idx 2    idx 3
  +-----------+-------+

  delete("A"):
    1. map["A"] -> idx 2            O(1) lookup
    2. unlink node 2 from list     O(1) pointer rewire
    3. erase map["A"]              O(1) hash erase

  Without the map:  O(n) scan + O(1) unlink = O(n)
  With the map:     O(1) + O(1) + O(1)      = O(1)

This pairing shows up in LRU cache, move-to-front problems, and many CF sequence-manipulation problems.

Reverse Offline — Deletions Become Insertions

When a problem says "process deletions in time order," consider reading the queries backwards. Deletions become insertions, and insertions into a doubly linked list are trivial once you know where to insert. This sidesteps the "I deleted something and now I need it back" headache entirely.

  Forward timeline (hard -- managing deletions):
  +-------------------------------------------------+
  | t=0    [1, 2, 3, 4, 5]    full sequence         |
  | t=1    [1, _, 3, 4, 5]    delete 2              |
  | t=2    [1, _, 3, _, 5]    delete 4              |
  | t=3    [1, _, _, _, 5]    delete 3              |
  +-------------------------------------------------+

  Reverse timeline (easy -- insertions only):
  +-------------------------------------------------+
  | t=3'   [1, _, _, _, 5]    start from final state|
  | t=2'   [1, _, 3, _, 5]    INSERT 3 (next to 1,5)|
  | t=1'   [1, _, 3, 4, 5]    INSERT 4 (next to 3,5)|
  | t=0'   [1, 2, 3, 4, 5]    INSERT 2 (next to 1,3)|
  +-------------------------------------------------+

  Each insertion is O(1). Collect answers in reverse, then reverse at the end.

Sentinels Kill Every Edge Case

Without sentinels, every deletion spawns two special cases: one for the head, one for the tail. Sentinels eliminate both. They are dummy nodes at each end that are never removed, so every real node always has valid L and R neighbors—no null checks, no branching.

  Without sentinels -- special cases for delete(x):
    if (x == head) head = R[x];     // special case 1
    else R[L[x]] = R[x];            // general left-link
    if (x == tail) tail = L[x];     // special case 2
    else L[R[x]] = L[x];            // general right-link

  With sentinels -- ONE case for ALL deletes:

    [SL] <--> [1] <--> [2] <--> [3] <--> ... <--> [n] <--> [SR]
    idx 0   idx 1  idx 2  idx 3          idx n  idx n+1

  Initialization for sequence 1..n:
    L[0] = 0;   R[0] = 1;              // left sentinel -> first real node
    for (int i = 1; i <= n; i++) {
        L[i] = i - 1;
        R[i] = i + 1;
    }
    L[n+1] = n;  R[n+1] = n+1;         // right sentinel <- last real node

  Delete(x): R[L[x]] = R[x];  L[R[x]] = L[x];
  // Always works. No if-statements. No null checks. No edge cases.

Linked List vs std::set — When to Use Which

The choice comes down to one question: do you need to search by value, or do you only need positional neighbors? std::set gives $O(\log n)$ insert/delete/find and $O(\log n)$ successor/predecessor. A linked list gives $O(1)$ delete/successor/predecessor but $O(n)$ find. The decision tree:

• Need sorted order + search by value? → std::set
• Need sequence order + delete by handle? → linked list
• Need both value lookup AND sequence manipulation? → hash map + linked list

When to Reach for This

Each of these is telling you the same thing: positional order matters, but you cannot afford to search.

Trigger phrases in problem statements:

• "find the next/previous element that hasn't been removed"
• "remove elements while maintaining neighbor relationships"
• "simulate removing every $k$-th element in a circle" (Josephus)
• "move an element to the front of a list in $O(1)$" (LRU / splice)
• "remove and later restore elements during backtracking" (dancing links)

Counter-examples—a linked list is NOT the answer:

• "insert and delete from a sorted sequence" → use std::set or balanced BST
• "find the $k$-th element in a dynamic sequence" → use order-statistics tree or BIT
• "need fast random access by index" → use array or vector; linked lists have $O(n)$ access

---

C++ STL Reference

Function / Class	Header	What it does	Time Complexity
std::list<T>	<list>	Doubly linked list	--
std::forward_list<T>	<forward_list>	Singly linked list (less overhead)	--
push_back(val)	<list>	Append to end	$O(1)$
push_front(val)	<list>	Prepend to front	$O(1)$
pop_back()	<list>	Remove last element	$O(1)$
pop_front()	<list>	Remove first element	$O(1)$
insert(it, val)	<list>	Insert before iterator it	$O(1)$
erase(it)	<list>	Remove element at iterator it; returns next iterator	$O(1)$
splice(pos, other)	<list>	Move all of other into *this before pos	$O(1)$
splice(pos, other, it)	<list>	Move single element it from other before pos	$O(1)$
splice(pos, other, first, last)	<list>	Move range [first, last) from other before pos	$O(1)$*
remove(val)	<list>	Remove all elements equal to val	$O(n)$
sort()	<list>	Merge sort (cannot use std::sort)	$O(n\log n)$
merge(other)	<list>	Merge two sorted lists	$O(n)$
reverse()	<list>	Reverse the list in-place	$O(n)$
unique()	<list>	Remove consecutive duplicates	$O(n)$

* splice with a range from the same list is $O(\text{distance})$ because it must update the size counter (since C++11). From a different list, it is $O(\text{distance})$ for the same reason.

std::forward_list differences: No push_back, size(), or reverse iterators. Use insert_after, erase_after, splice_after. Saves one pointer per node.

Critical: std::list iterators are not invalidated by insert/erase of other elements. Only the erased element's iterator is invalidated. This is the main advantage over vector.

---

Implementation

Minimal Array-Based Linked List (Contest Template)

This is what you actually use in contests. Heap allocation from std::list is slow; an array-based linked list (sometimes called a "static linked list") gives pointer-like behavior with array speed.

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

// Array-based doubly linked list -- O(1) insert/delete with handles
struct StaticList {
    static const int MAXN = 200005;
    int val[MAXN], prv[MAXN], nxt[MAXN];
    int head, tail, sz;

    void init() {
        // Sentinels: 0 = head sentinel, 1 = tail sentinel
        head = 0; tail = 1; sz = 0;
        nxt[head] = tail; prv[tail] = head;
        prv[head] = -1;   nxt[tail] = -1;
    }

    // Insert value v after node p, return new node index
    int insert_after(int p, int v) {
        int id = sz + 2;  // +2 because 0,1 are sentinels
        sz++;
        val[id] = v;
        nxt[id] = nxt[p]; prv[id] = p;
        prv[nxt[p]] = id; nxt[p] = id;
        return id;
    }

    void erase(int id) {
        nxt[prv[id]] = nxt[id];
        prv[nxt[id]] = prv[id];
    }

    void print() {
        for (int i = nxt[head]; i != tail; i = nxt[i])
            cout << val[i] << " ";
        cout << "\n";
    }
};

std::list with Splice (LRU Pattern)

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

int main() {
    // LRU Cache simulation using std::list + unordered_map
    // - list stores keys in usage order (front = most recent)
    // - map stores key -> iterator into the list for O(1) lookup

    int capacity = 3;
    list<int> usage;                              // front = MRU, back = LRU
    unordered_map<int, list<int>::iterator> pos;  // key -> iterator into list

    auto access = [&](int key) {
        if (pos.count(key)) {
            // Key exists: move it to front via splice
            // splice moves the element at pos[key] to the front of usage
            // This is O(1) -- no allocation, no copy, just pointer re-wiring
            usage.splice(usage.begin(), usage, pos[key]);
        } else {
            // Key is new: evict LRU if at capacity
            if ((int)usage.size() == capacity) {
                int evicted = usage.back();   // LRU key is at the back
                usage.pop_back();             // remove from list
                pos.erase(evicted);           // remove from map
            }
            // Insert new key at front (most recently used)
            usage.push_front(key);
            pos[key] = usage.begin();
        }
    };

    auto print_cache = [&]() {
        cout << "Cache (MRU->LRU): ";
        for (int k : usage) cout << k << " ";
        cout << "\n";
    };

    access(1); access(2); access(3);
    print_cache();  // Cache (MRU->LRU): 3 2 1

    access(2);      // 2 moves to front
    print_cache();  // Cache (MRU->LRU): 2 3 1

    access(4);      // 1 evicted, 4 added
    print_cache();  // Cache (MRU->LRU): 4 2 3
}

Dancing Links — Column Removal and Restoration

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

struct DLX {
    static const int MAXN = 100005;
    int L[MAXN], R[MAXN];  // left/right neighbours
    int n;

    void init(int _n) {
        n = _n;
        // Circular doubly linked list: 0..n-1
        for (int i = 0; i < n; i++) {
            L[i] = (i - 1 + n) % n;
            R[i] = (i + 1) % n;
        }
    }

    // "Cover" node i -- remove from list but keep its pointers intact
    void cover(int i) {
        R[L[i]] = R[i];
        L[R[i]] = L[i];
    }

    // "Uncover" node i -- restore it (LIFO order!)
    void uncover(int i) {
        R[L[i]] = i;
        L[R[i]] = i;
    }
};

int main() {
    DLX d;
    d.init(5);   // 0 <-> 1 <-> 2 <-> 3 <-> 4 (circular)

    d.cover(2);  // 0 <-> 1 <-> 3 <-> 4
    d.cover(0);  // 1 <-> 3 <-> 4

    // Restore in REVERSE order (critical for backtracking)
    d.uncover(0);
    d.uncover(2);

    int cur = 0;
    do {
        cout << cur << " ";
        cur = d.R[cur];
    } while (cur != 0);
    cout << "\n";  // 0 1 2 3 4
}

Josephus Problem — Circular Doubly Linked List Simulation

A complete solution for CSES Josephus Problem I using an array-based circular DLL. This $O(n^2)$ approach (with modulo optimization) is fine for $n\le 5000$. For Josephus II with $n\le 2\times {10}^5$, use an order-statistics tree—see Policy-Based DS—for $O(n\log n)$.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;

    // Circular doubly linked list: nodes 0..n-1 represent people 1..n
    vector<int> L(n), R(n);
    for (int i = 0; i < n; i++) {
        L[i] = (i - 1 + n) % n;
        R[i] = (i + 1) % n;
    }

    int cur = 0;
    int alive = n;
    for (int elim = 0; elim < n; elim++) {
        // cur counts as step 1, so advance k-1 more steps.
        // Modulo optimisation: skip full laps around the remaining circle.
        int steps = (k - 1) % alive;
        for (int j = 0; j < steps; j++)
            cur = R[cur];

        if (elim > 0) cout << ' ';
        cout << cur + 1;  // output 1-indexed

        // Remove cur and advance to the next survivor
        int nxt = R[cur];
        R[L[cur]] = R[cur];
        L[R[cur]] = L[cur];
        cur = nxt;
        alive--;
    }
    cout << '\n';
}

Complexity analysis:

• Each elimination advances at most alive - 1 steps after the modulo—total work across all eliminations is $O(n^2)$ worst case.
• For CSES Josephus I ($n\le 5000$): ${5000}^2=2.5\times {10}^7$—comfortably fast.
• For CSES Josephus II ($n\le 2\times {10}^5$): $4\times {10}^{10}$—too slow. Use an order-statistics tree (__gnu_pbds::tree) or a Fenwick tree with binary search for $O(n\log n)$. See Policy-Based DS.

Walkthrough ($n=5,k=3$):

Initial circle: 1 -> 2 -> 3 -> 4 -> 5 -> (1)
Start at person 1.

Elim 1: from 1, advance 2: 1->2->3. Eliminate 3.
  Circle: 1 <-> 2 <-> 4 <-> 5 <-> (1)       Output: 3
  cur = 4

Elim 2: from 4, advance 2: 4->5->1. Eliminate 1.
  Circle: 2 <-> 4 <-> 5 <-> (2)              Output: 3 1
  cur = 2

Elim 3: from 2, advance 2: 2->4->5. Eliminate 5.
  Circle: 2 <-> 4 <-> (2)                    Output: 3 1 5
  cur = 2

Elim 4: from 2, advance (2 % 2) = 0: stay at 2. Eliminate 2.
  Circle: 4 <-> (4)                           Output: 3 1 5 2
  cur = 4

Elim 5: from 4, advance (2 % 1) = 0: stay at 4. Eliminate 4.
  Output: 3 1 5 2 4

For Josephus I ($n\le 5000$), ${5000}^2=2.5\times {10}^7$—comfortably fast. For Josephus II ($n\le 2\times {10}^5$), $4\times {10}^{10}$ is far too slow; switch to an indexed set.

Full DLX — Algorithm X Exact Cover Solver

Worked example—4×4 exact cover matrix:

         C1  C2  C3  C4
   R1:    1   0   0   1     covers C1, C4
   R2:    0   1   1   0     covers C2, C3
   R3:    1   1   0   0     covers C1, C2
   R4:    0   1   0   1     covers C2, C4

   Solution: {R1, R2} -- R1 covers C1+C4, R2 covers C2+C3

2D structure (each * is a node, | = column links, <--> = row links):

  Header:  H --- C1 --- C2 --- C3 --- C4 --- H     circular left<->right
                  |       |       |       |
  R1:             *<------------------------->*     C1, C4
                  |       |       |       |
  R2:                     *<----->*                 C2, C3
                  |       |       |       |
  R3:             *<----->*                         C1, C2
                          |               |
  R4:                     *<------------>*          C2, C4
                  |       |       |       |
                 C1      C2      C3      C4         circular up<->down

  Column sizes: C1=2  C2=3  C3=1  C4=2

The recursion picks the column with the fewest 1s (MRV heuristic—minimum remaining values), tries each row that covers it, covers every column that chosen row also touches, and recurses. On failure it uncovers in exact reverse order.

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

struct DLX {
    static const int MAXN = 100005;
    int L[MAXN], R[MAXN], U[MAXN], D[MAXN];
    int col[MAXN];    // which column header owns this node
    int rowid[MAXN];  // which row this node belongs to
    int sz[MAXN];     // number of 1s in each column
    int head;         // master header node (index 0)
    int cnt;          // next free node index
    vector<int> ans;  // chosen row ids

    void init(int ncols) {
        head = 0;
        cnt = ncols + 1;
        // Build circular header row: H <-> C1 <-> C2 <-> ... <-> Cn <-> H
        for (int i = 0; i <= ncols; i++) {
            L[i] = i - 1; R[i] = i + 1;
            U[i] = D[i] = i;  // empty column points to itself
            sz[i] = 0; col[i] = i; rowid[i] = 0;
        }
        L[0] = ncols; R[ncols] = 0;
    }

    // Add a row with 1s in the given columns (1-indexed)
    void addRow(int r, const vector<int>& cols) {
        int first = -1;
        for (int c : cols) {
            int nd = cnt++;
            rowid[nd] = r;
            col[nd] = c;
            // Insert nd at the bottom of column c (above header)
            U[nd] = U[c]; D[nd] = c;
            D[U[c]] = nd; U[c] = nd;
            sz[c]++;
            if (first == -1) {
                first = nd;
                L[nd] = R[nd] = nd;
            } else {
                // Insert nd to the left of first (end of circular row)
                L[nd] = L[first]; R[nd] = first;
                R[L[first]] = nd; L[first] = nd;
            }
        }
    }

    // Remove column c and all rows that intersect it
    void cover(int c) {
        R[L[c]] = R[c]; L[R[c]] = L[c];
        for (int i = D[c]; i != c; i = D[i])
            for (int j = R[i]; j != i; j = R[j]) {
                U[D[j]] = U[j]; D[U[j]] = D[j];
                sz[col[j]]--;
            }
    }

    // Restore column c (MUST be called in LIFO order w.r.t. cover)
    void uncover(int c) {
        for (int i = U[c]; i != c; i = U[i])
            for (int j = L[i]; j != i; j = L[j]) {
                sz[col[j]]++;
                U[D[j]] = j; D[U[j]] = j;
            }
        R[L[c]] = c; L[R[c]] = c;
    }

    bool search() {
        if (R[head] == head) return true;  // all columns covered

        // MRV heuristic: pick column with fewest remaining 1s
        int best = R[head];
        for (int c = R[best]; c != head; c = R[c])
            if (sz[c] < sz[best]) best = c;

        if (sz[best] == 0) return false;   // dead end: empty column

        cover(best);
        for (int i = D[best]; i != best; i = D[i]) {
            ans.push_back(rowid[i]);
            for (int j = R[i]; j != i; j = R[j])
                cover(col[j]);

            if (search()) return true;

            // Backtrack: uncover in reverse order
            for (int j = L[i]; j != i; j = L[j])
                uncover(col[j]);
            ans.pop_back();
        }
        uncover(best);
        return false;
    }
};

int main() {
    //      C1  C2  C3  C4
    // R1:   1   0   0   1
    // R2:   0   1   1   0
    // R3:   1   1   0   0
    // R4:   0   1   0   1
    // Solution: {R1, R2}

    DLX dlx;
    dlx.init(4);
    dlx.addRow(1, {1, 4});
    dlx.addRow(2, {2, 3});
    dlx.addRow(3, {1, 2});
    dlx.addRow(4, {2, 4});

    if (dlx.search()) {
        sort(dlx.ans.begin(), dlx.ans.end());
        cout << "Solution rows:";
        for (int r : dlx.ans) cout << " R" << r;
        cout << "\n";  // Output: Solution rows: R1 R2
    } else {
        cout << "No solution\n";
    }
}

Step by step on the example:

1. MRV picks C3 (size 1—only one row covers C3, so we must use it).
2. Cover C3. The only row in C3 is R2. When covering C3, we also remove R2's other node (in C2) from C2's column: $\text{sz}[C2]$ drops from 3 to 2.
3. Choose R2. Add R2 to solution. Cover all other columns R2 touches → cover C2. Covering C2 removes rows R3 and R4 (they intersect C2), which also removes R3's node from C1 and R4's node from C4.
4. Remaining columns: C1 (size 1: only R1 left) and C4 (size 1: only R1 left).
5. MRV picks C1. Choose R1. Cover C4. All columns covered → $R[\text{head}]=\text{head}$.
6. Solution found: $\{R1,R2\}$. R1 covers C1+C4, R2 covers C2+C3. (Correct.)

Applications: Sudoku, N-Queens, pentomino tiling, Latin squares—any problem expressible as "choose subsets that cover every constraint exactly once."

Text-Editor Cursor with std::list

A cursor into a std::list<char> is just an iterator. The key insight is that list iterators survive insert/erase of other elements—only the erased element's own iterator is invalidated—which is exactly what makes cursor patterns work.

list<char> doc;
auto cursor = doc.end();  // cursor "before" this iterator
// insert:      doc.insert(cursor, ch);
// delete left: if (cursor != doc.begin()) cursor = doc.erase(prev(cursor));
// move left:   if (cursor != doc.begin()) --cursor;
// move right:  if (cursor != doc.end())   ++cursor;

std::list STL Reference

Function	Time	Notes
push_back(val) / push_front(val)	$O(1)$
pop_back() / pop_front()	$O(1)$
insert(it, val)	$O(1)$	Before iterator
erase(it)	$O(1)$	Returns next iterator
splice(pos, other)	$O(1)$	Move all of other before pos
splice(pos, other, it)	$O(1)$	Move one element
splice(pos, other, first, last)	$O(\text{dist})$*	Range version
remove(val)	$O(n)$	Remove all equal
sort()	$O(n\log n)$	Member—std::sort won't work
merge(other)	$O(n)$	Merge two sorted lists
reverse()	$O(n)$

* Since C++11, range splice from the same list counts elements to update size(). For $O(1)$ range splice inside the same list, use an array-based linked list.

std::forward_list is singly linked—no push_back, no size(), uses insert_after / erase_after / splice_after. Saves one pointer per node but loses more functionality than it gains in contests.

Complexity Comparison

Operation	std::list	Array-based LL	std::vector
Access by index	$O(n)$	$O(n)$	$O(1)$
Insert at front	$O(1)$	$O(1)$	$O(n)$
Insert at back	$O(1)$	$O(1)$	amortized $O(1)$
Insert at known position	$O(1)$	$O(1)$	$O(n)$
Delete at known position	$O(1)$	$O(1)$	$O(n)$
Find by value	$O(n)$	$O(n)$	$O(n)$
Splice (single element)	$O(1)$	N/A	$O(n)$
Sort	$O(n\log n)$	N/A	$O(n\log n)$
Memory per element	~48 bytes	~12 bytes (3 ints)	~4 bytes
Cache locality	Poor	Good	Excellent

At $n={10}^6$, std::list<int> uses ~48 MB while the array-based version uses ~12 MB and std::vector<int> uses ~4 MB. Combined with better cache behavior, array-based linked lists are 3–5× faster in practice for the same algorithmic complexity. std::list nearly hits the typical 256 MB memory limit at that scale, while the array-based version uses a quarter of that.

Structure	Per-element	$n={10}^5$ total	$n={10}^6$ total
std::list<int>	~48 bytes	~4.8 MB	~48 MB
Array-based LL (3 arrays)	~12 bytes	~1.2 MB	~12 MB
std::vector<int>	~4 bytes	~0.4 MB	~4 MB

---

Problem Patterns

Ordered Deletion (Dancing Links)

Elements are removed one at a time and you must always know who their nearest surviving neighbors are. The two-line rewire makes each deletion $O(1)$ and leaves the deleted node's own pointers intact for optional restoration.

// Initialize circular doubly linked list
int L[MAXN], R[MAXN];
for (int i = 0; i < n; i++) L[i] = i-1, R[i] = i+1;
L[0] = n-1; R[n-1] = 0; // circular

// Remove element i
R[L[i]] = R[i];
L[R[i]] = L[i];

Problems: CF 1154E, CF 1367F2

LRU / Move-to-Front

The list is kept in recency order—most recently accessed at the front, least recently accessed at the back. On access, splice the element to the front in $O(1)$. On eviction, pop the back. The hash map provides the iterator; the list provides the $O(1)$ reorder.

list<int> order;
unordered_map<int, list<int>::iterator> pos;
// Move key to front:
order.splice(order.begin(), order, pos[key]);

Problems: LC 146 (LRU Cache), CF 1288E

Josephus Elimination

$n$ people in a circle, every $k$-th person is eliminated. Simulate with a circular linked list. For pure Josephus ($k$ fixed), use the $O(n)$ recurrence instead: $J(n,k)=(J(n-1,k)+k)modn$.

// Simulation when k varies or extra logic is needed
int L[MAXN], R[MAXN];
// ... init circular list ...
int cur = 0;
for (int elim = 0; elim < n; elim++) {
    for (int step = 1; step < k; step++) cur = R[cur];
    cout << cur << " ";
    R[L[cur]] = R[cur];
    L[R[cur]] = L[cur];
    cur = R[cur];
}

Problems: CF 1535D, CSES Josephus Problem I

List Merging / Splitting

When two sorted sequences must be merged, or a sequence split at a given position, std::list::merge and std::list::splice rewire pointers without any copying.

list<int> a = {1, 3, 5}, b = {2, 4, 6};
a.merge(b); // a = {1,2,3,4,5,6}, b is empty, O(n)

Problems: CF 863D

Simulating a Text Editor Cursor

Insert at the cursor, delete at the cursor, move left and right. A doubly linked list gives $O(1)$ for all four operations because iterator validity is maintained across edits.

// Use two stacks (simpler) or a list with an iterator as cursor
list<char> doc;
auto cursor = doc.end(); // cursor points to char AFTER cursor position
// Insert: doc.insert(cursor, ch);
// Delete: if (cursor != doc.begin()) cursor = doc.erase(prev(cursor));
// Move left: if (cursor != doc.begin()) --cursor;
// Move right: if (cursor != doc.end()) ++cursor;

Problems: CF 675A, SPOJ EDIST

Undo/Redo with Cover/Uncover

Backtracking search that removes and restores elements. The "dancing links" trick: removed nodes keep their old pointers, so restoration is $O(1)$ if done in LIFO order.

Problems: CF 1conflict (see DLX tutorial on CF)

---

Contest Cheat Sheet

+----------------------------------------------------------+
|             LINKED LIST -- CONTEST CHEAT SHEET            |
+----------------------------------------------------------+
| WHEN TO USE:                                             |
|   - O(1) insert/delete at KNOWN position (have handle)   |
|   - Splice: move sublist between lists in O(1)           |
|   - Dancing links: cover/uncover for backtracking        |
|   - Almost NEVER. Try vector/set/deque first.            |
+----------------------------------------------------------+
| ARRAY-BASED LL (preferred in contests):                  |
|   int L[N], R[N];                                        |
|   Remove i:  R[L[i]] = R[i]; L[R[i]] = L[i];           |
|   Restore i: R[L[i]] = i;    L[R[i]] = i;   (LIFO!)    |
+----------------------------------------------------------+
| STL QUICK REF:                                           |
|   list<T> L;                                             |
|   L.splice(pos, other, it);  // move *it to before pos  |
|   auto it = L.insert(pos, val); // insert before pos    |
|   it = L.erase(it);         // erase, get next iterator |
+----------------------------------------------------------+
| COMPLEXITY:                                              |
|   Insert/Delete at iterator: O(1)                        |
|   Access by index: O(n) -- no random access!              |
|   splice (single element): O(1)                          |
|   Memory: ~48 bytes/node (list) vs ~12 bytes (array LL)  |
+----------------------------------------------------------+
| RULE OF THUMB: if n < 10^5, vector + shift is faster     |
+----------------------------------------------------------+

---

Common Mistakes and Debugging

Iterator invalidation—the sneaky one. std::list iterators survive insert/erase of other elements, but std::vector iterators do NOT. If you switch from list to vector (or vice versa), all your iterator logic breaks. When using erase, always capture the return value:

it = mylist.erase(it); // correct
// mylist.erase(it); ++it; // UNDEFINED BEHAVIOR

Vector beats list in practice. For $n\le {10}^5$, a vector with $O(n)$ insert/erase is faster than list with $O(1)$ insert/erase due to cache locality. The crossover point where list actually wins is surprisingly high. Profile before committing to std::list.

std::forward_list has no size(). Calling distance(fl.begin(), fl.end()) is $O(n)$. Track size manually if you need it.

No random access—std::advance is $O(n)$. *next(L.begin(), k) compiles and looks like $O(1)$, but it is $O(k)$. This is a common source of TLE when people treat list iterators like array indices.

Splice from same list updates size in $O(\text{distance})$. Since C++11, splice(pos, *this, first, last) (same list) must count elements to update size. If you need $O(1)$ splice within the same list, use an array-based linked list.

Forgetting LIFO order for dancing links. Cover/uncover (remove/restore) MUST be done in stack order. If you cover A then B, you must uncover B then A. Violating this corrupts the list.

Memory overhead. std::list<int> uses ~40–48 bytes per element (value + two pointers + allocator overhead) vs 4 bytes for a vector. For $n={10}^6$, that is ~48 MB vs ~4 MB. Watch the memory limit.

Sorting a list. You cannot use std::sort(L.begin(), L.end())—it requires random-access iterators. Use L.sort() (member function, merge sort, $O(n\log n)$).

Mental Traps

Trap 1: "Linked lists give fast deletion"—only if you already have a pointer.

A linked list deletion is $O(1)$ given a pointer to the node. But if you only have a value, you must first find the node—and that's $O(n)$. Without a companion structure (hash map, direct-index array), you've traded one $O(n)$ for another.

  [X] O(n) scan-then-delete path:
  +-----------------------------------------------------+
  | Want to delete value "7"                             |
  |                                                      |
  | [3] -> [5] -> [1] -> [7] -> [9] -> [4]              |
  |  ^      ^      ^      ^                              |
  | scan   scan   scan   FOUND -> unlink O(1)            |
  |                                                      |
  | Total: O(n) scan + O(1) unlink = O(n)                |
  +-----------------------------------------------------+

  [OK] O(1) delete path (with hash map handle):
  +-----------------------------------------------------+
  | Want to delete value "7"                             |
  |                                                      |
  | map["7"] -> node ptr --> [7] -> unlink O(1)          |
  |                                                      |
  | Total: O(1) lookup + O(1) unlink = O(1)              |
  +-----------------------------------------------------+

Trap 2: "Linked list problems are unusual in contests"—they appear more than you think.

Linked lists show up disguised in many problem types:

• Simulation: card games, queue operations, round-robin elimination
• Text editors: cursor movement, insert/delete at cursor (CF 675A)
• Sequence manipulation: move-to-front, splice sublists, ordered removal
• Backtracking: dancing links / Algorithm X for exact cover problems

The data structure is rarely named. Look for the operations—$O(1)$ delete at a known position, immediate neighbor queries—not the word "list."

Trap 3: "I'll just use std::list"—array-based lists are almost always better in contests.

std::list has high constant factors (~48 bytes/node, poor cache locality, allocator overhead). An array-based linked list (nxt[], prv[]) uses ~12 bytes/node, lives in contiguous memory, and is faster in practice for $n\le {10}^6$. The only time std::list wins is when you need splice across different lists.

---

Self-Test

Can you answer each of these from memory?

• [ ] Given a value (not a position), explain how to achieve $O(1)$ deletion from a linked list. What companion structure do you need?
• [ ] Write the two-line delete operation for an array-based doubly linked list from memory: R[L[i]] = ... and L[R[i]] = ...
• [ ] Explain why sentinel nodes eliminate all edge cases in insert/delete. What values do L[0] and R[n+1] hold?
• [ ] When would you choose std::set over a linked list? When would you choose the reverse?
• [ ] Describe the reverse offline trick: how does processing deletions backwards turn them into insertions?
• [ ] What is the LIFO constraint on dancing links cover/uncover, and what breaks if you violate it?
• [ ] For $n={10}^5$ elements, estimate the memory usage of std::list<int> vs an array-based linked list vs std::vector<int>.

---

Practice Problems

#	Problem	Source	Difficulty	Key Idea
1	Remove Linked List Elements	LeetCode 203	Easy	Basic deletion
2	Josephus Problem I	CSES	Easy	Circular elimination
3	Josephus Problem II	CSES	Medium	Josephus with indexed set (compare LL approach)
4	LRU Cache	LeetCode 146	Medium	list + hashmap splice pattern
5	Two Teams	CF 1154E	1500	Dancing-links deletion
6	Linova and Kingdom	CF 1336A	1600	Greedy with ordered removal
7	Flying Sort	CF 1367F2	2100	Subsequence manipulation
8	Messenger Simulator	CF 1288E	2000	Move-to-front queries
9	Dancing Links (Algorithm X)	SPOJ	Hard	Full DLX implementation

When NOT to Use This

• Need sorted order: Use Set & Multiset—linked lists have no ordering guarantees
• Random access by index: Use array or Policy-Based DS for $O(\log n)$ k-th element
• Range sum/min/max queries: Use Fenwick Tree or Segment Tree
• Small n ($<{10}^4$): Vector shifts are faster due to cache locality
• No handle to the node: Without a hash map or direct index, finding the node costs $O(n)$, negating the $O(1)$ delete

---

Debug This

Find the bug in each snippet.

Bug 1: Circular list initialization

for (int i = 0; i < n; i++) {
    L[i] = i - 1;
    R[i] = i + 1;
}
// BUG: L[0] = -1 and R[n-1] = n, not circular!

Fix: Add L[0] = n - 1; R[n - 1] = 0; to close the circle.

Bug 2: Dancing links uncover in wrong order

// Covered columns A, then B
cover(A);
cover(B);
// Later...
uncover(A);  // BUG: should uncover B first!
uncover(B);

Fix: Uncover must be LIFO: uncover(B); uncover(A);. Uncovering A first corrupts B's restoration because A's uncover may modify nodes that B's pointers reference.

Bug 3: Josephus simulation off-by-one

int cur = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < k; j++)  // BUG: should be k-1 steps!
        cur = R[cur];
    cout << cur << " ";
    R[L[cur]] = R[cur];
    L[R[cur]] = L[cur];
    cur = R[cur];
}

Fix: The current person counts as step 1, so advance k-1 times, not k times. Use for (int j = 1; j < k; j++).

Bug 4: Deletion without updating cur pointer

void remove_and_advance(int& cur) {
    R[L[cur]] = R[cur];
    L[R[cur]] = L[cur];
    // BUG: cur still points to the deleted node!
}

Fix: After deletion, advance cur: int next = R[cur]; R[L[cur]] = R[cur]; L[R[cur]] = L[cur]; cur = next;

---

Further Reading

• cp-algorithms: Linked Lists—limited coverage; linked lists are rarely a standalone topic
• Knuth's Dancing Links paper (arXiv)—the definitive DLX reference
• CF Blog: Dancing Links Tutorial—practical DLX for competitive programming
• CF Blog: Why you should avoid linked lists—benchmark data showing vector dominance
• C++ Reference: std::list—complete API reference
• See: Arrays and Strings for the data structure you should probably use instead
• See also: Stack, Queue, Deque for simpler sequential containers to try before reaching for a linked list
• See also: Data Structure Selection Guide for choosing the right structure under contest pressure

Next Up: Monotonic Stack—using stack discipline to answer "next greater element" queries in $O(n)$.