Common Operations and Complexity

Why an Operations Catalogue Matters

We have built singly, doubly, and circular linked lists in the previous four sections. Now we step back and ask the question every working engineer eventually asks: given a problem, will a linked list run fast enough? The answer comes in two parts, and a serious treatment must include both.

1. Asymptotic cost — the Big-O behavior as $n \to \infty$. This is what tells you that delete-head is constant time and access by index is linear, regardless of language or machine.
2. Real wall-clock cost — what the CPU actually does. Linked lists pay a hidden price (cache misses, allocator pressure, branch mispredictions) that is invisible to Big-O but very visible on a profiler. Sometimes a linear-time array scan beats a constant-time linked-list operation in practice, and you must know when.

Senior's rule of thumb: Big-O tells you how the algorithm scales. The constant factor tells you whether your users will notice. Linked lists have excellent Big-O for some operations and terrible constants for almost everything. Both facts matter.

The Master Complexity Table

Here is the canonical reference. Memorize the singly-linked column; the rest follow from symmetry. All times are worst case unless noted; $n$ is the list length, $k$ is an index.

Asymptotic Cost vs Real Performance

Big-O hides a multiplicative constant that, on modern hardware, can be the difference between a snappy app and a sluggish one. The dominant cost in a linked-list traversal is not the comparison or the pointer dereference; it is the cache miss.

The cache-miss penalty

Linked-list nodes are typically allocated independently on the heap, so consecutive nodes can land anywhere in physical memory. Walking the list is a sequence of essentially-random memory accesses — the CPU's prefetcher cannot predict what comes next, so each node = node.next can stall the pipeline waiting on RAM.

A concrete benchmark

On an x86-64 laptop circa 2024, summing an array of 1,000,000 32-bit ints takes about 1 ms (the prefetcher streams cache lines perfectly). Summing an equivalent std::list<int> of the same length takes 10–50 ms. The asymptotic complexity is identical — $O(n)$ for both — but the wall-clock difference is 10× to 50×.

Anatomy of Each Operation

1. Access by index — O(n), unavoidable

There is no $t[k]$ shortcut. We start at head and follow next exactly $k$ times. Doubly linked lists with a tail pointer can choose the closer end: cost becomes $O(\min(k,\, n-k))$.

2. Prepend — O(1), the linked list's superpower

Three writes: allocate node, node.next = head, head = node. Compare with a dynamic array's prepend, which must shift every existing element right.

3. Append — O(1) with tail, O(n) without

Without a tail pointer we must walk to the end. This is the most common production bug: a beginner builds a list with $n$ appends and accidentally pays $O(n^2)$. With a tail pointer, append is symmetric to prepend.

4. Insert after a known node — O(1)

If you already hold a pointer to the predecessor, you rewire two next-fields and you are done. This is the operation that makes intrusive linked lists popular in OS kernels: handlers receive a node pointer directly, skip the find phase, and unlink in constant time.

5. Insert before a known node — O(n) singly, O(1) doubly

Singly: you have node but not node.prev, so you walk from head until you find the predecessor. Doubly: node.prev is already there.

6. Delete head / delete tail

• Delete head: head = head.next. Always $O(1)$.
• Delete tail (singly): even with a tail pointer we must find the second-to-last node by walking from head. $O(n)$.
• Delete tail (doubly): tail = tail.prev; tail.next = null. $O(1)$.

7. Delete given a node pointer — the canonical doubly-linked win

Doubly linked: node.prev.next = node.next; node.next.prev = node.prev. $O(1)$. Singly linked: must walk to find the predecessor. $O(n)$. This single operation is why every production LRU cache uses a doubly linked list.

8. Reverse — O(n), constant extra space

Walk the list flipping each next pointer in place. Three local variables (prev, curr, nxt) and one pass. Far more memory-efficient than building a reversed copy.

9. Length — O(n) by default, O(1) if cached

A bare linked list does not know its own length; counting requires a full traversal. Production implementations cache size as a field and update it on insert/delete — $O(1)$ queries, no extra asymptotic cost.

