vault

Singly Linked List

15 min read

Singly Linked List

A singly linked list is a sequence of nodes where each node stores a value and a single pointer (next) to the following node; the last node’s next is null (or a sentinel). Access to the list is via a single head reference. Compared with the contiguous array, a singly linked list trades O(1) random access (which it cannot do) for O(1) insertion and deletion given a node reference, no upfront capacity allocation, and the ability to splice or rearrange chunks of the list cheaply by pointer rewiring. This note covers the data structure itself in depth — for the canonical interview operations on top of it (cycle detection, reversal, merging) see Linked List Cycle Detection, Linked List Reversal, and Merge Two Sorted Lists.

1. Intuition — The Treasure Hunt

A singly linked list is a treasure hunt: you start with one clue (the head), which tells you where to find the next clue. That clue tells you where the next clue is. Eventually a clue says “the hunt ends here” (null). To get to the 50th clue, you must follow 49 clues in order — there is no map, no shortcut. To insert a new clue between the 30th and 31st, you only need to (a) write the new clue with its arrow pointing at the old 31st, and (b) update the 30th clue’s arrow to point at the new one. The 32nd through 50th clues do not need to be touched at all — a key advantage over a numbered list (array), where inserting at position 31 forces you to renumber everything after.

The cost of this insertion-friendliness: every clue takes you exactly one hop forward. There is no “jump to clue 50” shortcut. If you need to find a value, you must walk the entire list.

2. Tiny Worked Example

Build a list 1 → 2 → 3 and trace each operation.

2.1 After Three Inserts at Head

Start with head = null. Insert 3, then 2, then 1 at the head.

After insert(3):

  head
   ↓
  [3 | next=null]


After insert(2):

  head
   ↓
  [2 | next=*]──→[3 | next=null]


After insert(1):

  head
   ↓
  [1 | next=*]──→[2 | next=*]──→[3 | next=null]

Each “insert at head” step:

  1. Create a new node with the value.
  2. Set the new node’s next pointer to the current head.
  3. Update head to point at the new node.

Total work per insert: 3 pointer assignments. O(1) regardless of list length.

2.2 Insert at Tail (Without Tail Pointer)

Insert 4 at the tail of 1 → 2 → 3.

Step 1 — walk to last node:
  head
   ↓
  [1 | next=*]──→[2 | next=*]──→[3 | next=null]
                                  ↑
                                cursor

Step 2 — rewire cursor.next:
  head
   ↓
  [1 | next=*]──→[2 | next=*]──→[3 | next=*]──→[4 | next=null]

Walking to the last node is O(n). Once there, the splice is O(1). Total: O(n).

This is the motivation for keeping a tail pointer (§4.3) — it shaves the walk to O(1).

2.3 Delete the Node with Value 2

Before:
  head
   ↓
  [1 | next=*]──→[2 | next=*]──→[3 | next=null]
                  ↑
              target

After:
  head
   ↓
  [1 | next=*]──→[3 | next=null]

  [2 | next=*]   ← orphaned, will be garbage-collected

You walk forward keeping a prev reference. When cursor.val == 2, set prev.next = cursor.next, skipping the target. O(n) to find, O(1) to splice.

3. Pseudocode

class Node:
    value
    next

class SinglyLinkedList:
    head : Node | null

    insert_head(value):
        node := new Node(value, next=head)
        head := node                                # O(1)

    insert_tail(value):                             # without tail pointer
        node := new Node(value, next=null)
        if head == null:
            head := node; return
        cursor := head
        while cursor.next != null:
            cursor := cursor.next
        cursor.next := node                         # O(n)

    find(value) -> Node | null:                     # search
        cursor := head
        while cursor != null:
            if cursor.value == value: return cursor
            cursor := cursor.next
        return null                                 # O(n)

    delete(value):                                  # delete first occurrence
        if head == null: return
        if head.value == value:
            head := head.next; return
        prev := head
        cursor := head.next
        while cursor != null:
            if cursor.value == value:
                prev.next := cursor.next
                return
            prev := cursor
            cursor := cursor.next                   # O(n)

The delete function illustrates a frequent annoyance with singly linked lists: deletion needs the node before the target, because there is no prev pointer to walk backward. We track prev manually as we walk. The next pattern (§4.4) — sentinel/dummy heads — eliminates the special-case for “delete the head” by giving every “real” node a predecessor.

4. Patterns

4.1 Linked List vs Array — When to Choose Which

