FundamentalsData structureaka SLL, forward list, one-way list

Singly Linked List

The simplest linked list: each node has a value and one next pointer, so traversal is forward-only and deletion needs the predecessor.

▶ VisualizePattern: Fast & Slow PointersPractice (4)
Progress

Definition

A singly linked list is the basic form of a Linked List: nodes carry exactly one link, next. Memory per node is minimal (value + one pointer), and all operations at the head are O(1). The cost of having only one direction is that you cannot step backwards, so deleting a node requires a pointer to the node before it.

It is the form nearly every interview problem uses (ListNode { val; next }). Techniques that matter here: the dummy-head sentinel, the three-pointer reversal, and running two pointers at different speeds or offsets.

Standard library equivalents: std::forward_list (C++), no direct type in Java/Python/JS (people write the node class themselves). Go's container/list is doubly linked.

next pointerforward onlydummy headpredecessorreversal

Intuition

A mental model before the formal terms.

A train where each carriage only knows the carriage behind it. From the locomotive you can walk to the back, but from the last carriage you cannot see the one in front. To uncouple carriage 5 you must be standing on carriage 4.

Reversal is like turning every coupling around one at a time while holding onto three carriages — the one already turned, the one you are turning, and the next one so you do not lose the rest of the train.

How it works

  1. Node layout: value, next. The list keeps head (and optionally size); a tail pointer is optional but makes append O(1).
  2. insertAt(i, v): walk to node i - 1 (O(i)), then new.next = prev.next; prev.next = new. With a dummy head, i = 0 is the same code path.
  3. deleteAt(i): walk to node i - 1, then prev.next = prev.next.next.
  4. deleteNode(node) without a predecessor: copy node.next.value into node and unlink node.next — works only if node is not the tail.
  5. reverse(): prev = null; while cur: nxt = cur.next; cur.next = prev; prev = cur; cur = nxt; head = prev.
  6. middle(): slow moves 1, fast moves 2; when fast reaches the end slow is at the middle.
  7. kthFromEnd(k): advance lead by k, then move lead and trail together until lead is null.

Why it works

All structural edits are local pointer writes: the nodes before and after the change keep their identity, so nothing else needs to move.

Reversal maintains the invariant that prev heads a correctly reversed list of all nodes visited so far; the loop ends when cur is null, so every node has been visited exactly once.

The offset two-pointer technique works because the gap between the pointers is preserved as both advance one step at a time; when the leader falls off the end, the trailer is exactly k nodes before it.

Operations

OperationDescriptionCost
pushFront(v)Point the new node at head; make it the head.O(1)
pushBack(v)O(1) with a tail pointer, otherwise walk to the end.O(1) / O(n)
popFront()head = head.next.O(1)
insertAt(i, v)Walk to predecessor then splice.O(i)
deleteAt(i)Walk to predecessor then unlink.O(i)
search(v)Forward scan.O(n)
reverse()Three-pointer in-place reversal.O(n)
middle() / kthFromEnd(k)Two-pointer single pass.O(n)

Recognition

How to tell a problem wants this.

  • The problem defines ListNode with val and next only.
  • You must reverse, reorder, rotate, or partition a list in place with O(1) extra space.
  • "Without knowing the length" — use two pointers rather than a counting pass (though a counting pass is also O(n)).
“cycle in linked list” → Fast & Slow Pointers“reverse a linked list” → Linked List Manipulation

Interactive demo

Play, step, change the input. ← → and space work too.

empty list
1/30Start with an empty list: head = null. Each node stores a value and a single `next` pointer, so traversal is one-directional.
VisitingInsertedRemovedMatch
PseudocodeLearn Singly Linked List →
1append(v): walk to the tail; tail.next = Node(v)
2prepend(v): node = Node(v); node.next = head; head = node
3insert(v, i): walk to node i-1; node.next = prev.next; prev.next = node
4delete(v): walk until curr.value == v; prev.next = curr.next
5reverse(): prev = null; curr = head
6  while curr: next = curr.next; curr.next = prev; prev = curr; curr = next
7  head = prev
Variables
size0
Complexity
access O(n)
search O(n)
insert O(1)
delete O(1)
Speed