10. Concatenate — O(1) with both tails

a.tail.next = b.head; a.tail = b.tail. Two writes, regardless of how long the lists are. This is the single operation where linked lists genuinely beat every array variant: a billion-element list can be appended to another in constant time.

Interactive: Operation Cost Visualizer

Pick an operation, choose a list size, and step through the work. The cyan bar shows pointer hops in the linked list; the green bar shows the equivalent step count in a dynamic array. Watch how the two curves cross as the operation changes — that crossing is the only reason to ever pick a linked list.

Notice three things while you play:

1. access middle visits $n/2$ nodes; arrays jump in one step.
2. append (no tail) visits every node; append (with tail) visits one. Same operation, different data structure.
3. delete head visits one node for the linked list, $n$ for the array. The linked list is asymptotically better, even though the array beats it on most other ops.

Worked Example I: Merge Two Sorted Lists

This is the canonical linked-list interview problem and the recursive step inside merge sort. Given two sorted singly linked lists, produce a single sorted list by rewiring pointers — no new nodes, no copies. The famous trick is the dummy head: a placeholder node whose only purpose is to absorb the "is this the first element?" special case so the loop body has zero branches.

merge_sorted(1->4->5, 2->3->6) returns 1->2->3->4->5->6

If a.val=3 and b.val=3, we take from a first. Stable merge sort relies on this.

If a = 9->10 remains and b is None, tail.next = a installs both nodes with one assignment — no element-by-element copy.

1from dataclasses import dataclass
2from typing import Optional
3
4@dataclass
5class Node:
6    val: int
7    next: Optional["Node"] = None
8
9def merge_sorted(a: Optional[Node], b: Optional[Node]) -> Optional[Node]:
10    dummy = Node(val=0)        # sentinel — never returned to caller
11    tail = dummy               # always points at the last node we appended
12
13    while a is not None and b is not None:
14        if a.val <= b.val:
15            tail.next = a
16            a = a.next
17        else:
18            tail.next = b
19            b = b.next
20        tail = tail.next       # advance the writer
21
22    tail.next = a if a is not None else b   # attach the remainder in O(1)
23    return dummy.next                       # skip the sentinel

Complexity. Each iteration moves one of a, b forward by one and does $O(1)$ work, so the total cost is $O(n + m)$ time and $O(1)$ extra space (we allocate one dummy node, period). This is the engine that powers merge sort on linked lists: $O(n \log n)$ time, $O(\log n)$ recursion stack, and no need for random access — making it the sort of choice for linked structures.

Worked Example II: k-th Node From the End

"Find the $k$-th node from the end" is asked at every coding interview because it forces the candidate to discover the two-pointer (lead/follow) idiom. The naive solution walks the list twice (once to compute length, once to walk $n - k$ steps); the elegant solution does it in one pass.

On 1->2->3->4->5 with k=2, returns the node holding 4.

k=2, list=1->2->3->4->5: after the loop, lead points at the node holding 3.

k=2, list=1->2->3->4->5: lead becomes None after pointing past 5. follow has stepped from 1 to 4. Return the node holding 4.

1def kth_from_end(head: Optional[Node], k: int) -> Optional[Node]:
2    if k <= 0:
3        return None
4
5    lead = head
6    for _ in range(k):           # advance lead k steps first
7        if lead is None:
8            return None          # list shorter than k — no answer
9        lead = lead.next
10
11    follow = head
12    while lead is not None:      # walk both until lead falls off
13        lead = lead.next
14        follow = follow.next
15
16    return follow                # follow is now k from the end

Complexity. One pass, two pointer hops per node visited. $O(n)$ time, $O(1)$ extra space — and crucially one traversal, not two. On a list whose nodes live in cold RAM, halving the number of passes can halve real wall-clock time even though Big-O is unchanged.

Same Algorithms in TypeScript

Here is merge_sorted in TypeScript with class-based nodes. The shape is identical — the dummy-head trick is language-agnostic — but the type system makes the nullable next-pointer explicit, which catches a whole class of bugs at compile time.