PropertySingly Linked ListDynamic Array
Random access by indexO(n)O(1)
Insert/delete at headO(1)O(n) (shift everything)
Insert/delete at tailO(1) with tail ptr / O(n) withoutO(1) amortized
Insert/delete at arbitrary position (given pointer)O(1)O(n) shift
Insert/delete at arbitrary position (given index)O(n) walk + O(1) spliceO(n) shift
Memory overhead per element1 pointer (typically 8 bytes)none beyond the value
Cache localityPoor — nodes scattered in heapExcellent — contiguous
Capacity preallocationNone — grow one node at a timeGeometric resizing

The cache-locality difference is the primary reason arrays dominate in practice for typical workloads. Walking 1000 contiguous integers in an array is roughly 10–50× faster than walking 1000 nodes scattered through a heap, despite both being O(n) — the cache-line prefetcher streams the array, while the linked list takes a cache miss on every node. Bjarne Stroustrup has frequently demonstrated this in talks (Stroustrup, GoingNative 2012, “Why You Should Avoid Linked Lists”) — for randomly inserting and removing elements in sorted order, std::vector beats std::list for sizes well into the hundreds of thousands of elements.

So when does a singly linked list actually beat an array?

  • You insert/delete at the head frequently and order matters (e.g., maintaining a stack via head-only operations — though Deque / Dynamic Array also do this efficiently).
  • You splice large chunks between lists — moving a sublist of length k from one list to another is O(1) for linked lists (rewire two pointers) but O(k) for arrays (copy k elements). Compilers’ instruction lists, OS process queues, and concurrent linked structures benefit from this.
  • You cannot afford reallocation pauses — geometric array resize copies everything, which can be a 100 ms hiccup on a 100 MB array. Linked lists never re-allocate; each insert is O(1) worst-case.
  • You don’t know an upper bound on size and the geometric overhead of a dynamic array is unacceptable.

4.2 Sentinel / Dummy Head

A sentinel head (also called dummy head) is a permanent node before the first real node. It carries no payload; its only purpose is to be a predecessor for the first real node, eliminating the special-case for “insert before the head” or “delete the head.”

With sentinel:

  [sentinel] ──→ [1] ──→ [2] ──→ [3] ──→ null
       ↑
   "head" pointer always points here, never moves

Without the sentinel, code like delete(head_value) needs a special branch (if head.value == target: head = head.next). With the sentinel, every real node has a predecessor (the sentinel for the first one, otherwise the real node before it), so delete is one uniform loop:

def delete(self, value):
    prev = self.sentinel
    while prev.next is not None:
        if prev.next.value == value:
            prev.next = prev.next.next
            return
        prev = prev.next

This is a small but meaningful interview tip: whenever a linked-list problem has special-cased head behavior, a sentinel often eliminates it. Reversal, merging, and partition operations all simplify when you allocate a sentinel first.

4.3 Tail Pointer Optimization

Maintain a tail reference alongside head:

head ──→ [1] ──→ [2] ──→ [3] ←── tail
                            next=null

Effect on costs:

OperationWithout tailWith tail
insert_headO(1)O(1)
insert_tailO(n)O(1)
delete_headO(1)O(1) (and update tail if list becomes empty)
delete_tailO(n) (still — can’t reach the predecessor of tail in O(1) without prev)O(n) still

Notice delete_tail is still O(n) even with a tail pointer — to splice out the last node you need to set prev.next = null, but prev is the second-to-last node, and reaching it from head is O(n). The only way to make delete_tail O(1) is to carry a prev pointer per node — at which point you have a Doubly Linked List.

Tail-pointer linked lists are exactly what you want for FIFO queues built from linked storage: enqueue appends at tail (O(1)), dequeue removes at head (O(1)). See Queue for the queue abstraction.

4.4 The “Runner” / Slow-Fast Pointer Technique

Many linked-list algorithms walk two pointers at different speeds. The classic example is finding the middle node in one pass:

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow      # when fast hits the end, slow is at the middle

When fast is at the end (after 2k steps from head), slow is at position k — the middle. One pass, O(n) time, O(1) space. This same machinery underpins Linked List Cycle Detection (Floyd’s tortoise-and-hare).

A related variant: find the k-th-from-last node. Advance one pointer k steps ahead, then advance both in lockstep until the lead pointer hits the end; the trailing pointer is now k from the end.

5. Python Implementation

from typing import Optional, Iterator
 
