Boo-AI — Master Artificial Intelligence by Building from Scratch

A singly linked list is a finite chain of heap-allocated nodes where each node carries a payload and exactly one outgoing pointer to its successor. From the outside it behaves like a sequence; from the inside it is a graph with out-degree exactly one and no cycles. The whole structure is reachable from a single external pointer called the head; the last node's pointer is the sentinel value None (Python) or nullptr (C++).

Section 6.1 introduced nodes and pointers in isolation. This section assembles them into a complete abstract data type with rigorous performance guarantees, an interactive lab to watch every pointer rewrite happen, and two production-grade implementations — one in Python and one in modern C++ — that survive code review at any serious shop.

Definition and Invariants

Formally, a singly linked list is a tuple $L = (\text{head}, \text{tail}, n)$ with the following invariants. Let $v_0 = \text{head}$ and $v_{i+1} = v_i.\text{next}$ .

Termination. There exists a finite $n \geq 0$ such that $v_n = \bot$ (None / nullptr). No cycles — a cycle would make the structure infinite under .next traversal.
Reachability. Every node in the list is reachable from $\text{head}$ in $O(n)$ hops. Lose head and the list becomes garbage.
Tail consistency. If $n > 0$ , then $\text{tail} = v_{n-1}$ and $\text{tail.next} = \bot$ . If $n = 0$ then both head and tail are $\bot$ .
Size cache. The stored size $n$ equals the number of reachable nodes from head. Every mutator must preserve this.

Why these invariants matter: every algorithm in this section assumes them. A bug that violates one (e.g., an append that forgets to advance tail) won't fail loudly — the list will look fine until the next operation that depends on the broken invariant, often a hundred lines and an hour later. Maintain invariants in the same function that mutates state, never in two places.

The Singly Linked List ADT

The minimal ADT we will implement covers every operation a singly linked list supports asymptotically well. Methods that would force a linear scan from head (e.g., access by index) are listed honestly with their $O(n)$ cost so you can see why arrays and linked lists complement rather than replace each other.

Operation	Complexity	What it costs structurally
is_empty()	O(1)	Check head is None
__len__()	O(1)	Return the cached size
prepend(v)	O(1)	One allocation, two pointer writes
append(v) with tail pointer	O(1)	One allocation, two pointer writes
append(v) without tail pointer	O(n)	Walk to the end first
insert_after(node, v)	O(1)	Splice with no traversal — node already in hand
insert_at(i, v)	O(i)	Walk i steps, then O(1) splice
delete_head()	O(1)	Move head one hop
delete_after(node)	O(1)	Skip one node — no traversal
delete_value(v)	O(n)	Two-pointer walk to find, then unlink
find(v)	O(n)	Linear scan from head
reverse()	O(n) time, O(1) space	Walk once, flip every next pointer
__iter__()	O(n) total	One yield per hop
to_list()	O(n)	Eager copy into a Python list

Reading the table: the only operations that beat an array unconditionally are prepend, insert_after, and delete_after — all of them require either "at the head" or "at a node you already hold". Index-based access loses to arrays by an order of magnitude. Choose the structure that matches your dominant access pattern.

The Two-Pointer Traversal Idiom

A singly linked list's deepest constraint is that given a node, you can only see forward. There is no .prev pointer. Yet many mutations need to know the predecessor: to delete a node you must rewrite its predecessor's .next. The fix is the two-pointer walk: maintain a cursor $\text{curr}$ and a one-step lagging cursor $\text{prev}$ that marches with it.

🐍python

1prev, curr = None, head
2while curr is not None and not condition(curr):
3    prev, curr = curr, curr.next
4# At this point: prev is the predecessor of curr (or None if curr == head).

Two facts make this idiom safe and idiomatic. First, the tuple assignment prev, curr = curr, curr.next evaluates both right-hand expressions before any assignment, so we never lose a pointer. Second, prev is $\bot$ exactly when $\text{curr} = \text{head}$ , which gives us a clean branch for the "deleting the head" special case. You will see this pattern in every singly-list mutator below.

