Linked lists

coreCommon atAmazonMicrosoftMetaBloombergHRTRead firstArraysPractise in the Sandbox →

A linked list stores each item in a node that points to the next one (and, in a doubly linked list, the previous one). There’s no indexing, so finding position i is O(n), but once you hold a node, inserting or removing next to it is O(1): just rewire a few pointers. Sentinel nodes at both ends remove every “empty list / first node / last node” special case.

The idea in plain words

A treasure hunt: each clue tells you where the next clue is. To reach clue 50 you must follow 49 clues; there’s no shortcut. But inserting a new clue between 12 and 13 is trivial: write the new clue to point at 13, and change clue 12 to point at the new one. Nothing else moves.

That’s the trade against an array:

	Array	Linked list
reach position i	O(1)	O(i)
insert/remove at a known spot	O(n) (shift)	O(1) (rewire)
memory	one block, cache friendly	one allocation per node, plus pointers, scattered

A doubly linked list adds a prev pointer to each node. That’s what makes removing a node O(1) when all you have is the node itself: you can reach both neighbours without walking from the head.

Sentinels (also called dummy nodes) are permanent fake nodes at the front and back. With them, every real node always has a real prev and a real next, so insert and remove are the same four or two lines every time.

See it

Push to the front and back, click a node to select it, insert after it or remove it. Each operation plays the exact pointer writes in order. Note that none of them branch on “is this the first node?”.

Doubly linked list with sentinels

sandbox

valuepush frontpush backinsert after selectedremove selectedreset

node being linked / selectednode being unlinked

dashed boxes = sentinels; solid arrow = next, dashed arrow = prev; the highlighted arrow is the pointer written in this step

Sentinels (dashed) are dummy nodes that never hold data. Click a real node to select it, then insert after it or remove it.

↺◀▶ Play▶1 / 1

log (newest first)

Nothing yet. Try an operation.

When to reach for it

The problem says…	Why a linked list fits
“remove / move this item in O(1)” and you can keep a reference to it	Doubly linked list + a hash map from key to node: O(1) find, O(1) unlink and relink. See caching.
“maintain an order that changes constantly” (recency, insertion order with deletes)	Splicing is O(1); an array would shift.
the input is a linked list	Reverse, merge, split, find middle, detect cycles: pointer manipulation in O(1) space.
“insert many items in the middle while iterating”	Insert next to the cursor without shifting.
chains inside a hash table bucket	Each bucket’s collisions form a short list. See hash maps.

If none of these apply, prefer an array. It’s faster in practice for almost everything else.

How it works

Reversing in place (singly linked)

1. prev = null, curr = head.
2. Save nxt = curr.next before touching anything; it’s the only path to the rest of the list.
3. Flip the link: curr.next = prev.
4. Advance: prev = curr, curr = nxt. When curr is null, prev is the new head.

Reverse a singly linked list in place

step through

node values (up to 8)

prevnull

curr1

nxt—

list from prevnull

prev = null, curr = head. Invariant: everything before curr is already reversed and starts at prev.

↺◀▶ Play▶1 / 22

Python

reverse.py

from __future__ import annotations
from dataclasses import dataclass


@dataclass
class Node:
    val: int
    next: Node | None = None


def reverse(head: Node | None) -> Node | None:
    prev: Node | None = None
    curr = head
    while curr:
        nxt = curr.next  # 1. save the rest before we cut the link
        curr.next = prev  # 2. flip one link
        prev = curr  # 3. the reversed part now starts at curr
        curr = nxt  # 4. move into the untouched part
    return prev  # prev is the new head


def build(vals: list[int]) -> Node | None:
    dummy = Node(0)  # a dummy head avoids special-casing the first append
    tail = dummy
    for v in vals:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next


def to_list(head: Node | None) -> list[int]:
    out: list[int] = []
    while head:
        out.append(head.val)
        head = head.next
    return out


if __name__ == "__main__":
    assert to_list(reverse(build([1, 2, 3, 4, 5]))) == [5, 4, 3, 2, 1]
    assert to_list(reverse(build([7]))) == [7]
    assert reverse(None) is None
    print("ok")

TypeScript

reverse.ts

import assert from "node:assert/strict";

class ListNode {
  constructor(public val: number, public next: ListNode | null = null) {}
}