Pseudocode

1class Node: value, next
2class SinglyLinkedList: head = null, size = 0
3pushFront(v): head = Node(v, head); size++
4insertAt(i, v):
5  if i == 0: pushFront(v); return
6  prev = nodeAt(i - 1); prev.next = Node(v, prev.next); size++
7deleteAt(i):
8  if i == 0: head = head.next; size--; return
9  prev = nodeAt(i - 1); prev.next = prev.next.next; size--
10reverse(): prev = null; cur = head
11  while cur: nxt = cur.next; cur.next = prev; prev = cur; cur = nxt
12  head = prev
13middle(): slow = fast = head; while fast and fast.next: slow = slow.next; fast = fast.next.next; return slow

Implementation

1from typing import Generic, Optional, TypeVar
2 
3T = TypeVar("T")
4 
5 
61 · Node and head pointer
7class ListNode(Generic[T]):
8    __slots__ = ("value", "next")
9 
10    def __init__(self, value: T, next: "Optional[ListNode[T]]" = None) -> None:
11        self.value = value
12        self.next = next
13 
14 
15class SinglyLinkedList(Generic[T]):
16    def __init__(self) -> None:
17        self.head: Optional[ListNode[T]] = None
18        self._n = 0
19 
20    def __len__(self) -> int:
21        return self._n
22 
23    def _node_at(self, i: int) -> ListNode[T]:
24        if not 0 <= i < self._n:
25            raise IndexError(i)
26        cur = self.head
27        for _ in range(i):
28            cur = cur.next  # type: ignore[union-attr]
29        return cur  # type: ignore[return-value]
30 
312 · Push front
32    def push_front(self, v: T) -> None:
33        self.head = ListNode(v, self.head)
34        self._n += 1
35 
363 · Insert at index (walk to i-1)
37    def insert_at(self, i: int, v: T) -> None:
38        if not 0 <= i <= self._n:
39            raise IndexError(i)
40        if i == 0:
41            self.push_front(v)
42            return
43        prev = self._node_at(i - 1)
44        prev.next = ListNode(v, prev.next)
45        self._n += 1
46 
474 · Delete at index (unlink via predecessor)
48    def delete_at(self, i: int) -> T:
49        if not 0 <= i < self._n or self.head is None:
50            raise IndexError(i)
51        if i == 0:
52            gone = self.head
53            self.head = gone.next
54        else:
55            prev = self._node_at(i - 1)
56            gone = prev.next  # type: ignore[assignment]
57            prev.next = gone.next
58        self._n -= 1
59        return gone.value
60 
615 · Reverse in place
62    def reverse(self) -> None:
63        prev: Optional[ListNode[T]] = None
64        cur = self.head
65        while cur is not None:
66            cur.next, prev, cur = prev, cur, cur.next
67        self.head = prev
68 
696 · Middle via slow/fast pointers
70    def middle(self) -> T:
71        if self.head is None:
72            raise ValueError("empty list")
73        slow = fast = self.head
74        while fast is not None and fast.next is not None:
75            slow = slow.next  # type: ignore[assignment]
76            fast = fast.next.next
77        return slow.value
Walkthrough
  1. _node_at walks i links with a for _ in range(i) loop; the leading underscore marks it as internal.
  2. push_front wraps the old head in a new node — one line, O(1).
  3. insert_at/delete_at find the predecessor with _node_at(i - 1); index 0 is special-cased because the head has no predecessor.
  4. reverse uses a single tuple assignment cur.next, prev, cur = prev, cur, cur.next — right side evaluates fully before any assignment.
  5. middle runs the slow/fast walk; is not None checks avoid falsy-value surprises.