The Tail Pointer: Making Append O(1)

Without a tail pointer, append must walk from head to find the last node before splicing — $\Theta(n)$ per call. Calling it $n$ times in a loop (a stunningly common pattern: building a list from a stream) costs $\Theta(n^2)$ . A tail pointer fixes this for one extra word of state and one extra line of bookkeeping per mutator.

The trade is real but small: every operation that touches the last node must update tail. Specifically:

append sets tail to the new node.
prepend on an empty list sets tail to the new node.
delete_head on a one-node list clears tail to None.
delete_value when the deleted node was the tail sets tail to its predecessor.
reverse sets tail to the old head before the loop.

The classic bug: updating head but forgetting tail (or vice versa). Symptom: a few operations later, an append writes to a node that is no longer in the list. Lists with a tail pointer should be tested with the four boundary cases — insert into empty, delete the only element, append after empty, reverse a one-node list — on every change.

The Sentinel Head Pattern

Most of the "is it the head?" special cases above can be eliminated by allocating one permanent dummy node and storing real values starting at dummy.next. The list then has the form

dummy → [v₁] → [v₂] → ... → [vₙ] → None

Now every real node has a predecessor, so every insertion and deletion uses the same code path. The cost is a single permanent node (16-32 extra bytes for the lifetime of the list). Linux's kernel-internal list (struct list_head) uses a sentinel for exactly this reason: the kernel cannot afford special cases sprinkled across hundreds of subsystems.

When to reach for sentinels: if your list participates in many insert/delete code paths (think: free lists, kernel lists, intrusive lists in C), the sentinel pattern pays for itself in readability after the second or third call site. For a one-off list in a script, the explicit if head is None check is fine.

In-Place Reversal — Step by Step

Reversing a singly linked list in $O(n)$ time and $O(1)$ extra space is the canonical linked-list interview problem and a microcosm of the entire data structure. The algorithm walks the list once, flipping every .next to point backward. Three named pointers carry the state: prev, curr, and nxt.

🐍python

1def reverse(head):
2    prev = None
3    curr = head
4    while curr is not None:
5        nxt = curr.next      # save successor BEFORE we clobber it
6        curr.next = prev     # flip this node's pointer
7        prev = curr          # advance the lagging pointer
8        curr = nxt           # advance the leading pointer
9    return prev              # new head

The loop body is the entire algorithm, and the order of those four lines is non-negotiable. Trace it on 1 → 2 → 3 → None:

State	prev	curr	nxt	list seen from new head
initial	None	1	—	(building)
after iter 1	1	2	2 (saved)	1 → None
after iter 2	2	3	3 (saved)	2 → 1 → None
after iter 3	3	None	None (saved)	3 → 2 → 1 → None
return prev	—	—	—	head = 3 → 2 → 1 → None

Why save nxt first? Line 2 of the loop body overwrites curr.next. If we hadn't already stashed it in nxt, line 4 would have no way to reach the rest of the list. This is the lost-pointer bug, and it's eliminated by always saving before clobbering. Most linked-list bugs are some variation on this rule.

A Complete SinglyLinkedList in Python

Here is the full class. Every method is annotated below; every line of the algorithm is explained. Methods are grouped: queries (__len__, is_empty, find), mutators (prepend, append, insert_after, delete_head, delete_value, reverse), and Python protocol (__iter__, to_list).

SinglyLinkedList — production-grade Python

🐍python

Explanation(44)

Code(93)

1Node class — the building block

A Node bundles a value and a single forward pointer (next). This is the entire structural commitment of a singly linked list: every node has exactly one outgoing arrow.

2Node constructor

value is the payload; nxt defaults to None so Node(7) creates an isolated tail-style node. Naming it nxt (not next) avoids shadowing Python's built-in next().

3Store the payload

Attaches the value to the instance. CPython stores a reference, not a copy, so even huge objects cost a constant 8 bytes per slot.

4Store the forward pointer