export function reverse(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let curr = head;
  while (curr) {
    const nxt: ListNode | null = curr.next; // 1. save the rest before we cut the link
    curr.next = prev; // 2. flip one link
    prev = curr; // 3. the reversed part now starts at curr
    curr = nxt; // 4. move into the untouched part
  }
  return prev; // prev is the new head
}

function build(vals: number[]): ListNode | null {
  const dummy = new ListNode(0); // a dummy head avoids special-casing the first append
  let tail = dummy;
  for (const v of vals) tail = tail.next = new ListNode(v);
  return dummy.next;
}

function toArray(head: ListNode | null): number[] {
  const out: number[] = [];
  for (let n = head; n; n = n.next) out.push(n.val);
  return out;
}

assert.deepEqual(toArray(reverse(build([1, 2, 3, 4, 5]))), [5, 4, 3, 2, 1]);
assert.deepEqual(toArray(reverse(build([7]))), [7]);
assert.equal(reverse(null), null);
console.log("ok");

C#

reverse.cs

static ListNode? Reverse(ListNode? head)
{
    ListNode? prev = null, curr = head;
    while (curr is not null)
    {
        var nxt = curr.Next;   // 1. save the rest before we cut the link
        curr.Next = prev;      // 2. flip one link
        prev = curr;           // 3. the reversed part now starts at curr
        curr = nxt;            // 4. move into the untouched part
    }
    return prev;               // prev is the new head
}

static ListNode? Build(int[] vals)
{
    var dummy = new ListNode(0); // a dummy head avoids special-casing the first append
    var tail = dummy;
    foreach (int v in vals) tail = tail.Next = new ListNode(v);
    return dummy.Next;
}

static List<int> ToList(ListNode? head)
{
    var output = new List<int>();
    for (var n = head; n is not null; n = n.Next) output.Add(n.Val);
    return output;
}

if (!ToList(Reverse(Build([1, 2, 3, 4, 5]))).SequenceEqual([5, 4, 3, 2, 1])) throw new Exception("reverse");
if (!ToList(Reverse(Build([7]))).SequenceEqual([7])) throw new Exception("single");
if (Reverse(null) is not null) throw new Exception("empty");
Console.WriteLine("ok");

class ListNode(int val)
{
    public int Val = val;
    public ListNode? Next;
}

Splicing with sentinels (doubly linked)

1. Create two sentinels, head and tail, linked to each other. The real nodes live between them.
2. Insert node after a: with b = a.next, first set the new node’s own pointers (node.prev = a, node.next = b), then the neighbours’ (a.next = node, b.prev = node).
3. Unlink node: node.prev.next = node.next and node.next.prev = node.prev.
4. Optionally reset the removed node’s pointers so a stale reference can’t walk back into the list.
5. Front is “insert after head”, back is “insert after tail.prev”; empty means head.next == tail.

Python

insert_after / unlink.py

from __future__ import annotations


class DNode:
    __slots__ = ("val", "prev", "next")

    def __init__(self, val: int = 0) -> None:
        self.val = val
        self.prev: DNode = self  # sentinels start pointing at themselves
        self.next: DNode = self


def make_list() -> tuple[DNode, DNode]:
    head, tail = DNode(), DNode()  # 1. two sentinels that never hold data
    head.next, tail.prev = tail, head
    return head, tail


def insert_after(a: DNode, node: DNode) -> None:
    b = a.next
    node.prev, node.next = a, b  # 2. set the new node's own links first
    a.next = b.prev = node  # 3. then point both neighbours at it


def unlink(node: DNode) -> None:
    node.prev.next = node.next  # 4. neighbours skip over the node
    node.next.prev = node.prev
    node.prev = node.next = node  # 5. detach, so stale references can't wander back in


def values(head: DNode, tail: DNode) -> list[int]:
    out, n = [], head.next
    while n is not tail:
        out.append(n.val)
        n = n.next
    return out


if __name__ == "__main__":
    head, tail = make_list()
    a, b, c = DNode(1), DNode(2), DNode(3)
    insert_after(head, a)  # front
    insert_after(a, c)
    insert_after(a, b)  # middle
    assert values(head, tail) == [1, 2, 3]
    unlink(b)  # O(1): no search, we hold the node
    assert values(head, tail) == [1, 3]
    insert_after(tail.prev, b)  # back
    unlink(a)
    unlink(c)
    unlink(b)
    assert values(head, tail) == [] and head.next is tail and tail.prev is head
    print("ok")