Complexity (this implementation)
time O(1) push_front, O(n) insert_at/delete_at/reverse/middle · space O(n)
Language notes
  • Tuple assignment order matters: cur.next, prev, cur = prev, cur, cur.next works, but reordering the targets so cur is assigned before cur.next breaks it.
  • Type checkers need Optional narrowing; the # type: ignore comments mark spots where a bounds check already guarantees non-None.
  • Unlinked nodes are freed immediately by reference counting.
Common mistakes in this language
  • Using while cur: instead of while cur is not None: when nodes could be falsy.
  • Recursing to reverse a long list and hitting RecursionError.
  • Walking to index i rather than i - 1 before insert/delete.
Language differences that matter here
  • Python's tuple assignment lets reverse flip links in one statement; C++/JS/TS need an explicit temporary.
  • Freeing removed nodes: explicit delete in C++; automatic in JS/TS/Python.
  • Null safety: TypeScript makes T | null narrowing mandatory; JS and Python rely on runtime checks; C++ dereferencing nullptr is undefined behaviour.
  • C++ std::forward_list is the only standard-library singly linked list among the four languages.

Complexity

OperationAverageWorstNote
AccessO(n)O(n)O(1) at the head.
SearchO(n)O(n)
InsertO(1)O(1)After a known node; O(n) by index.
DeleteO(1)O(1)After a known node; O(n) by index or by node without predecessor.
UpdateO(n)O(n)O(1) once located.
Push front / Pop frontO(1)O(1)
Push backO(n)O(n)O(1) if a tail pointer is maintained.
ReverseO(n)O(n)
SpaceO(n)One pointer per node.

Advantages & disadvantages

Advantages
  • Smallest memory footprint of any linked list (one pointer per node).
  • O(1) push/pop at the head — a natural Stack.
  • Simple to implement; every interview list problem builds on it.
Disadvantages
  • Forward traversal only; no O(1) access to a node's predecessor.
  • Deleting a given node needs a preceding pointer (or the copy-next trick, which fails on the tail).
  • O(n) access by index and no cache locality.

Use cases

  • Stacks and simple queues (with a tail pointer).
  • Hash-table bucket chains (Separate Chaining) where only insert-at-head and scan are needed.
  • Adjacency lists built as linked nodes in memory-constrained systems.
  • Immutable / persistent lists in functional languages where sharing tails is free.
Use it when
  • Stack-like usage (LIFO at the head) with minimal memory.
  • Forward-only iteration with occasional insertion after the current node.
  • Interview problems that specify ListNode — the structure is given, the skill is pointer manipulation.
Avoid it when
  • You need to remove arbitrary nodes given only their reference, or iterate backwards — use a Doubly Linked List.
  • You need O(1) append without wanting to maintain a tail pointer — use a Dynamic Array or Deque.
  • Random access or sorted-order queries.

Alternatives

Doubly Linked ListDynamic ArrayDequeCircular Linked List

Common mistakes

  • Overwriting cur.next before saving it during reversal, dropping the rest of the list.
  • Handling i == 0 separately and then also mis-handling it — use a dummy head so one code path covers all positions.
  • Using the copy-next deletion trick on the tail node (there is no next to copy from).
  • Fast pointer check while fast.next without first checking fast itself for even-length lists.
  • Returning the wrong middle for even lengths (first vs second middle) — decide the loop condition intentionally.

Interview patterns

  • Reverse the whole list, reverse a sublist [m, n], reverse in k-groups.
  • Find the middle with slow/fast; split the list for merge sort or palindrome checks.
  • Remove the n-th node from the end with an offset pair and a dummy head.
  • Merge two sorted lists by splicing; partition around a value with two dummy heads.
  • Add two numbers represented as lists; detect and remove cycles.
Interview questions on this

Interview problems

Linked List CycleeasyMiddle of the Linked ListeasyReverse Linked ListeasyMerge k Sorted Listshard