class Node:
    """A singly-linked list node — same shape used in cycle / reversal / merge notes."""
    def __init__(self, value, next: Optional["Node"] = None):
        self.value = value
        self.next = next
 
class SinglyLinkedList:
    """Sentinel-headed singly linked list with a tail pointer for O(1) push_back."""
 
    def __init__(self):
        # Sentinel removes the head edge case; tail caches the last real node.
        self._sentinel = Node(value=None)
        self._tail: Node = self._sentinel
        self._size = 0
 
    def __len__(self) -> int:
        return self._size
 
    def __iter__(self) -> Iterator:
        cursor = self._sentinel.next
        while cursor is not None:
            yield cursor.value
            cursor = cursor.next
 
    # ---- O(1) operations ----
 
    def push_front(self, value):
        """Insert at head."""
        node = Node(value, next=self._sentinel.next)
        self._sentinel.next = node
        if self._tail is self._sentinel:           # was empty: tail must update
            self._tail = node
        self._size += 1
 
    def push_back(self, value):
        """Insert at tail (uses cached tail pointer)."""
        node = Node(value)
        self._tail.next = node
        self._tail = node
        self._size += 1
 
    def pop_front(self) -> object:
        """Remove and return the first value; raises IndexError if empty."""
        if self._size == 0:
            raise IndexError("pop from empty list")
        first = self._sentinel.next
        self._sentinel.next = first.next
        if self._tail is first:                    # popped the only node
            self._tail = self._sentinel
        self._size -= 1
        return first.value
 
    # ---- O(n) operations ----
 
    def find(self, value) -> Optional[Node]:
        cursor = self._sentinel.next
        while cursor is not None:
            if cursor.value == value:
                return cursor
            cursor = cursor.next
        return None
 
    def remove(self, value) -> bool:
        """Remove first occurrence; returns True if removed, False if not found."""
        prev = self._sentinel
        while prev.next is not None:
            if prev.next.value == value:
                victim = prev.next
                prev.next = victim.next
                if victim is self._tail:           # removed the tail
                    self._tail = prev
                self._size -= 1
                return True
            prev = prev.next
        return False

The implementation choices to flag:

  • Sentinel head. _sentinel is a permanent node with no payload. push_front, pop_front, and remove never need an if list is empty branch on the sentinel itself — the sentinel always exists. Only the _tail reference needs to fall back to the sentinel when the list goes empty.
  • Tail pointer. Cached so push_back is O(1). When the last real node is removed, _tail must be re-set to the sentinel (the new “predecessor of nothing”).
  • Iterator skips the sentinel. Yields only real values; the sentinel is an implementation artifact, not part of the user-visible sequence.

6. Complexity

OperationTimeSpace
push_frontO(1)O(1)
push_back (with tail pointer)O(1)O(1)
push_back (without tail pointer)O(n)O(1)
pop_frontO(1)O(1)
pop_backO(n)O(1) — see §4.3
find(value)O(n)O(1)
remove(value) (first occurrence)O(n)O(1)
Random access by indexO(n)O(1)
Concatenate two lists (with tail pointers)O(1)O(1)
Reverse — see Linked List ReversalO(n)O(1)

Memory. Each node takes the value’s size plus one pointer (typically 8 bytes on 64-bit systems) plus any allocator overhead (commonly another 8–16 bytes per heap allocation). For a list of 4-byte integers on 64-bit Linux/glibc, this can be 24–32 bytes per element versus 4 bytes per element in a dynamic array — a 6–8× memory blowup. For a list of strings or large structs, the overhead percentage is smaller.

7. Variants

  • Doubly linked list (Doubly Linked List) — adds a prev pointer per node; enables O(1) deletion given a node reference and O(1) pop_back.
  • Circular linked list — last node’s next points back to head (or to a sentinel). Useful for round-robin schedulers and ring buffers; eliminates the null-terminator special case.
  • XOR linked list — stores prev XOR next in a single pointer field, halving the per-node pointer cost of a doubly-linked list. Clever but unfriendly to garbage collectors and tools like Valgrind, so largely a curiosity.
  • Skip list (Skip List) — multi-level singly linked structure that achieves O(log n) search by adding “express lanes.”
  • Unrolled linked list — each node stores an array of multiple values, amortizing the per-element pointer overhead and improving cache locality. Used in some text-editor buffer implementations (e.g., GNU Emacs’ gap buffer is a related but distinct idea).
  • Self-organizing list — moves recently accessed elements toward the head; approximates LRU with a list-only structure.