self.next is the only structural field. Every algorithm in this class manipulates this attribute and nothing else.

6SinglyLinkedList class

The list owns three pieces of metadata: head (front pointer), tail (back pointer), and size (cached length). Those three are the entire ADT state — every operation maintains them as invariants.

8Empty state

A fresh list has no nodes. head and tail are both None; size is 0. Invariant: head is None iff tail is None iff size == 0.

9Tail pointer is the speed trick

Without this pointer, append walks the whole list to find the end (O(n)). With it, we splice in O(1). The price: every operation that touches the last node must update tail.

EXAMPLE

head -> [1] -> [2] -> [3] -> None
                       ^tail

10Cached size

Counting nodes on demand is O(n). Storing size makes len(list) O(1). The cost is one increment/decrement on every insert/delete — well worth it.

12__len__ — Pythonic length

Implementing __len__ lets users write len(my_list). Returning the cached size is O(1).

15is_empty

Single source of truth: head is None. Don't test size == 0 here — if some buggy code path forgot to update size, head being None is still authoritative.

18prepend — insert at head, O(1)

The new node's next is wired to the OLD head BEFORE we move head. This ordering is the canonical safe-insert idiom: wire outgoing arrows first, then redirect existing ones.

LOOP TRACE · 4 iterations

lst = []

head = None

tail = None

size = 0

prepend(3)

head = node(3)

tail = node(3)

size = 1

prepend(2)

head = node(2)

tail = node(3)

size = 2

prepend(1)

head = node(1)

tail = node(3)

size = 3

19Build the new node first

Node(value, self.head) constructs the newcomer with its next already aimed at the current head. The list is still consistent at this moment — the new node is not yet reachable from head.

20Redirect head — the commit

This single assignment is the moment the list logically grows. Until this line runs, the new node is invisible to readers; after it, the new node is the front.

21Empty-list edge case

If the list was empty before, the new node is also the tail. Forgetting this leaves tail dangling at None and breaks the next append.

23Bookkeeping

Maintain the size invariant. Always update size in the same function that mutates head/tail — never in two separate places.

25append — insert at tail, O(1)

Thanks to the tail pointer, append never walks the list. Without that pointer, this method becomes O(n) — and calling append in a loop becomes accidentally O(n^2).

26Build the new tail node

node.next defaults to None — exactly what a tail must be. We don't need to set it explicitly.

27Empty-list branch

If tail is None the list was empty, so head must also be set to the new node. Otherwise head stays where it was and we splice from the old tail.

29Splice from old tail

self.tail.next = node attaches the newcomer to the old tail in one assignment. This is the line that requires the tail pointer to exist — without it we'd traverse from head to find the last node.

31Move tail forward

After every successful append the tail pointer must advance to the new last node. Skipping this line is the most common subtle bug: appends seem to work but later operations corrupt the list.

34insert_after — splice in O(1)

Given a reference to a node already in the list, we insert immediately after it without any traversal. This is where linked lists beat arrays: O(1) middle insertion when you already hold the position.

EXAMPLE

before: ... -> [A] -> [C] -> ...
after:  ... -> [A] -> [B] -> [C] -> ...

37Three-line splice

Build new node aimed at prev_node's successor, then redirect prev_node's next to the new node. Two pointer rewrites, zero traversal.

39Tail edge case

If we inserted after the old tail, the new node IS the new tail. This is the only case where insert_after touches the tail pointer.

43delete_head — O(1)

Deleting the head is the cheapest mutation a singly linked list offers: just move head one hop. We return the removed value so callers can use the list as a stack/queue.

47Advance head

head = head.next discards the front node. In Python the freed node becomes garbage when its refcount drops to zero — we don't free explicitly. In C, this is where you'd call free().

48Last-node edge case

If we just removed the only node, head is now None and tail must be cleared. Forgetting this leaves tail pointing at a node that's no longer in the list.

53delete_value — the two-pointer walk

We track BOTH the current node and its predecessor. When we find the target, prev.next = curr.next unlinks it in one pointer rewrite. The two-pointer pattern is the canonical idiom whenever a singly linked list mutation needs to reach 'the previous node'.