1class ListNode {
2  constructor(public val: number, public next: ListNode | null = null) {}
3}
4
5function mergeSorted(
6  a: ListNode | null,
7  b: ListNode | null,
8): ListNode | null {
9  const dummy = new ListNode(0);
10  let tail = dummy;
11
12  while (a !== null && b !== null) {
13    if (a.val <= b.val) {
14      tail.next = a;
15      a = a.next;
16    } else {
17      tail.next = b;
18      b = b.next;
19    }
20    tail = tail.next!; // safe: we just assigned it
21  }
22
23  tail.next = a !== null ? a : b;
24  return dummy.next;
25}
26
27function kthFromEnd(head: ListNode | null, k: number): ListNode | null {
28  if (k <= 0) return null;
29
30  let lead: ListNode | null = head;
31  for (let i = 0; i < k; i++) {
32    if (lead === null) return null;
33    lead = lead.next;
34  }
35
36  let follow: ListNode | null = head;
37  while (lead !== null) {
38    lead = lead.next;
39    follow = follow!.next;
40  }
41  return follow;
42}

Two language-level observations:

• The ! non-null assertion on tail.next! is a deliberate signal to the reader: "I have just written a non-null value here, the type checker can't prove it, but I can." In performance-critical code, the alternative (a runtime null check) costs a branch per loop iteration.
• A C or C++ port would look almost identical, but you would also write delete / free calls when nodes are removed from a list — Python and TypeScript hand that off to the GC.

The Linked-List Algorithm Bestiary

Beyond the basic CRUD operations, a small zoo of classic algorithms operate on linked lists. Memorising these templates pays off in interviews, in production code review, and (most importantly) in spotting when a problem is secretly "just" one of these.

Where These Operations Run in Production

The pattern across all ten: linked lists win when (a) you already hold pointers to nodes (intrusive use), (b) the dominant operations are splice/unlink, and (c) random access is unnecessary. They lose any time you would have walked the structure linearly anyway.

Pattern Recognition: Reach for What?

Pitfalls and Performance Traps

1. The accidental O(n²) append loop

1# WRONG: append walks to the tail every time
2for v in values:                # values has length n
3    head = append_no_tail(head, v)   # O(n) per call → O(n^2) total
4
5# RIGHT: keep a tail pointer, OR build in reverse and reverse once
6tail = None
7for v in values:
8    node = Node(v)
9    if head is None:
10        head = tail = node
11    else:
12        tail.next = node
13        tail = node

2. Reversing without saving next first

1# WRONG: we clobber curr.next BEFORE saving it
2prev = None
3curr = head
4while curr is not None:
5    curr.next = prev      # destroys the link to the rest of the list!
6    prev = curr
7    curr = curr.next      # now points at prev — infinite loop
8
9# RIGHT: save nxt, then rewire
10prev = None
11curr = head
12while curr is not None:
13    nxt = curr.next       # save BEFORE we overwrite
14    curr.next = prev
15    prev = curr
16    curr = nxt

3. Forgetting to update tail on delete-tail

After deleting the last node, tail is dangling. Production bug: the next append writes through the old (freed) tail. Always update tail in lockstep with the structural change.

4. Concatenation without both tail pointers

a.tail.next = b.head is $O(1)$ only if you have a.tail. Without it, you walk a first — back to $O(n)$. The whole point of a tail pointer is to make this case constant time; do not lose it.

5. Caching length but updating it inconsistently

Cached size is one of the most common sources of correctness bugs. Every mutation method must update the count. A single forgotten increment in insert_after and your iterator runs short by one. Either cache it religiously or compute it on demand — never half-and-half.

Quick Checks

With the operations catalogued and their real costs understood, we are ready to study the algorithms that make linked lists genuinely indispensable. The next section dives into the two-pointer family: Floyd's cycle detection, finding the middle, finding the cycle entry, and the deeper invariant-based proofs that show why these tricks always work.