8. Common Interview Problems

ProblemLeetCodePattern
Reverse Linked ListLC 206See Linked List Reversal
Merge Two Sorted ListsLC 21See Merge Two Sorted Lists
Linked List CycleLC 141See Linked List Cycle Detection
Linked List Cycle II (find start)LC 142Floyd’s two-phase
Middle of the Linked ListLC 876Slow/fast pointer (§4.4)
Remove Nth Node From End of ListLC 19Two-pointer with k-step lead (§4.4)
Palindrome Linked ListLC 234Slow/fast to middle, reverse second half, compare
Intersection of Two Linked ListsLC 160Two-pointer trick: walk both until they meet
Remove Duplicates from Sorted ListLC 83Single-pass, sentinel-headed scan
Partition ListLC 86Two sub-lists with sentinel heads, then concatenate
Add Two NumbersLC 2Pairwise digit add with carry
Reorder ListLC 143Find middle, reverse second half, interleave

9. Pitfalls

9.1 Forgetting Null Checks

cursor.next.value blows up when cursor.next is null. Every dereference of next must come after a cursor.next != null check (or be inside a loop whose condition guarantees it). The slow/fast pointer pattern is especially treacherous — fast.next.next requires both fast and fast.next to be non-null.

9.2 Off-by-One When Counting

“K-th node from the start” — is K 0-indexed or 1-indexed? “K-th from the end” — is the last node K=0 or K=1? Read the problem statement carefully and trace a 4-node example by hand before submitting.

9.3 Losing the Head

A while head: head = head.next loop walks the list but destroys the original head reference. The list is now unreachable from the caller’s perspective. Always use a separate cursor variable: cursor = head; while cursor: cursor = cursor.next.

9.4 Forgetting to Update the Tail Pointer

When you maintain a tail pointer, every operation that could affect the last node — push_back, pop_front of the only node, pop_back (if implemented), remove of the tail value — must also update _tail. This is bug-prone. Some implementations forgo the tail pointer entirely and accept O(n) push_back rather than carry the burden.

9.5 Cycles

If a node is reachable from itself by following next pointers, your “walk to the end” loop becomes infinite. If you might be handed a cyclic list, use Linked List Cycle Detection first. The sentinel-headed list above assumes no cycles in user inputs.

9.6 Aliasing in Tests

node = ll.find(42)
node.value = 100        # silently mutates the list!

find returns a reference, not a copy. If you intend to read-only, rename the return type or copy the value. This is a frequent bug source in code that relies on linked-list internals.

9.7 Reversed prev and cursor

When walking with a prev and cursor pair (for delete or reverse), it is easy to write prev = cursor; cursor = cursor.next after mutating cursor.next, by which time cursor.next already points elsewhere. Always save what you need before mutation. See Linked List Reversal §3 — the iterative reversal pattern is precisely a worked example of doing this correctly.

9.8 Comparing Nodes Instead of Values

if cursor == target compares object identity in most languages; if cursor.value == target compares values. Mistaking one for the other gives subtle bugs — the test passes for some inputs (when the user happens to pass the same Node object) and fails for others.

10. Diagram — Anatomy of a Singly Linked List with Sentinel and Tail

flowchart LR
    S(["sentinel<br/>val=null"])
    A([1])
    B([2])
    C([3])
    N([null])
    S -->|next| A
    A -->|next| B
    B -->|next| C
    C -->|next| N
    head[head pointer] -.points at.-> S
    tail[tail pointer] -.points at.-> C

What this diagram shows. A sentinel-headed, tail-tracked singly linked list with three real values 1, 2, 3. The sentinel is a permanent node carrying no value; the head pointer always points to it (never moves). The tail pointer caches the final real node so that push_back is O(1). The terminal null marks the end of the list — every traversal stops there. The arrows are unidirectional: there is no way to move backward from any node, which is the defining limitation of singly-linked storage and the reason pop_back remains O(n) even with the tail pointer.

11. Open Questions

  • At what list size does an unrolled linked list (multiple values per node) become measurably faster than a plain singly-linked list for typical workloads? Cache-line size and value size both factor in.
  • Is there a real production system in 2026 that benefits from singly linked lists over doubly linked lists for the memory savings, given the per-allocation overhead of modern allocators? Most “linked-list” use cases in production code I’ve seen use doubly linked lists.

12. See Also

Graph View

Backlinks