LOOP TRACE · 3 iterations

start

prev = None

curr = node(1)

step 1

prev = node(1)

curr = node(2)

step 2 (match)

prev = node(2)

curr = node(3)

54Initialize the lagging pointer

prev is None at the start because the head has no predecessor. This special case is exactly why the two-pointer walk needs to branch on prev is None below.

55Walk while not found

The loop hops both pointers in lockstep until either we run off the end (curr is None) or we match. The tuple assignment prev, curr = curr, curr.next swaps them safely in one step — the right-hand side is evaluated first, so we never lose a pointer.

57Not found

If curr is None we walked the whole list. Return False so the caller can distinguish 'not present' from 'removed'.

59Head case

If prev is None the target was the head, so we move head forward instead of rewriting prev.next. Mishandling this is the #1 linked-list bug.

61General case — the unlink

prev.next = curr.next splices curr out of the chain. After this line nothing in the list reaches curr; CPython will reclaim it on the next GC cycle.

62Tail edge case

If we removed the tail, the new tail is prev (which may be None if the list became empty). Forgetting this leaves tail dangling.

67find — linear scan

Singly linked lists offer no shortcut for search. find walks the chain hop by hop, returning the first matching node or None. Worst-case O(n).

74reverse — in-place pointer flip

The canonical algorithm. We walk the list once and reverse every next pointer. The new head is whatever was the old tail. Three named pointers — prev, curr, nxt — are enough; no extra storage, O(n) time, O(1) extra space.

LOOP TRACE · 5 iterations

start: 1->2->3

prev = None

curr = node(1)

nxt = ?

after iter 1

prev = node(1)

curr = node(2)

nxt = node(3)

after iter 2

prev = node(2)

curr = node(3)

nxt = None

after iter 3

prev = node(3)

curr = None

nxt = None

head = prev

head = node(3) -> 2 -> 1 -> None

75Tail becomes the old head

Before we mutate any pointers we record this fact: the front node will end up at the back. Updating tail before the loop is cleaner than tracking it inside.

76Loop entry condition

We process every node exactly once. The loop terminates when curr falls off the end (becomes None).

77Save the next pointer FIRST — don't lose it

This single line is the algorithm's secret. The very next line (curr.next = prev) is about to overwrite curr.next — if we hadn't stashed it in nxt we'd have no way to reach the rest of the list. This is the lost-pointer bug, and it's eliminated by always saving before clobbering.

78Flip the pointer

curr.next = prev is the actual reversal. The current node now points backward. Notice prev was None on iteration 1 — that correctly makes the old head's next become None (it's the new tail).

79Advance prev

prev catches up to where curr was. After this assignment the reversed prefix grows by one node.

80Advance curr

curr moves to the saved next. We restored the forward link's role from the stash we made on line 77. The unprocessed suffix shrinks by one node.

81Install the new head

After the loop, curr is None and prev points at what used to be the tail. That's the new head. One assignment installs the reversed list.

83__iter__ — make it a Python iterable

Implementing __iter__ as a generator lets users write 'for v in lst:' and 'list(lst)'. Each yield emits one value and pauses the function until the next iteration.

89to_list — eager copy

list(self) drains the iterator into a Python list. Useful for printing, equality checks, and tests. O(n) time and O(n) extra space.

49 lines without explanation

