Cairn
data structures · concurrency · O(n) time per insert/delete/find (traversal-dominated), O(n) space, lock-free (not wait-free, not starvation-free)

↩ back to Concurrency

Harris Linked List

The Treiber Stack races one CAS'd pointer; the Michael-Scott Queue races two. A linked list with inserts and deletes anywhere in the middle is a different kind of hard: the node a thread wants to delete can be the exact node another thread's insert is trying to attach itself to, at the exact same instant. Hazard Pointers and Epoch-Based Reclamation both close a real gap on this site, but neither defines a structure of its own — both retry the Treiber Stack's own pop loop with extra bookkeeping layered on top. This page is the first genuinely new CAS-based shape since the queue: Tim Harris published the standard lock-free linked list in 2001, and its one new idea has no analogue on either earlier page — mark a node as logically deleted before anyone physically unlinks it, so a concurrent insert that was mid-flight against that exact node fails cleanly instead of silently vanishing.

Same measure-don't-assume discipline as this site's other ten Concurrency pages: every claim below — that skipping the mark step loses a real insert, and marking first closes it completely — comes from exhaustively searching every reachable interleaving of a small state machine, not a handful of hand-picked traces.

Try it

Pick a scenario and a delete variant — Correct (mark before unlinking) is Harris's real algorithm; Naive (unlink directly, no mark) skips the one step that makes it work — then either step through by hand with Step T0 / Step T1, or press Explore all schedules to search every reachable interleaving at once. Try the Minimal (T0: insert X after B · T1: delete B) scenario with the Naive variant first — it loses the insert in as little as 4 moves. Switch to Correct with the same scenario and the loss vanishes completely, at every one of the same states.

Pick a scenario and delete variant, then step each thread by hand.

Why it works

The list is a singly-linked chain with a permanent dummy head, same convention as the Michael-Scott Queue: real values live after it. Every node's next field is really a pair, { ref, marked }, swapped together by one CAS — real lock-free implementations pack both into a single machine word (the mark is one bit stolen from the pointer) for exactly this reason, so hardware CAS can check and set both atomically. insert(pred, value) reads pred.next, then tries CAS(pred.next, predNext, { ref: newNode, marked: false }) — it only succeeds if pred.next is still exactly what was just read, which means pred wasn't marked and nothing else linked in ahead of this insert. If that comparison fails for any reason, the insert hasn't corrupted anything; it just hasn't happened yet, and a real implementation retries from a fresh traversal.

delete(pred, target) is where the new idea lives. The naive approach — read target.next, then CAS(pred.next, target, targetNext) to splice target straight out — looks identical in shape to the queue's own dequeue, but has a hazard the queue's two-pointer design never creates: target itself can still be in the middle of someone else's insert at the moment this CAS fires. If an insert already linked a new node onto target.next after this delete did its read but before its CAS, the delete's CAS still succeeds — pred.next still equals target, untouched — but it overwrites pred.next with the stale value it read earlier, severing the chain right before the new node instead of right after target. The new node, and everything a real list might have chained after it, is gone — not freed, not corrupted, just unreachable from pred onward, even though its own insert CAS reported success.

Harris's fix closes exactly that gap: before touching pred at all, delete first tries CAS(target.next, targetNext, { ref: targetNext.ref, marked: true }) — flip the mark bit on target's own next field, changing nothing about reachability yet. If an insert already linked a new node onto target.next, this CAS's own comparison fails (the value isn't targetNext anymore) and delete simply rereads and retries the mark against whatever is there now — which means by the time the mark finally succeeds, it has captured whatever the real, current next node is, insert or no insert. Only then does delete attempt CAS(pred.next, target, thatCapturedNext), using a value that's provably not stale. Nothing about this needs pred to be touched twice, and nothing about it needs the insert to know delete exists — the mark alone is enough to make the two operations fail safely against each other instead of silently corrupting the chain.

Reference implementation

Pseudocode compareAndSwap(ref, expected, next) stands for the real hardware primitive, same as this site's other CAS-based pages: atomically check whether ref still equals expected, and if so set it to next, reporting success or failure as one indivisible step. pred/target below are passed in already found by a traversal from the head — this page's demo fixes them per scenario to isolate the delete-vs-insert race itself, the same simplification the Treiber Stack and Michael-Scott Queue's own demos make for push/pop and enqueue/dequeue.

function insert(pred, value) {
  while (true) {
    const predNext = pred.next;                 // { ref, marked }
    const node = { value: value, next: { ref: predNext.ref, marked: false } };
    if (compareAndSwap(pred, 'next', predNext, { ref: node, marked: false })) return OK;
    // else retry: pred changed (marked for deletion, or another insert landed first)
  }
}

function deleteCorrect(pred, target) {
  let targetNext;
  while (true) {
    targetNext = target.next;
    if (targetNext.marked) return ALREADY_DELETED;
    // mark first — captures whatever target.next really is right now
    if (compareAndSwap(target, 'next', targetNext, { ref: targetNext.ref, marked: true })) break;
    // else retry: someone inserted after target since the last read — reread and remark
  }
  // best-effort unlink using the value captured at the moment marking succeeded, never stale
  compareAndSwap(pred, 'next', { ref: target, marked: false }, { ref: targetNext.ref, marked: false });
}