TypeScript

insert_after / unlink.ts

import assert from "node:assert/strict";

class DNode {
  prev: DNode = this; // sentinels start pointing at themselves
  next: DNode = this;
  constructor(public val = 0) {}
}

function makeList(): [DNode, DNode] {
  const head = new DNode(), tail = new DNode(); // 1. two sentinels that never hold data
  head.next = tail;
  tail.prev = head;
  return [head, tail];
}

export function insertAfter(a: DNode, node: DNode): void {
  const b = a.next;
  node.prev = a; // 2. set the new node's own links first
  node.next = b;
  a.next = node; // 3. then point both neighbours at it
  b.prev = node;
}

export function unlink(node: DNode): void {
  node.prev.next = node.next; // 4. neighbours skip over the node
  node.next.prev = node.prev;
  node.prev = node.next = node; // 5. detach, so stale references can't wander back in
}

function values(head: DNode, tail: DNode): number[] {
  const out: number[] = [];
  for (let n = head.next; n !== tail; n = n.next) out.push(n.val);
  return out;
}

const [head, tail] = makeList();
const a = new DNode(1), b = new DNode(2), c = new DNode(3);
insertAfter(head, a); // front
insertAfter(a, c);
insertAfter(a, b); // middle
assert.deepEqual(values(head, tail), [1, 2, 3]);
unlink(b); // O(1): no search, we hold the node
assert.deepEqual(values(head, tail), [1, 3]);
insertAfter(tail.prev, b); // back
unlink(a); unlink(c); unlink(b);
assert.deepEqual(values(head, tail), []);
assert.ok(head.next === tail && tail.prev === head);
console.log("ok");

C#

insert_after / unlink.cs

var (head, tail) = MakeList();
DNode a = new(1), b = new(2), c = new(3);
InsertAfter(head, a);                 // front
InsertAfter(a, c);
InsertAfter(a, b);                    // middle
if (!Values(head, tail).SequenceEqual([1, 2, 3])) throw new Exception("insert");
Unlink(b);                            // O(1): no search, we hold the node
if (!Values(head, tail).SequenceEqual([1, 3])) throw new Exception("unlink");
InsertAfter(tail.Prev, b);            // back
Unlink(a); Unlink(c); Unlink(b);
if (Values(head, tail).Count != 0 || head.Next != tail || tail.Prev != head) throw new Exception("empty");
Console.WriteLine("ok");

static (DNode, DNode) MakeList()
{
    DNode head = new(), tail = new(); // 1. two sentinels that never hold data
    head.Next = tail;
    tail.Prev = head;
    return (head, tail);
}

static void InsertAfter(DNode a, DNode node)
{
    var b = a.Next;
    node.Prev = a; node.Next = b;     // 2. set the new node's own links first
    a.Next = node; b.Prev = node;     // 3. then point both neighbours at it
}

static void Unlink(DNode node)
{
    node.Prev.Next = node.Next;       // 4. neighbours skip over the node
    node.Next.Prev = node.Prev;
    node.Prev = node.Next = node;     // 5. detach, so stale references can't wander back in
}

static List<int> Values(DNode head, DNode tail)
{
    var output = new List<int>();
    for (var n = head.Next; n != tail; n = n.Next) output.Add(n.Val);
    return output;
}

class DNode
{
    public int Val;
    public DNode Prev, Next;
    public DNode(int val = 0) { Val = val; Prev = this; Next = this; } // sentinels start self-linked
}

Order of writes

When inserting, set the new node’s pointers first: they only read the list, so a mistake there can’t lose anything. Then overwrite the neighbours. If you write a.next = node before reading a.next into b, you’ve lost the rest of the list. Saying “I’ll save b first” out loud catches this.

Linked lists in each language

	Python	TypeScript	C#
built in	none (deque is not a node list you can splice)	none	LinkedList<T> (doubly linked) with LinkedListNode<T>
O(1) ops on a node	write your own Node class	write your own	AddAfter(node, x), AddBefore, Remove(node), AddFirst, RemoveLast
node class tips	__slots__ or @dataclass(slots=True) to cut memory	class with next: Node | null	class (reference type); a record gives value equality you don’t want here
null-safety	Optional[Node] / Node | None	strict null checks, ! only when proven	nullable reference types, ?.

In interviews you nearly always write your own node class; it’s three lines and shows you know the mechanics.

What it costs