1class Node:
2    def __init__(self, value, nxt=None):
3        self.value = value
4        self.next = nxt
5
6class SinglyLinkedList:
7    def __init__(self):
8        self.head = None
9        self.tail = None      # tail pointer makes append O(1)
10        self.size = 0
11
12    def __len__(self):
13        return self.size
14
15    def is_empty(self):
16        return self.head is None
17
18    def prepend(self, value):
19        node = Node(value, self.head)
20        self.head = node
21        if self.tail is None:
22            self.tail = node
23        self.size += 1
24
25    def append(self, value):
26        node = Node(value)
27        if self.tail is None:
28            self.head = node
29        else:
30            self.tail.next = node
31        self.tail = node
32        self.size += 1
33
34    def insert_after(self, prev_node, value):
35        if prev_node is None:
36            raise ValueError("prev_node must not be None")
37        node = Node(value, prev_node.next)
38        prev_node.next = node
39        if prev_node is self.tail:
40            self.tail = node
41        self.size += 1
42
43    def delete_head(self):
44        if self.head is None:
45            return None
46        removed = self.head.value
47        self.head = self.head.next
48        if self.head is None:
49            self.tail = None
50        self.size -= 1
51        return removed
52
53    def delete_value(self, target):
54        prev, curr = None, self.head
55        while curr is not None and curr.value != target:
56            prev, curr = curr, curr.next
57        if curr is None:
58            return False
59        if prev is None:
60            self.head = curr.next
61        else:
62            prev.next = curr.next
63        if curr is self.tail:
64            self.tail = prev
65        self.size -= 1
66        return True
67
68    def find(self, target):
69        curr = self.head
70        while curr is not None:
71            if curr.value == target:
72                return curr
73            curr = curr.next
74        return None
75
76    def reverse(self):
77        prev, curr = None, self.head
78        self.tail = self.head
79        while curr is not None:
80            nxt = curr.next
81            curr.next = prev
82            prev = curr
83            curr = nxt
84        self.head = prev
85
86    def __iter__(self):
87        curr = self.head
88        while curr is not None:
89            yield curr.value
90            curr = curr.next
91
92    def to_list(self):
93        return list(self)

Driver session that exercises every method:

🐍python

1>>> lst = SinglyLinkedList()
2>>> lst.append(1); lst.append(2); lst.append(3)
3>>> lst.to_list()
4[1, 2, 3]
5>>> lst.prepend(0)
6>>> lst.to_list()
7[0, 1, 2, 3]
8>>> lst.delete_value(2)
9True
10>>> lst.to_list()
11[0, 1, 3]
12>>> lst.reverse()
13>>> lst.to_list()
14[3, 1, 0]
15>>> len(lst), lst.is_empty()
16(3, False)

Modern C++ with unique_ptr Ownership

The same ADT in modern C++ teaches a lesson Python hides: ownership. In C, a singly linked list is a parade of malloc/free calls and every bug is a memory bug — double-free, use-after-free, leak, dangling pointer. In modern C++ we encode ownership in the type system with std::unique_ptr: each node owns its successor, and the destructor chain frees the entire list automatically when the head is destroyed.

SinglyLinkedList — modern C++ with std::unique_ptr

📄cpp

Explanation(25)

Code(70)

5Generic over the value type

template<class T> makes the list reusable for any payload type without rewriting it. The compiler stamps out one specialization per T you instantiate.

6Class wraps the data structure

Encapsulation: head_, tail_, and size_ are private. Public operations are the only way to touch them, so invariants stay safe.

7Nested Node struct — implementation detail

Defining Node inside the class hides it from outside code. Users of SinglyLinkedList<int> never need to mention Node — that's a feature.

9unique_ptr<Node> next — ownership encoded in the type

Each node OWNS its successor. When a node is destroyed its unique_ptr destructor automatically destroys the next node, which destroys the next, and so on. No manual delete, no leaks. This is the modern C++ replacement for raw 'Node* next'.

10std::move into the value

std::move(v) hands the parameter's resources into self.value without copying. For T=string this matters: a copy duplicates the heap buffer; a move just steals the pointer.

13head_ owns the entire chain

Because each next is a unique_ptr, head_ transitively owns every node. Destroying the list (e.g., when SinglyLinkedList goes out of scope) destroys every node automatically.

EXAMPLE

head_ -> [1|.] -> [2|.] -> [3|.] -> nullptr
         ^owner   ^owner   ^owner

14tail_ is a NON-owning raw pointer

If tail_ were also a unique_ptr we'd have two owners of the last node — a double-free bug. tail_ is a raw observer; ownership lives only along the head_ chain.