function deleteNaive(pred, target) {               // the one-line "simplification"
  while (true) {
    const targetNext = target.next;
    if (compareAndSwap(pred, 'next', { ref: target, marked: false }, { ref: targetNext.ref, marked: false })) return OK;
    // else retry
  }
}

The demo above runs this exact shape as a step-by-step state machine, with every read, every local computation, and every CAS as its own independently interleavable move. The Naive variant changes exactly one thing: it deletes straight from deleteNaive's read-then-unlink shape, with no mark step and no retry-on-mark-failure at all.

Pitfalls

The correct algorithm never loses an insert — exhaustively confirmed, 0 occurrences across every scenario tried, including ones that race an insert against a delete on purpose. The naive variant does, and the shortest reproducing schedule needs only two threads doing one operation each:

scenariodelete variantreachable stateslost-insert statesshortest schedule
T0: insert X after B · T1: delete BCorrect190—
T0: insert X after B · T1: delete BNaive1214 moves
T0: insert X after B · T1: delete B, delete DCorrect370—
T0: insert X after B · T1: delete B, delete DNaive2234 moves
T0: delete B · T1: delete D (no insert in flight)Correct160—
T0: delete B · T1: delete D (no insert in flight)Naive90—

The minimal reproduction (Minimal scenario, Naive variant, starting chain head → A → B → C): T1 calls deleteNaive(A, B) and reads targetNext = B.next = { ref: C, marked: false } — then stalls, before its CAS. T0 now calls insert(B, 'X'): reads predNext = B.next (still { ref: C, marked: false }, T1 hasn't written anything yet) and succeeds its own CAS, B.next = { ref: X, marked: false } — the chain is now head → A → B → X → C, fully intact, X's own insert reporting success. T1 resumes and fires its CAS: CAS(A.next, B, targetNext.ref) — compares A.next against B, still true (B hasn't been removed yet), so it succeeds, setting A.next = C using the stale targetNext.ref read before X existed. The chain is now head → A → C: B is correctly gone, but X — a fully successful, completed insert — is gone with it, unreachable from the head. Four moves total: T1's read, T0's read, T0's CAS, T1's CAS. The correct variant, given the identical schedule up to T0's insert succeeding, takes a different path at T1's mark attempt: CAS(B.next, { ref: C, marked: false }, { ref: C, marked: true }) compares against B.next's current value, which is now { ref: X, marked: false }, not what T1 read earlier — the mark CAS fails, forcing T1 to reread (targetNext.ref is now X) and remark against that. Its eventual unlink CAS then uses X, not C, giving head → A → X → C. X survives.

Two things worth being precise about, the same way the Michael-Scott Queue's own page is about its phantom-empty bug. First, the lost insert isn't a crash or a dangling reference — confirmed separately by tracking every node ever inserted against every node still reachable from the head at every fully-finished state reachable in either buggy scenario above: X is a perfectly well-formed node, its own next field intact, simply never looked at again by anyone walking the list from the head. Second, the Delete only sanity scenario — two threads each deleting a different, unrelated node, no insert anywhere in the trace — comes back with 0 lost-insert states under either variant: there's nothing for a stale read to go stale against when nobody is inserting. The bug needs a genuine race between an insert and a delete that shares the exact same target node to ever surface.

This structure's CAS'd pointers face the identical ABA hazard the Treiber Stack's own page demonstrates exhaustively once node identities can be recycled — nothing about that mechanism is re-derived here. What is new is that the physically-unlinked node this page's delete produces is exactly the kind of "popped but maybe still referenced elsewhere" node Hazard Pointers and Epoch-Based Reclamation already exist to reclaim safely — neither page is specific to a stack, and a real implementation of this list would reach for one of them before actually freeing a deleted node's memory, the same way it would for the Treiber Stack.

Complexity

Time: every one of this page's own demo moves (read, mark CAS, unlink CAS) is O(1), with no bound on retries under contention — the same lock-free guarantee as the Treiber Stack and Michael-Scott Queue. But unlike either of those, insert and delete here first need to find pred and target by walking the chain from the head, which this page's demo deliberately skips to isolate the marking race — a real implementation pays O(n) for that traversal on every single operation, the one cost a dedicated head/tail pointer lets the stack and the queue avoid entirely. Space: O(n) for n live elements plus the one permanent dummy node, same shape as the queue. Six of this site's other Concurrency pages built on ordinary reads and writes all guarantee bounded waiting (see the Safety vs. Liveness guide); this page, the Treiber Stack, the Michael-Scott Queue, Hazard Pointers, and Epoch-Based Reclamation all give that up in exchange for never blocking anything, a trade Busy-Waiting vs. Blocking measures the cost of directly — the same CAS-vs-spinlock tradeoff the Michael-Scott Queue's own Complexity section measures isn't re-derived separately here, since nothing about compare-and-swap's cost under contention changes just because the structure being raced over is a list instead of a stack or a queue.