Operation	Singly linked	Doubly linked	Notes
access / search	O(n)	O(n)	Walk from the head.
insert at head	O(1)	O(1)
insert at tail	O(1) with a tail pointer	O(1)
insert after a held node	O(1)	O(1)
remove a held node	O(n) (need its predecessor)	O(1)	The reason prev exists.
remove head	O(1)	O(1)
memory per item	value + 1 pointer	value + 2 pointers	Plus allocator overhead per node.

Big-O hides the constant: following pointers means a likely cache miss per node, while an array scan streams through memory. A linked list that’s “O(n), same as an array” can be several times slower to traverse.

Variations you’ll meet

• Fast and slow pointers. Move one pointer 2 steps, another 1 step. They meet if there’s a cycle (Floyd’s algorithm); when fast hits the end, slow is at the middle. See two pointers.
• Dummy head for building. Start a result list at a dummy node and tail.next = … repeatedly; return dummy.next. Removes the “first element” special case when merging or filtering.
• Circular lists. The last node points back to the first. A single sentinel that is both head and tail gives a circular doubly linked list (that’s how .NET’s LinkedList<T> works inside).
• Hash map + doubly linked list. O(1) lookup plus O(1) reorder: the standard shape behind recency-ordered caches and ordered dictionaries.
• Skip lists. Linked lists with express lanes give O(log n) search; Redis sorted sets use them. See sorted containers.
• Intrusive / index-based lists. Store next/prev as integer indices into arrays (no per-node allocation). Common in performance-sensitive code and in hash table internals.

Pitfalls

• Losing the rest of the list by overwriting next before saving it.
• Null dereferences at the ends: node.next.next when node.next is null. Sentinels fix most of these; for singly linked code, check fast and fast.next.
• Forgetting the back pointer. Updating next but not prev (or vice versa) leaves the list consistent in one direction only. Test by walking both ways.
• Off-by-one in “k-th from the end”. Draw a 3-node example and count.
• Recursion on long lists. Recursive reverse or traversal uses O(n) call stack; Python fails around 1,000 nodes by default.
• Comparing nodes by value when you mean identity. Use is (Python), === (TS), ReferenceEquals or a class without overridden equality (C#).

In the interview

• Draw it. Three boxes and arrows on the whiteboard prevent most pointer bugs.
• Say whether you use sentinels and why: “Dummy head and tail so insert and remove never branch on empty or end-of-list.”
• Narrate each write in order: “Save next, flip, advance.” Interviewers watch the order.
• Test the edges explicitly: empty list, one node, two nodes, operation at the head, operation at the tail.
• Follow-ups: “do it in O(1) space” (no auxiliary array), “do it without recursion”, “make it thread-safe” (a lock around the splice; the four writes must appear atomic).

Check yourself

Check yourself

pick one

You hold a reference to a node in a singly linked list and must delete it in O(1). The node is not the tail. What's the classic trick?

AImpossible without the headBCopy the next node's value into this node, then unlink the next nodeCSet this node to null

Check yourself

pick one

In a doubly linked list with head and tail sentinels, how many pointer writes does removing a node take (excluding optional cleanup)?

A1B2C4DDepends on whether it is the first node

Check yourself

pick one

A cache keeps its entries ordered by last use, and a hash map hands you any entry's node. Why is that list doubly linked rather than singly linked?

ADoubly linked lists use less memoryBTo remove an arbitrary node in O(1) you need its predecessor, and prev gives it without a walkCSingly linked lists cannot be iterated

Practice on your own

Classic textbook exercises, not gym questions:

• Detect a cycle and return the node where it starts (Floyd).
• Remove the k-th node from the end in one pass.
• Merge two sorted linked lists using a dummy head.
• Reverse the nodes between positions m and n in one pass.

Go deeper

• CLRS, §10.2 “Linked lists”: sentinels and the LIST-DELETE / LIST-INSERT procedures.
• Sedgewick and Wayne, Algorithms, §1.3 “Linked lists”.
• Microsoft Learn, LinkedList<T> (O(1) node operations, circular implementation).
• Bjarne Stroustrup, “Why you should avoid linked lists” (GoingNative 2012 keynote): why arrays usually win in practice.

Related

Hash mapsPair with a list for O(1) lookup and reorder.

CachingEviction orders built on splicing.

Two pointersFast and slow pointers on lists.

Queues and dequesLists as queues, and why ring buffers often win.