21prepend — O(1) front insert

Same algorithm as Python, but we manage ownership transfers explicitly with std::move.

22make_unique allocates the node

make_unique<Node>(std::move(v)) is the safe, exception-correct way to allocate. It also avoids the slight pessimization of 'unique_ptr<Node>(new Node(...))'.

23Wire newcomer to old head FIRST

node->next = std::move(head_) transfers ownership of the entire current list into the new node. After this line, head_ is null and the new node owns the chain.

24Empty-list tail edge case

If tail_ was null we just inserted the only node; tail_ must be set to its raw address. node.get() returns the raw pointer without affecting ownership.

25Commit: install the new head

head_ = std::move(node) makes the new node the front of the list. node is now empty (moved-from); the unique_ptr's destructor will run on it but with no owned object.

30append — O(1) thanks to tail_

We splice from tail_ in constant time. Without tail_, we'd walk head_->next->next->... which is O(n) per call.

32Cache the raw pointer BEFORE the move

node.get() must be called while node still owns the object. After std::move(node), node is empty and node.get() would be nullptr.

38delete_value — two-pointer walk in C++

Same algorithm as Python's delete_value, but pointers are explicit. prev and curr are raw observers; ownership stays in the unique_ptr chain.

41Walk both pointers in lockstep

curr->next.get() peeks through the unique_ptr to read the raw pointer without taking ownership. The chain is unchanged during the search.

47Move ownership of the doomed node into a local

We extract the unique_ptr that owned curr into a local variable. When the local goes out of scope at the end of this function, the node is freed automatically — no explicit delete.

50Splice the chain past the doomed node

doomed->next still owns curr's successor. We move that ownership back into prev->next (or head_), reconnecting the chain in O(1).

53Update tail if we removed the last node

Same edge case as Python. If curr was the tail, the new tail is prev (which may be null).

55Automatic cleanup

When this function returns, doomed's destructor runs. unique_ptr deletes the node, which has no owned next anymore — so the destruction is bounded, not recursive into the rest of the list.

58reverse — same algorithm, ownership-aware

We slide unique_ptrs around instead of rewriting raw pointers. The dance is identical to Python's reverse, but every step transfers ownership cleanly.

61Take ownership of the chain into curr

std::move(head_) leaves head_ empty and gives curr full ownership of every remaining node. We will rebuild head_ at the end.

64Save next BEFORE clobbering

Same lost-pointer rule as Python. std::move(curr->next) extracts ownership of the suffix into nxt before we overwrite curr->next on the next line.

65Flip the pointer (with ownership)

curr->next = std::move(prev). The current node now owns the reversed prefix. C++ enforces single-ownership at compile time — you literally cannot create a cycle by accident here.

68Install the new head

After the loop, prev owns the entire reversed list. We move it into head_ in one O(1) step.

45 lines without explanation

1#include <iostream>
2#include <memory>
3#include <utility>
4
5template <class T>
6class SinglyLinkedList {
7    struct Node {
8        T value;
9        std::unique_ptr<Node> next;
10        explicit Node(T v) : value(std::move(v)), next(nullptr) {}
11    };
12
13    std::unique_ptr<Node> head_;
14    Node* tail_ = nullptr;       // raw, non-owning back pointer
15    std::size_t size_ = 0;
16
17public:
18    bool empty() const noexcept { return !head_; }
19    std::size_t size() const noexcept { return size_; }
20
21    void prepend(T v) {
22        auto node = std::make_unique<Node>(std::move(v));
23        node->next = std::move(head_);
24        if (!tail_) tail_ = node.get();
25        head_ = std::move(node);
26        ++size_;
27    }
28
29    void append(T v) {
30        auto node = std::make_unique<Node>(std::move(v));
31        Node* raw = node.get();
32        if (!head_)         head_ = std::move(node);
33        else                tail_->next = std::move(node);
34        tail_ = raw;
35        ++size_;
36    }
37
38    bool delete_value(const T& target) {
39        Node* prev = nullptr;
40        Node* curr = head_.get();
41        while (curr && curr->value != target) {
42            prev = curr;
43            curr = curr->next.get();
44        }
45        if (!curr) return false;
46
47        std::unique_ptr<Node> doomed =
48            prev ? std::move(prev->next) : std::move(head_);
49
50        if (prev) prev->next = std::move(doomed->next);
51        else      head_      = std::move(doomed->next);
52
53        if (curr == tail_) tail_ = prev;
54        --size_;
55        return true;            // doomed deletes itself here
56    }
57
58    void reverse() {
59        std::unique_ptr<Node> prev = nullptr;
60        std::unique_ptr<Node> curr = std::move(head_);
61        tail_ = curr.get();
62        while (curr) {
63            std::unique_ptr<Node> nxt = std::move(curr->next);
64            curr->next = std::move(prev);
65            prev = std::move(curr);
66            curr = std::move(nxt);
67        }
68        head_ = std::move(prev);
69    }
70};

The ownership rule in one sentence: the unique_ptr chain owns; the tail_ raw pointer observes. Two owners of the same node would be a double-free; one owner plus any number of raw observers is correct.

Interactive: Singly Linked List Lab

Drive every method by hand. Each operation animates the affected nodes — cyan for newcomers, rose for deletions, amber for finds, orange for pointer rewrites. The reverse (step) button performs the canonical algorithm one pointer-flip at a time, marking prev in green, curr in amber, and nxt in violet so you can watch the three-cursor dance end to end.

Singly Linked List Lab — head, optional tail, and pointer rewriting

size = 3

insert valuefind valuedelete value

head -> 1 -> 2 -> 3 -> None (size=3)

Try the canonical exercises in this order:

Append three values, then delete the head once. Watch the size and head update in O(1).
Delete a value that lives in the middle. The two-pointer walk shows up in the log: the cost reads O(k) where k is the index of the match.
Click "reverse (step)" repeatedly on a list of 4 nodes. Confirm that prev climbs from None up the list while curr falls off the back. After the last step, head = prev installs the reversed list.
Find a value that isn't there. The log shows O(n) walked all — an unsuccessful search has the same cost as a worst-case successful one.

Asymptotic Comparison vs Array

The asymptotic table tells half the story; the constant-factor table tells the rest. Big-O hides the cost of cache misses, and on real CPUs that cost dwarfs the structural difference for small $n$ .

Operation	Dynamic Array	Singly Linked List	Winner
Random access lst[i]	O(1)	O(n)	array (by an order of magnitude)
Append at end	O(1) amortized	O(1) with tail ptr	tie
Prepend at front	O(n) (shift)	O(1)	list
Insert at known node/index	O(n) (shift)	O(1) with node, O(i) by index	list (when you hold the node)
Delete at known node	O(n) (shift)	O(1) with predecessor	list
Search by value	O(n)	O(n)	tie asymptotically; array wins on cache
Memory per element	≈ sizeof(T)	sizeof(T) + 8-16 (next ptr) + allocator overhead	array (≈ 2-3× denser)
Cache locality	excellent (contiguous)	poor (each node is its own heap chunk)	array (often 5-20× faster scan)
Reallocation cost	occasional O(n) copy	none — nodes never move	list (when stable addresses matter)
Iterator stability under mutation	invalidated on resize	stable as long as node lives	list

The cache-locality fact deserves emphasis: on a modern machine a sequential scan over a contiguous array of

10^6

32-bit ints runs at near memory-bandwidth speed (often a few milliseconds). The same data in a linked list, with each node fetched from a random heap address, can be 5–20× slower because every .next dereference is a cache miss. Choose linked lists for their structural advantages, not for raw scan throughput.

Where Singly Linked Lists Run in Production

Singly linked lists are everywhere a system needs cheap insertion and doesn't need random access. A non-exhaustive tour of places this exact data structure runs on every machine you own:

The Linux kernel uses intrusive singly-linked lists (struct hlist_head) for hash-table chaining in the page cache, dentry cache, and futex hash. The singly-linked variant saves one pointer per node — multiplied by millions of dentries, that is tens of MB of kernel memory.
Hash table buckets in essentially every language runtime: Python's old-style collisions, Java's HashMap at low load factors, Go's map overflow buckets, Redis's dictionary. A bucket is a singly linked list of (key, value) entries.
Adjacency lists in graphs. Each vertex stores a singly linked list of its outgoing edges. BFS and DFS (Chapter 17) walk these lists without needing random access, so the linear-only access pattern is fine.
Memory allocators (jemalloc, tcmalloc, ptmalloc, and every kernel slab allocator) keep free lists: a singly linked list of available chunks. Allocation pops the head (O(1)); deallocation pushes onto the head (O(1)).
LISP, Scheme, OCaml, Erlang, Haskell. The list is the primary native data structure. cons cells are nodes; the "head" of a list is its car; the rest is its cdr. The whole functional-programming idiom of pattern-matching [head, ...tail] rests on this representation.
Operating-system process control blocks. The scheduler keeps runnable processes in a singly linked list per priority class; context switches dequeue from the head.
Async task queues (Java's ConcurrentLinkedQueue, libuv's pending-callback queue, Tokio's task queue): lock-free singly linked lists with atomic compare-and-swap on the head/tail pointers.
Music playlists with only "next track" semantics (no history): a singly linked list. Want a history button? Upgrade to a doubly linked list (next section).
Stack frames in CPS-transformed compilers. Continuation-passing style explicitly represents the call stack as a singly linked list of activation records on the heap.
Undo logs for transactional storage engines (SQLite's rollback journal, Postgres's xlog buffers): each transaction prepends a record describing how to undo the change.

Pitfalls and How to Avoid Them

Pitfall	Symptom	Fix
Forgetting to update head when deleting the head	Old head node still reachable after delete; size and content desync	Branch on `prev is None` and reassign head explicitly
Lost-pointer bug in reverse (clobber next before saving)	List truncates after first iteration; only one node remains	ALWAYS save curr.next into nxt BEFORE writing curr.next = prev
Memory leak in C when removing without free()	Heap grows unboundedly under repeated insert/remove	Always `free(doomed)` after unlinking; in C++ use unique_ptr to make it automatic
append called in a loop without a tail pointer	O(n^2) performance; building a 100k-element list takes seconds	Maintain a tail pointer; or build with prepend then reverse once
Forgetting to update tail after delete_value removes the last node	Next append writes into a node not in the list; later traversal corrupted	After unlink, check `if curr is self.tail: self.tail = prev`
Concurrent modification during iteration	Iterator returns deleted values, skips inserted ones, or segfaults in C	Don't share singly linked lists across threads without a lock; or use a lock-free variant
Comparing nodes with == instead of `is`	Confuses identity (same node) with equality (same value); subtle bugs in delete logic	Use `is` / `is not` for node identity; reserve `==` for value comparison
Building a cycle by accident	find / iter / __len__ never terminates; CPU hits 100%	Never assign a later node into an earlier node's next pointer; Floyd's tortoise-and-hare detects cycles in O(n) if you suspect one

Quick Checks

Quick Check

You have head -> 1 -> 2 -> 3 -> 4 -> None. You run the canonical in-place reverse. After EXACTLY two iterations of the while loop have completed, what are the values of prev, curr, and the relevant pointer state?

Quick Check

A teammate's SinglyLinkedList has head and size but NO tail pointer. They call append in a tight loop to build a list of n elements. What is the total cost?

Singly linked lists give you $O(1)$ insert and delete at any node you already hold, a stable iterator under mutation, and a footprint that scales linearly without ever copying. They lose random access and cache locality. The next two structural variants — doubly linked lists (Section 6.3) and circular linked lists (Section 6.4) — trade extra memory for backward traversal and sentinel-free wraparound. Section 6.5 then revisits the array-vs-list comparison with measured benchmarks instead of asymptotic hand-waving.