Chapter map

Where this sits in CS 300. Chapter 3 named the seven data structures; chapter 4 picks one family — linear, ordered collections — and builds it end-to-end, twice (pointer-based and array-based). Everything you learn here about cost is a function of memory layout transfers verbatim to trees (ch. 6), heaps, and graph adjacency lists (opt. ch. 10).

What you add to your toolkit here:

Pointer-based lists. Singly linked (SLL) and doubly linked (DLL); append, prepend, insert-after, remove, search, traverse. You can write these from scratch, by hand.
Sentinel / dummy-node idiom. The trick that collapses “first / middle / last” special cases into one uniform case.
Three restricted list ADTs: Stack (LIFO), Queue (FIFO), Deque (both ends) — each built on linked lists or arrays.
Array-based lists. The std::vector cost model (amortized $O(1)$ back, $O(n)$ insert/erase elsewhere) contrasted cleanly with the linked-list cost model.
A decision framework (see 4.18+) for picking between array-based, SLL, DLL, and sentinel-DLL. This is the question that actually shows up on assignments.

Mastery checklist — you should be able to, without references:

Draw an SLL of 3 nodes and execute insertAfter and remove on it by redrawing the pointers one step at a time.
Write the node struct for an SLL and a DLL; write append, prepend, insertAfter, remove, and search for both.
Explain why remove on an SLL requires the predecessor’s pointer, and how DLL gets around it.
State the cost of every List-ADT operation on (a) SLL, (b) DLL, (c) array-based list — without guessing. Know why each one is what it is.
Implement Stack, Queue, and Deque on both a linked list and an array, and argue which backing data structure you’d pick for each.
Rewrite an SLL method that has a 3-case switch (empty / head / middle) to use a sentinel node and collapse to one case.
Traverse a linked list iteratively and recursively; know when recursion blows the stack.
Given a workload description (“mostly appends, rare middle removals, needs $O(1)$ random access”), pick the right list variant and justify.

Looking ahead. Chapter 5 moves from linear to keyed storage (hash tables), but the pointer-chasing mental model you’re building here is exactly what hash-table chaining uses internally. Chapter 6 (trees) extends the node + pointer idiom from one “next” pointer to two (“left” / “right”); the whole tree chapter will feel like a generalization of this one.

4.1 The List ADT

Chapter 3 surveyed the seven fundamental data structures and the nine common abstract data types, then spent most of its energy on searching and sorting. Chapter 4 starts the depth-first tour: each ADT gets its own chapter where we define the contract, implement it, and analyze the operations. First up: the list.

The list is the workhorse ADT. Nearly every other sequence-based structure (stack, queue, deque) is a list with additional constraints. Understanding what a list’s contract actually is — and what it deliberately leaves unspecified — is the first step to picking the right structure later.

The contract: operations

::: center Operation What it does Example (start: 99, 77)

Append(L, x) Insert $x$ at the end Append(L, 44) $\Rightarrow$ 99, 77, 44 Prepend(L, x) Insert $x$ at the front Prepend(L, 44) $\Rightarrow$ 44, 99, 77 InsertAfter(L, w, x) Insert $x$ immediately after $w$ InsertAfter(L, 99, 44) $\Rightarrow$ 99, 44, 77 Remove(L, x) Remove first occurrence of $x$ Remove(L, 77) $\Rightarrow$ 99 Search(L, x) Return item (or null) Search(L, 99) $\Rightarrow$ 99; Search(L, 22) $\Rightarrow$ null Print(L) Print items in order “99, 77” PrintReverse(L) Print items in reverse order “77, 99” Sort(L) Sort items ascending 77, 99 IsEmpty(L) True iff list has no items false for (99, 77) GetLength(L) Number of items 2 :::

What the contract doesn’t say

Two interface families: Sequence and Set

Step back one level. Every container ADT in CS 300 belongs to one of two families, distinguished by where the order of items lives:

Sequence interface. Items have an extrinsic order --- the caller chose where each item goes. Operations are positional: get_at(i), set_at(i,x), insert_at(i,x), insert_first/last(x), delete_first/last(). This chapter implements Sequence. List, stack, queue, and deque are all Sequence with restricted operation sets.
Set interface. Items have an intrinsic order determined by a key. Operations are key-based: find(k), insert(x), delete(k), and ordered ops like find_min(), find_next(k). ch. 5 (hash tables) and ch. 6 (BSTs) implement Set.

The framing is from MIT 6.006. It explains why the chapter map is the shape it is: ch. 4 builds Sequence implementations end-to-end, then ch. 5—ch. 6 swap the interface and rebuild from scratch. Pick the right family first; pick the implementation second.

List is the root ADT; stacks and queues restrict it

C++: `std::list`, `std::vector`, `std::forward_list`

C++ gives you several list-like containers. All three satisfy the list ADT; they differ in which operations are cheap and what extra features they offer.

Three takes on ``list'' in C++

#include <vector>
#include <list>
#include <forward_list>

std::vector<int>        v = {7, 9, 5};   // dynamic array
std::list<int>          l = {7, 9, 5};   // doubly linked list
std::forward_list<int>  f = {7, 9, 5};   // singly linked list

v.push_back(44);                 // O(1) amortized (append)
l.push_back(44);                 // O(1)
// f has no push_back!           // forward_list is single-link only

v.insert(v.begin(), 44);         // O(n) (prepend: shifts everything)
l.push_front(44);                // O(1)
f.push_front(44);                // O(1)

int len_v = v.size();            // O(1)
int len_l = l.size();            // O(1)
// f.size() doesn't exist; forward_list doesn't track length

::: center Operation std::vector std::list std::forward_list

Append at end $O(1)$ amortized $O(1)$ no direct op Prepend at front $O(n)$ $O(1)$ $O(1)$ Insert after a known position $O(n)$ $O(1)$ $O(1)$ Indexed access v[i] $O(1)$ $O(i)$ $O(i)$ Search by value $O(n)$ $O(n)$ $O(n)$ size() $O(1)$ $O(1)$ not provided :::

What this chapter builds

4.2 Singly Linked Lists: Append and Prepend

This is the first concrete implementation of the list ADT: the singly linked list. Instead of storing items in a contiguous block of memory (like an array), a linked list scatters them across individually-allocated nodes that “point” to each other. The payoff is cheap insertion and deletion at known positions; the price is slower traversal and higher per-item memory overhead.

The node type in C++

A node and a list wrapper

struct Node {
    int   data;
    Node* next;

    Node(int d) : data(d), next(nullptr) {}
};

struct LinkedList {
    Node* head = nullptr;
    Node* tail = nullptr;
};

head is how the list knows where to start; tail is the optimization that lets append run in $O(1)$ without walking the list. An empty list has both set to nullptr.

Append: add at the end

Two cases: an empty list needs its head and tail both pointed at the new node; a non-empty list only has to reach through the existing tail.

append

void append(LinkedList& list, Node* newNode) {
    if (list.head == nullptr) {          // empty list
        list.head = newNode;
        list.tail = newNode;
    } else {                              // non-empty list
        list.tail->next = newNode;        // stitch on the end
        list.tail       = newNode;        // advance tail
    }
}

Prepend: add at the front

Symmetric to append, but we touch head instead of tail.

prepend

void prepend(LinkedList& list, Node* newNode) {
    if (list.head == nullptr) {          // empty list
        list.head = newNode;
        list.tail = newNode;
    } else {                              // non-empty list
        newNode->next = list.head;        // point new node at old head
        list.head     = newNode;          // new node is the new head
    }
}

Cost summary

::: center Operation Singly linked list Why

append $O(1)$ with tail pointer Two writes; no traversal prepend $O(1)$ Two writes; no traversal :::

Both basic insertions are constant time. That’s the primary advantage of a linked list over an array for workloads that repeatedly add at the ends.

Language conventions for “null”

What’s coming next

4.3 Singly Linked Lists: Insert-After

Append and prepend covered the two endpoints. Insert-after is the general case: given a pointer to some existing node curNode, splice a newNode in right after it. The operation is still $O(1)$ — because we already have a pointer to the splice point — but the bookkeeping has to handle three cases instead of two.

The three cases

The pseudocode looks like it’s handling three unrelated scenarios, but they all flow from the same question: which of the list’s invariants does this insertion threaten?

::: center Case What needs updating

Empty list Both head and tail curNode is the tail Tail’s next pointer, and tail itself curNode is interior Just two next pointers (no head/tail changes) :::

The algorithm

insertAfter

void insertAfter(LinkedList& list, Node* curNode, Node* newNode) {
    if (list.head == nullptr) {                  // Case 1: empty list
        list.head = newNode;
        list.tail = newNode;
    }
    else if (curNode == list.tail) {              // Case 2: after tail
        list.tail->next = newNode;
        list.tail       = newNode;
    }
    else {                                         // Case 3: interior
        newNode->next = curNode->next;
        curNode->next = newNode;
    }
}

Picture of the interior splice

::: center Before:
... $\to$ [curNode | $\bullet$ ] $\to$ [nextNode | ...] $\to$ ...
Step 1: newNode $\to$ next = curNode $\to$ next
... $\to$ [curNode | $\bullet$ ] $\to$ [nextNode | ...] $\to$ ...
$\nwarrow$
[newNode | $\bullet$ ]
Step 2: curNode $\to$ next = newNode
... $\to$ [curNode | $\bullet$ ] $\to$ [newNode | $\bullet$ ] $\to$ [nextNode | ...] $\to$ ... :::

Two pointer writes, no scan. Constant time.

Why we need the curNode argument

Mapping to `std::list`

The STL version

#include <list>
std::list<int> l = {7, 9, 5};

auto it = std::next(l.begin(), 1);   // iterator to the "9"
l.insert(it, 42);                    // inserts *before* it: 7, 42, 9, 5

auto it2 = std::next(l.begin(), 1);  // iterator to the "42"
l.insert(std::next(it2), 100);       // inserts before "9": 7, 42, 100, 9, 5

std::list::insert(pos, x) inserts before pos. To insert after a position, pass std::next(pos). The STL picks “before” because that’s what pos = end() naturally means — insert at the end. Under the hood it’s the same two-pointer splice, just with a doubly linked list.

Cost

::: center Operation Singly linked list Why

insertAfter(curNode, …) $O(1)$ Two pointer writes; no scan Find curNode by value or index $O(n)$ Walk from head Insert by index $k$ $O(k) + O(1) = O(n)$ Walk first, then splice :::

4.4 Singly Linked Lists: Remove

Removal in a singly linked list has the same shape of problem as insertion: you need to update a next pointer that lives in the predecessor of the node you want to delete — and a singly linked list doesn’t make that predecessor easy to reach. The workaround is the same one used by insertAfter: name the operation RemoveAfter, and make the caller pass the predecessor pointer.

Why predecessor-based removal?

The three cases

Two variables carry the state of the splice:

curNode — the node before the one being removed (or null if we’re removing the head).
sucNode — the node after the one being removed (i.e., the new successor that the splice will connect to).

::: center Case What gets updated

Remove the head (curNode null) head moves to successor; if that’s null, also null out tail. Remove an interior node curNode $\to$ next moves to successor. No endpoint changes. Remove the tail (curNode $\to$ next $\to$ next null) curNode $\to$ next becomes null; also move tail to curNode. :::

The algorithm

removeAfter

void removeAfter(LinkedList& list, Node* curNode) {
    // Case A: remove the head
    if (curNode == nullptr && list.head != nullptr) {
        Node* toFree = list.head;
        Node* sucNode = list.head->next;
        list.head = sucNode;
        if (sucNode == nullptr) {        // list is now empty
            list.tail = nullptr;
        }
        delete toFree;
        return;
    }

    // Case B / C: remove the node after curNode (if one exists)
    if (curNode != nullptr && curNode->next != nullptr) {
        Node* toFree = curNode->next;
        Node* sucNode = curNode->next->next;
        curNode->next = sucNode;
        if (sucNode == nullptr) {        // we just removed the tail
            list.tail = curNode;
        }
        delete toFree;
    }
}

The textbook’s pseudocode omits the delete. In real C++ you must free the removed node, or you leak memory. Python, Java, and JavaScript’s garbage collectors would do it for you; C++ makes you explicit.

Picture of the interior splice

::: center Before:
... $\to$ [curNode | $\bullet$ ] $\to$ [victim | $\bullet$ ] $\to$ [sucNode | ...] $\to$ ...
After curNode $\to$ next = sucNode:
... $\to$ [curNode | $\bullet$ ] $\to$ [sucNode | ...] $\to$ ...
The victim node is unreachable — delete it. :::

Cost

::: center Operation Singly linked list Why

removeAfter(curNode) $O(1)$ Two pointer writes; no scan Remove by value (find + remove) $O(n)$ Linear walk to find the predecessor Remove at index $k$ $O(k) = O(n)$ Walk to position, then splice :::

Why we don’t have `Remove(node)` directly

All five SLL operations together

Now that we have append / prepend / insert-after / remove-after, we can fill in the canonical cost table for a singly linked list with both head and tail pointers:

::: center Operation Cost Assumption

append(x) $O(1)$ Tail pointer cached prepend(x) $O(1)$ — insertAfter(p, x) $O(1)$ Caller has pointer p removeAfter(p) $O(1)$ Caller has pointer p search(x) $O(n)$ Linear scan at(i) $O(i)$ Walk from head remove(x) by value $O(n)$ Search + splice :::

4.5 Linked List Search

Search on a linked list is exactly what you’d expect: start at the head, walk node-by-node following next pointers, stop when you find a match or hit null. This is linear search from Chapter 3, applied to a linked-list structure. It’s worth its own section because linked-list search exposes a recurring pattern — the walker idiom — that will be the scaffolding for traversal, reversal, length computation, and many other linked-list algorithms.

The algorithm

Node* search(const LinkedList& list, int key) {
    Node* curNode = list.head;
    while (curNode != nullptr) {
        if (curNode->data == key) {
            return curNode;
        }
        curNode = curNode->next;
    }
    return nullptr;
}

Three things to notice: the loop advances through curNode = curNode $\to$ next; the termination check is on the pointer, not the data; and we return the pointer to the node, not its index.

Why return a pointer instead of an index

Cost

::: center Case Comparisons Runtime

Key at head 1 $O(1)$ Key at position $k$ $k + 1$ $O(k)$ Key absent $n$ $O(n)$ :::

Sorting a linked list doesn't help search

On an array, sorting unlocks binary search: $O(\log n)$ . On a linked list, it does not. Even with a sorted linked list, you can’t jump to the middle element in constant time. The best you can do is stop early when a value exceeds the key (“early exit” on sorted data):

while (curNode != nullptr && curNode->data < key) {
    curNode = curNode->next;
}
return (curNode && curNode->data == key) ? curNode : nullptr;

Helpful on hits near the front; still $\Theta(n)$ worst case.

Linked-list search is hostile to CPU caches

Two common variations

Return a pointer and its predecessor

Sometimes a caller wants both the found node and the one before it — so they can immediately RemoveAfter. The idiom tracks prev alongside curNode:

std::pair<Node*, Node*> searchWithPrev(const LinkedList& list, int key) {
    Node* prev = nullptr;
    Node* cur  = list.head;
    while (cur != nullptr) {
        if (cur->data == key) return {cur, prev};
        prev = cur;
        cur  = cur->next;
    }
    return {nullptr, nullptr};
}

The prev pointer is the “trailing pointer” trick. It’s the closest a singly linked list gets to a doubly linked list’s back pointer, synthesized fresh on each walk.

Recursive search

Node* searchRec(Node* cur, int key) {
    if (cur == nullptr)        return nullptr;
    if (cur->data == key)      return cur;
    return searchRec(cur->next, key);
}

Same algorithm, recursive shape. Intellectually clean, but each call adds a stack frame — $O(n)$ recursion depth. The iterative version uses $O(1)$ stack. Prefer iterative for long lists; recursive is just for illustration or when the language (e.g. functional languages with tail-call optimization) supports it cheaply.

What search gives you

4.6 Doubly Linked Lists

The pain of a singly linked list lives at the prev pointer it doesn’t have: no cheap reverse traversal, no removal without a predecessor argument, no insertion “before” a known node. The doubly linked list spends one extra pointer per node to erase all of these problems. You get bidirectional traversal, $O(1)$ removal given the victim itself, and a cleaner (if wordier) splice operation.

The node type in C++

A DLL node

struct DNode {
    int    data;
    DNode* next;
    DNode* prev;

    DNode(int d) : data(d), next(nullptr), prev(nullptr) {}
};

struct DLinkedList {
    DNode* head = nullptr;
    DNode* tail = nullptr;
};

One extra pointer per node compared to an SLL. On a 64-bit system that’s 8 extra bytes per item; for 32-bit int data plus two 64-bit pointers, a DLL node is already 20 bytes of pointers and padding wrapping 4 bytes of data — a 5 $\times$ memory overhead versus a std::vector<int>. Bring this up when someone claims linked lists are “cheap.”

Invariants

Append

append on a DLL

void append(DLinkedList& list, DNode* newNode) {
    if (list.head == nullptr) {          // empty list
        list.head = newNode;
        list.tail = newNode;
    } else {                              // non-empty list
        list.tail->next = newNode;        // stitch forward
        newNode->prev   = list.tail;      // stitch backward
        list.tail       = newNode;        // advance tail
    }
}

Compared to the SLL version, we do one extra write: set newNode $\to$ prev = list.tail before moving the tail. Still $O(1)$ .

Prepend

Symmetric to append. Every tail becomes head; every next swaps with prev.

prepend on a DLL

void prepend(DLinkedList& list, DNode* newNode) {
    if (list.head == nullptr) {          // empty list
        list.head = newNode;
        list.tail = newNode;
    } else {                              // non-empty list
        newNode->next  = list.head;       // forward link in
        list.head->prev = newNode;        // backward link in
        list.head       = newNode;        // advance head
    }
}

What the back-pointer unlocks

When the extra pointer is not worth it

Cost of the endpoint operations

::: center Operation SLL DLL Notes

append $O(1)$ $O(1)$ One extra write on DLL prepend $O(1)$ $O(1)$ One extra write on DLL insertAfter(n) $O(1)$ $O(1)$ DLL also has insertBefore remove(n) needs prev, so $O(n)$ to find it, then $O(1)$ $O(1)$ given node DLL wins outright :::

`std::list` is a circular DLL

Where this is going

4.7 Doubly Linked Lists: Insert-After

Insert-after on a doubly linked list is the same algorithm as the SLL version from 4.3, with one extra pointer write per affected side to keep the prev links in sync. The interior case — where all four invariants meet — requires four pointer updates instead of the SLL’s two. Each of the four has to happen in the right order, and every pattern you pick here will be the template for the rest of the DLL operations.

The three cases

::: center Case Pointer writes Structures affected

Empty list 2 head, tail curNode is tail 3 tail’s next, new node’s prev, tail Interior 4 curNode’s next, sucNode’s prev, new node’s next and prev :::

The algorithm

insertAfter on a DLL

void insertAfter(DLinkedList& list, DNode* curNode, DNode* newNode) {
    if (list.head == nullptr) {                      // Case A: empty
        list.head = newNode;
        list.tail = newNode;
    }
    else if (curNode == list.tail) {                  // Case B: after tail
        list.tail->next = newNode;
        newNode->prev   = list.tail;
        list.tail       = newNode;
    }
    else {                                             // Case C: interior
        DNode* sucNode = curNode->next;
        newNode->next  = sucNode;
        newNode->prev  = curNode;
        curNode->next  = newNode;
        sucNode->prev  = newNode;
    }
}

Case C, step by step

The interior case is four pointer writes. The order is flexible, but the intent must stay consistent: wire the new node first, then redirect the existing ones. Writing the old pointers first while the new node is still dangling breaks invariants mid-flight and can get you into trouble on multi-threaded or signal-interrupted code. Safe ordering:

::: center Step Write

1 newNode $\to$ next = curNode $\to$ next (remember the successor first) 2 newNode $\to$ prev = curNode (wire the predecessor) 3 curNode $\to$ next = newNode (splice forward) 4 sucNode $\to$ prev = newNode (splice backward) :::

Picture of the interior splice

::: center Before:
... $\leftrightarrow$ [curNode] $\leftrightarrow$ [sucNode] $\leftrightarrow$ ...
After:
... $\leftrightarrow$ [curNode] $\leftrightarrow$ [newNode] $\leftrightarrow$ [sucNode] $\leftrightarrow$ ... :::

Four arrows redirected. Nothing else changes — the head, the tail, and any nodes further away are untouched.

Why inserting before is now trivial

insertBefore on a DLL

void insertBefore(DLinkedList& list, DNode* curNode, DNode* newNode) {
    if (list.head == nullptr) {
        list.head = newNode;
        list.tail = newNode;
    }
    else if (curNode == list.head) {                   // before the head
        newNode->next   = list.head;
        list.head->prev = newNode;
        list.head       = newNode;
    }
    else {
        DNode* predNode = curNode->prev;
        newNode->next  = curNode;
        newNode->prev  = predNode;
        predNode->next = newNode;
        curNode->prev  = newNode;
    }
}

Symmetric to insertAfter, mirror-imaged. Same structure, same four-writes-in-interior-case, same cache-predecessor-first discipline.

Cost

::: center Operation Cost Assumption

insertAfter(curNode, x) $O(1)$ Caller has curNode insertBefore(curNode, x) $O(1)$ Caller has curNode insert at index $k$ $O(k)$ Walk from head, then splice :::

In the STL

std::list::insert

std::list<int> l = {7, 9, 5};
auto it = std::next(l.begin(), 1);  // iterator to "9"

l.insert(it, 42);                    // 7, 42, 9, 5  (insert before)
l.insert(std::next(it), 100);        // 7, 42, 9, 100, 5 (insert after "9")

std::list::insert(pos, x) inserts before pos. This is the only primitive the STL provides — insert after is written as insert(std::next(pos), x). The implementation under the hood is the four-pointer-write interior case above, wrapped in a circular-DLL-with-sentinel that also eliminates the “empty list” special case.

4.8 Doubly Linked Lists: Remove

This is where the extra prev pointer pays its rent. On a DLL, removing a node takes $O(1)$ given nothing but the node itself — no predecessor argument, no backward scan. The SLL couldn’t do this. The algorithm is also structurally cleaner: instead of three scenario branches, we use four independent checks that each handle one of the pointers that might need updating.

Four independent checks instead of three cases

The SLL’s RemoveAfter had three cases. The DLL’s Remove is organized differently: four independent “if this pointer exists, patch it” checks. Any combination of them fires depending on where the victim sits.

::: center Condition Action

sucNode $\neq$ null sucNode $\to$ prev = predNode predNode $\neq$ null predNode $\to$ next = sucNode curNode == list.head list.head = sucNode curNode == list.tail list.tail = predNode :::

The algorithm

remove on a DLL

void remove(DLinkedList& list, DNode* curNode) {
    DNode* sucNode  = curNode->next;
    DNode* predNode = curNode->prev;

    if (sucNode  != nullptr) sucNode->prev  = predNode;
    if (predNode != nullptr) predNode->next = sucNode;

    if (curNode == list.head) list.head = sucNode;
    if (curNode == list.tail) list.tail = predNode;

    delete curNode;
}

Six lines of logic, four conditional pointer writes, one delete. No traversal. $O(1)$ in all cases.

Picture

::: center Before, for an interior removal:
... $\leftrightarrow$ [predNode] $\leftrightarrow$ [curNode] $\leftrightarrow$ [sucNode] $\leftrightarrow$ ...
After:
... $\leftrightarrow$ [predNode] $\leftrightarrow$ [sucNode] $\leftrightarrow$ ... :::

The curNode is short-circuited by updating exactly two pointers: predNode $\to$ next and sucNode $\to$ prev. The victim is then unreachable from the list and can be safely freed.

The big comparison to SLL

This is the place where the SLL/DLL trade-off lands most clearly.

::: center Operation SLL DLL

Remove, given node pointer $O(n)$ (scan for prev) or use awkward RemoveAfter(prev) $O(1)$ from the node Remove by value $O(n)$ (walk to find) $O(n)$ (walk to find) + $O(1)$ unlink Remove during a walk $O(1)$ with trailing prev $O(1)$ natively Splice a node between two existing lists painful; need prev in both places trivial with the node’s prev/next pointers :::

Cost

::: center Operation Cost Assumption

remove(node) $O(1)$ Caller has a pointer to the node Remove by value $O(n)$ Linear search to find, then $O(1)$ unlink Remove at index $k$ $O(k)$ Walk to position, then $O(1)$ unlink Remove all of value $x$ $O(n)$ Single walk; remove matches in place :::

Handling ownership in C++

Return-the-node variant

DNode* unlink(DLinkedList& list, DNode* curNode) {
    DNode* sucNode  = curNode->next;
    DNode* predNode = curNode->prev;
    if (sucNode  != nullptr) sucNode->prev  = predNode;
    if (predNode != nullptr) predNode->next = sucNode;
    if (curNode == list.head) list.head = sucNode;
    if (curNode == list.tail) list.tail = predNode;
    curNode->next = curNode->prev = nullptr;   // disconnect for safety
    return curNode;                            // caller owns it now
}

The curNode $\to$ next = curNode $\to$ prev = nullptr line matters: leaving stale pointers on a detached node invites bugs where the caller accidentally walks from it back into the old list.

Where this leaves the list ADT

4.9 Linked List Traversal

Traversal is the loop that ties linked lists back to every other container: “do something to each element.” It is also the cheapest linked list operation to get right, because a linked list has exactly one shape of walk through it --- curNode = curNode->next, repeated until the pointer falls off the end.

The walker idiom, one more time

You have written this loop (or a close cousin) in every earlier section. It deserves its own name because it is the single building block under search, insert-after-value, remove-by-value, size, clear, copy, and almost any other “go look at everything” operation.

Forward traversal, the loop everyone writes

// Apply `visit` to every node in a singly-
// or doubly-linked list, front to back.
void traverse(Node* head) {
    for (Node* cur = head; cur != nullptr; cur = cur->next) {
        visit(cur);
    }
}

Three things make this loop airtight. First, the starting state is the list handle (head), not a guess --- if the list is empty, head is nullptr and the loop body never runs. Second, the termination condition is cur != nullptr, which works for length 0, length 1, and length n with no special cases. Third, the advance step is a single field read; next is either a valid node or the sentinel nullptr that the list’s append/prepend/remove code is contractually required to maintain.

Doubly-linked lists: reverse traversal for free

Because every node in a DLL carries a prev pointer and the list keeps a tail handle, you can walk the list backwards at the same cost as forwards. This is one of the concrete payoffs for the extra pointer per node discussed in section 4.6.

A singly-linked list has no efficient reverse traversal. The only way to visit the nodes in reverse is to either reverse the list first (O(n) destructive), push every node onto a stack during a forward pass (O(n) space), or use recursion (which is push-onto- a-stack by another name, using the call stack). All three cost Theta(n) extra work or space on top of the walk itself. The DLL does it in zero extra work because the backward links were already built.

Cost

::: center Operation Cost Notes

Forward traversal (SLL or DLL) $\Theta(n)$ Must visit each node Reverse traversal (DLL) $\Theta(n)$ Symmetric to forward Reverse traversal (SLL) $\Theta(n)$ Plus $\Theta(n)$ space :::

The big-Theta is non-negotiable: to touch every element you pay n operations. The interesting cost is per-step, which is O(1) for both SLL and DLL because each step is one pointer indirection. This is what makes the linked list traversal the same asymptotic cost as an array’s for (int i = 0; i < n; ++i) even though the underlying machine work is quite different.

Traversal as the hidden primitive

Once you have the walker loop, almost every other “touch everything” operation is a specialization of it.

::: center Operation What the walker body does

size() Increment a counter print() Print cur->data search(x) Compare, return if found sum() Accumulate cur->data clear() delete prev, advance copy() Append cur->data to new list contains(x) Compare, return bool :::

The reason linked list code looks repetitive across the chapter is that it is repetitive: every one of these operations is the same loop with a different body. If you find yourself writing the traversal scaffold for the fifth time in one class, that is the signal to factor out a higher-order helper that takes a callable --- which is exactly what the STL does in std::for_each, std::find_if, and std::accumulate.

STL: traversal without writing the loop

#include <list>
#include <algorithm>
#include <numeric>
#include <iostream>

std::list<int> xs = {3, 1, 4, 1, 5, 9};

// print each
std::for_each(xs.begin(), xs.end(),
              [](int v) { std::cout << v << ' '; });

// find first element > 4
auto it = std::find_if(xs.begin(), xs.end(),
                       [](int v) { return v > 4; });

// sum
int total = std::accumulate(xs.begin(), xs.end(), 0);

std::list exposes iterators (begin(), end(), rbegin(), rend()) that are the library’s name for “the current walker.” Advancing an iterator with ++it is exactly the cur = cur->next step; the iterator just hides the pointer. Once you understand the raw loop, the STL version stops looking magical.

4.10 Sorting Linked Lists

Sorting is the first algorithm in this chapter that isn’t just a walker variant. It’s also where the cost difference between arrays and linked lists stops being theoretical --- many classic array sorts straight up don’t work on a linked list, and the ones that do have a different implementation on each list flavor. Insertion sort was first analyzed on arrays in ; here we adapt it to a linked-list traversal.

Insertion sort on a DLL: the easy case

Insertion sort on a doubly-linked list is almost identical to the array version. The outer loop visits each node starting from the second; the inner loop walks prev pointers back through the sorted prefix until it finds the right slot, then splices the current node there.

DLL insertion sort

void insertionSort(DList& L) {
    DNode* cur = L.head ? L.head->next : nullptr;
    while (cur) {
        DNode* nxt = cur->next;   // cache before mutation
        DNode* s   = cur->prev;
        while (s && s->data > cur->data) s = s->prev;

        L.remove(cur);
        if (!s) L.prepend(cur);
        else    L.insertAfter(s, cur);

        cur = nxt;
    }
}

The cache-nxt-before-mutating pattern is the same one you saw in remove-during-traversal (section 4.9). You can’t advance via cur->next after L.remove(cur) splices cur out --- its next may now point somewhere else, or may be stale.

SLL insertion sort, forward-search variant

// Find the node *after which* `value` should go,
// or nullptr if it belongs at the head.
Node* findInsertPos(List& L, int value) {
    Node* before = nullptr;
    Node* cur    = L.head;
    while (cur && value > cur->data) {
        before = cur;
        cur    = cur->next;
    }
    return before;
}

Cost

::: center Variant Best Average/Worst Why

DLL insertion sort $O(n)$ $O(n^2)$ Already-sorted skips inner loop SLL insertion sort $O(n)$ $O(n^2)$ Descending list = trivial :::

The best-case $O(n)$ trigger differs between the two: a sorted DLL never enters the inner loop (the prev data is already smaller), while a reverse-sorted SLL inserts every element at the head --- findInsertPos returns nullptr immediately, which is also a no-op.

Which array sorts survive the linked-list trip?

::: center Algorithm Port? Reason

Insertion sort Yes Only needs neighbor access Merge sort Yes Splitting & merging is pointer surgery Selection sort Yes (ish) Needs $n$ linear “find min” passes Shell sort No Gap-jumps require indexed access Quicksort Poor Partition needs both-ends access Heap sort No Heap needs parent/child by index :::

4.11 Sentinel (Dummy) Nodes

Every removal and insertion algorithm you’ve written so far has a prologue: a cluster of if statements for the empty list, the head, and the tail. Sentinel nodes --- also called “dummy” nodes --- are a structural trick that makes those special cases disappear. You pay one pointer of overhead and a pinch of conceptual weirdness; in return, every other method gets shorter.

Why the head-and-tail cases exist

Take a close look at ListRemove from section 4.8: the very first lines check if (curNode == list->head) and if (curNode == list->tail). Those branches exist because head has no predecessor and tail has no successor. Most of the body is just “update the list handle instead of an in-list pointer.”

A sentinel makes head-has-no-predecessor false. Every real node now has a valid prev pointing to either another real node or the sentinel. The removal code never has to ask “am I at the head?” because it always has a predecessor to splice around.

One dummy vs. two dummies

::: center Variant Simplifies Still special-cases

No sentinel --- head, tail, empty One head sentinel head/empty tail Two sentinels everything none (for interior ops) :::

The two-sentinel DLL is the cleanest: ListRemove is just “unsplice,” with no branches at all, because both neighbors are guaranteed to exist.

Two-sentinel DLL remove --- branchless

void remove(DNode* cur) {
    // cur is a real node, so cur->prev and cur->next
    // are both non-null (they point at real nodes
    // or at the sentinels).
    cur->prev->next = cur->next;
    cur->next->prev = cur->prev;
    delete cur;
}

Compare that with the no-sentinel version’s four pointer checks (section 4.8). Both are $O(1)$ --- but the branchless version is faster in practice (the CPU loves straight-line code), shorter, and almost impossible to get wrong.

What sentinels cost

::: center Cost Amount Notes

Extra memory 1 or 2 nodes Constant, regardless of list size Extra complexity “size” is tracked separately size() != number of nodes Extra care iterators must skip sentinels Usually hidden in begin()/end() :::

The “size is tracked separately” point matters for correctness. A sentinel-based list must either keep a size counter or define “size” as “number of nodes minus the sentinels.” Walking the whole list and counting no longer gives the right answer for a caller who expects 0 on an empty list.

Do real C++ lists use sentinels?

Yes. std::list in libstdc++ and libc++ is a doubly-linked circular list with a single sentinel. The list object itself contains the sentinel inline (no heap allocation for an empty list), and end() returns an iterator to that sentinel. That’s why dereferencing end() is undefined behavior but comparing against it is fine: the sentinel exists, it just doesn’t hold a user value.

The payoff: std::list::splice

The circular-sentinel layout enables one operation that no contiguous container can match: moving an entire range of nodes between two lists in $O(1)$ , regardless of range size. The STL exposes this as std::list::splice.

std::list::splice: the operation only a linked list can do in $O(1)$

#include <list>
std::list<int> a {1, 2, 3, 4, 5};
std::list<int> b {10, 20, 30};

// Move the [2, 3, 4] range from a into b before
// the position of 20. O(1) -- no copies, no allocation.
auto first = std::next(a.begin());      // points to 2
auto last  = std::next(a.begin(), 4);   // points to 5 (one past 4)
b.splice(std::next(b.begin()), a, first, last);

// a is now {1, 5}; b is now {10, 2, 3, 4, 20, 30}.

The cost is $O(1)$ because splice only rewires four pointers --- the next/prev of the boundary nodes on each side. The range itself isn’t touched. std::vector cannot do this without copying or moving every element in the range, an inherent $O(k)$ cost. This is the canonical answer to “why would I ever use std::list when vector usually wins?” If your workload splices large ranges between lists, the linked structure pays for its cache-hostility and per-node allocation overhead. Otherwise it usually doesn’t.

4.12 Recursion on Linked Lists

A linked list is a recursive data structure in disguise: it is “a head node plus the rest of the list, which is also a linked list.” That definition practically hands you the recursive algorithms for free. Every iterative walker from the last few sections has a recursive twin that is often shorter, and occasionally clearer --- at a real performance cost.

Forward traversal, recursive

Recursive forward traverse

void traverse(Node* node) {
    if (!node) return;       // empty list: done
    visit(node);             // head: do the work
    traverse(node->next);    // tail: trust recursion
}

Three lines, one branch. The base case is “empty list,” which maps exactly to node == nullptr. The inductive step is “visit head, recurse on tail.” This is the cleanest expression of a traversal you can write --- and the iterative version from section 4.9 is still faster in practice.

Forward vs. reverse: one line swap

The striking thing about recursive list code is how little has to change to reverse the order. Swap “visit” and “recurse” and you get a reverse traversal:

Recursive reverse traverse

void traverseReverse(Node* node) {
    if (!node) return;
    traverseReverse(node->next);  // recurse FIRST
    visit(node);                  // then visit
}

This works on a singly-linked list --- no prev pointer needed. The reversal is hiding in the call stack: each activation records a node, all activations unwind in LIFO order, and visits happen on the way out.

Recursive search

Node* search(Node* node, int key) {
    if (!node)              return nullptr; // not found
    if (node->data == key)  return node;    // found
    return search(node->next, key);         // keep looking
}

Three cases, each a single line. The third case is a tail call: the recursive call is the last thing the function does. Some compilers (including modern g++/clang with -O2) can recognize this and rewrite it as a loop, reclaiming the stack frame each step. With tail-call optimization, the recursive version has the same stack cost as the iterative one. Without it, a 10,000-element list will blow the default 8MB stack on Linux somewhere around recursion depth 100,000 --- well above 10k, but closer than you think.

Cost: recursive vs iterative

::: center Operation Rec. time Rec. space Iterative space

Forward traverse $\Theta(n)$ $\Theta(n)^*$ $\Theta(1)$ Reverse traverse $\Theta(n)$ $\Theta(n)$ $\Theta(n)$ (explicit stack) Search $\Theta(n)$ $\Theta(n)^*$ $\Theta(1)$ :::

$^*$ With tail-call optimization, $\Theta(1)$ . C++ does not guarantee TCO --- treat it as a performance optimization, not a correctness property.

4.13 Stack ADT

Stacks are the first “restricted list” ADT. Where a list lets you touch any element, a stack lets you touch one: the top. That single restriction is the entire point. It buys you a mental model (LIFO, last-in-first-out), a suite of cheap operations (everything $O(1)$ ), and a surprisingly long list of real-world algorithms that just fall out of it.

The five operations

::: center Op Semantics Cost

push(x) Add x at top $O(1)$ pop() Remove and return top $O(1)$ peek() Return top without removing $O(1)$ empty() True iff no elements $O(1)$ size() Number of elements $O(1)$ :::

All five are guaranteed $O(1)$ --- that’s not a coincidence, it’s the contract. A data structure that calls itself a stack but has $O(n)$ push is mislabeled; the whole reason stacks exist is to be cheap.

C++: std::stack

C++ provides std::stack as a container adapter --- a wrapper around an underlying container that exposes only the stack operations. The underlying container defaults to std::deque but can be any container that supports push_back, pop_back, and back.

std::stack basics

#include <stack>
#include <iostream>

std::stack<int> s;
s.push(7); s.push(14); s.push(9); s.push(5);

while (!s.empty()) {
    std::cout << s.top() << ' ';  // peek
    s.pop();                      // remove
}
// Output: 5 9 14 7   (LIFO)

Notice top() is the STL’s name for peek(), and pop() returns void --- you must call top() before pop() if you want the value. This split is deliberate: it avoids forcing a copy on every pop, which matters for stacks of expensive-to-copy types.

Why restrict access at all?

A stack has strictly fewer operations than a list. That seems strictly worse. The payoff is threefold:

Speed guarantee. A list has $O(n)$ random access; a stack’s operations are all $O(1)$ . The restriction is what makes that guarantee possible.
Code clarity. A function that takes a stack<T>& advertises its intent: “I will use this LIFO.” A function taking vector<T>& is making no such promise.
Implementation freedom. Once you commit to LIFO semantics, the implementer can swap in any underlying container (array, DLL, circular buffer) without breaking callers.

4.14 Stacks via Linked Lists

Section 4.13 defined what a stack is. This section picks one concrete implementation: a singly-linked list where the head is the top. Every stack operation becomes a list operation you already know.

The mapping

::: center Stack op List op (head = top) Cost

push(x) prepend(x) $O(1)$ pop() Read head, remove head $O(1)$ peek() Read head->data $O(1)$ empty() head == nullptr $O(1)$ size() Counter updated on push/pop $O(1)$ :::

The key design choice is head-as-top. Why not tail? Because in a singly-linked list, prepending is $O(1)$ and appending-then-removing is $O(n)$ without a tail pointer (you’d still need to walk to find the new tail after popping). Putting the top at the head lines the cheap operations up perfectly.

Implementation

Singly-linked stack

template <typename T>
class Stack {
    struct Node { T data; Node* next; };
    Node*  head_ = nullptr;
    size_t n_    = 0;

public:
    ~Stack() { while (!empty()) pop(); }

    bool   empty() const { return head_ == nullptr; }
    size_t size()  const { return n_; }

    void push(const T& x) {
        head_ = new Node{x, head_};  // prepend
        ++n_;
    }

    T pop() {
        // caller's responsibility: !empty()
        Node*  top = head_;
        T      val = std::move(top->data);
        head_      = head_->next;
        delete top;
        --n_;
        return val;
    }

    const T& peek() const { return head_->data; }
};

A few things worth pointing out:

Destructor walks and frees. A stack owns its nodes. Without the destructor, every Stack that goes out of scope while non-empty leaks the whole chain.
n_ counter. Keeping size() $O(1)$ requires maintaining a counter. Walking the list every time would make size() $O(n)$ , violating the ADT contract.
pop returns by value; peek by const-reference. Pop has to return because the node is about to be deleted, so you can’t hand out a reference into freed memory. Peek can return a reference because the node is still alive.

Linked list vs. array backing

A stack doesn’t have to be a linked list. A dynamic array (std::vector) with push-back-as-push and pop-back-as-pop is often faster in practice because the elements are contiguous and the CPU prefetches. The tradeoff:

::: center Metric Linked list Dynamic array

push worst case $O(1)$ $O(n)$ (on resize) push amortized $O(1)$ $O(1)$ pop $O(1)$ $O(1)$ Cache friendliness Poor Excellent Memory overhead / elem 1 pointer 0—1 slot (slack) Handles huge sizes Any Any :::

For almost every use case, array-backed is the right default --- which is why std::stack defaults to std::deque (array-ish under the hood) rather than std::list. The linked-list version shines when you need guaranteed worst-case $O(1)$ with no amortization.

4.15 Queue ADT

A queue is the stack’s twin. Where a stack is LIFO (last-in, first-out), a queue is FIFO (first-in, first-out). Both are restricted list ADTs with exactly two access points --- the only difference is whether you remove from the same end you insert at (stack) or the opposite end (queue).

The five operations

::: center Op Semantics Cost

push(x) / enqueue Add x at rear $O(1)$ pop() / dequeue Remove and return front $O(1)$ peek() / front Return front without removing $O(1)$ empty() True iff no elements $O(1)$ size() Number of elements $O(1)$ :::

Every operation is $O(1)$ , same as a stack. The restriction (only two access points) is what makes this achievable --- a general list cannot guarantee $O(1)$ on both ends without extra structure.

C++: std::queue

std::queue mirrors std::stack: a container adapter with a default underlying container (std::deque) and a minimal interface. The names are slightly different because a queue has two ends.

std::queue basics

#include <queue>
#include <iostream>

std::queue<int> q;
q.push(7); q.push(14); q.push(9); q.push(5);

while (!q.empty()) {
    std::cout << q.front() << ' ';  // peek
    q.pop();                        // remove
}
// Output: 7 14 9 5   (FIFO --- insertion order)

Notice the output is in insertion order, not reversed like a stack. Also notice std::queue exposes both front() and back(); you can peek at either end but only pop from the front and push to the back.

Where queues show up

::: center Use case What the queue represents

BFS graph traversal Frontier of nodes to visit Scheduling (OS, jobs) Tasks waiting to run Producer/consumer Work items, producer pushes, consumer pops Message passing Inbox (network, IPC) Printer / print spool Jobs queued for the device Buffered I/O Bytes waiting to be read or written :::

The unifying theme: “things arrive over time; serve them in arrival order.” That is a much more common pattern than LIFO, which is why queues are everywhere the moment you leave single- threaded algorithm land.

Why a queue needs two pointers on a linked list

On a singly-linked list, pop-from-front is cheap (just advance head) but push-to-back is $O(n)$ --- unless you keep a tail pointer. A stack’s linked implementation needs only the head, but a queue needs both head and tail because the two operations live at opposite ends.

4.16 Queues via Linked Lists

The queue-via-linked-list implementation is structurally almost identical to the stack version from 4.14, but with one critical addition: the queue needs a tail pointer so push-to-back stays $O(1)$ .

The mapping

::: center Queue op List op (head = front, tail = rear) Cost

push(x) append(x) via tail pointer $O(1)$ pop() Read head, remove head $O(1)$ peek() Read head->data $O(1)$ empty() head == nullptr $O(1)$ size() Counter updated on push/pop $O(1)$ :::

The design is head-as-front, tail-as-rear. Pop removes from the head ( $O(1)$ : advance head). Push adds at the tail ( $O(1)$ only if we keep a tail pointer).

Implementation

Singly-linked queue with head and tail

template <typename T>
class Queue {
    struct Node { T data; Node* next; };
    Node*  head_ = nullptr;
    Node*  tail_ = nullptr;
    size_t n_    = 0;

public:
    ~Queue() { while (!empty()) pop(); }

    bool   empty() const { return head_ == nullptr; }
    size_t size()  const { return n_; }

    void push(const T& x) {
        Node* node = new Node{x, nullptr};
        if (tail_) tail_->next = node;  // link old tail
        else       head_       = node;  // was empty
        tail_ = node;
        ++n_;
    }

    T pop() {
        // caller's responsibility: !empty()
        Node* front = head_;
        T     val   = std::move(front->data);
        head_ = head_->next;
        if (!head_) tail_ = nullptr;    // queue now empty
        delete front;
        --n_;
        return val;
    }

    const T& peek() const { return head_->data; }
};

Two lines deserve close attention:

The empty-push case. When tail_ is nullptr, the queue is empty; the new node is simultaneously the head and the tail, so both pointers must be set. Missing this turns a push on an empty queue into a silent no-op.
The empty-pop case. When the pop removes the last element, tail_ must be reset to nullptr as well. Missing this leaves a dangling pointer: the next push will write to tail_->next, which is a pointer into freed memory.

Why not a doubly-linked list?

A DLL would work, but it’s overkill. A queue never traverses backward, never inserts in the middle, and never removes from anywhere other than the head. The prev pointer on every node would be dead weight --- pure memory overhead with no corresponding operation to justify it.

::: center Operation Needs prev?

push(x) No (append at tail, only need tail->next) pop() No (remove head, only need head->next) peek() No :::

An SLL with head+tail is the minimum sufficient structure. That’s usually the right way to choose data structures: add capability up to exactly what the operations demand, no further.

Implementing the ring buffer

The notebox above gestures at the ring buffer; it deserves a concrete implementation, since it is the structure used in OS kernels for bounded producer-consumer queues, in audio/video pipelines for fixed-latency buffering, and inside std::deque block-by-block.

Ring-buffer queue in C++

template <typename T, size_t N>
class RingQueue {
    T   buf_[N];
    size_t head_ = 0;
    size_t tail_ = 0;
    size_t sz_   = 0;     // explicit size: avoids head==tail ambiguity
public:
    bool empty() const { return sz_ == 0; }
    bool full()  const { return sz_ == N; }
    size_t size() const { return sz_; }

    bool enqueue(const T& x) {
        if (full()) return false;     // caller decides: drop or block
        buf_[tail_] = x;
        tail_ = (tail_ + 1) % N;
        ++sz_;
        return true;
    }

    bool dequeue(T& out) {
        if (empty()) return false;
        out  = buf_[head_];
        head_ = (head_ + 1) % N;
        --sz_;
        return true;
    }
};

4.17 Deque ADT

A deque (pronounced “deck,” short for double- ended queue) is the union of a stack and a queue. Where a stack restricts you to one end and a queue to two specific ends (front for pop, back for push), a deque lets you push and pop at either end. That flexibility costs nothing in asymptotic time: all four operations remain $O(1)$ .

The eight operations

::: center Op Semantics Cost

push_front(x) Insert x at front $O(1)$ push_back(x) Insert x at back $O(1)$ pop_front() Remove and return front $O(1)$ pop_back() Remove and return back $O(1)$ peek_front() Return front without removing $O(1)$ peek_back() Return back without removing $O(1)$ empty() True iff no elements $O(1)$ size() Number of elements $O(1)$ :::

The ADT hierarchy, visualized

::: center ADT Push front Push back Pop front Pop back

Stack $\bullet$ $\bullet$ Queue $\bullet$ $\bullet$
Deque $\bullet$ $\bullet$ $\bullet$ $\bullet$ :::

A stack is a deque that only uses one end. A queue is a deque that uses opposite ends. Every stack and queue operation is also a valid deque operation --- deques strictly generalize both.

C++: std::deque

std::deque is a full container, not an adapter. It supports random-access iterators, operator[], and the standard container interface on top of the eight deque ops.

std::deque basics

#include <deque>
#include <iostream>

std::deque<int> d;
d.push_back(7);     // d: 7
d.push_front(14);   // d: 14 7
d.push_front(9);    // d: 9 14 7
d.push_back(5);     // d: 9 14 7 5

std::cout << d.front() << ' ' << d.back() << "\n"; // 9 5
d.pop_back();       // d: 9 14 7
d.pop_front();      // d: 14 7
std::cout << d[0] << "\n"; // 14  --- random access works

Linked-list implementation: the DLL’s payoff

A deque on a linked list is where the doubly-linked list finally earns its keep. Think about it:

::: center Operation SLL cost DLL cost

push_front $O(1)$ $O(1)$ push_back $O(1)$ (with tail) $O(1)$ pop_front $O(1)$ $O(1)$ pop_back $O(n)$ (no prev!) $O(1)$ :::

The fourth row is the killer. To pop the back of a singly-linked list, you have to walk the list to find the new tail (the second-to-last node), because there’s no prev pointer to back up from the current tail. That walk is $O(n)$ --- game over for the ADT contract.

4.18 Array-Based Lists

The chapter has spent 17 sections on pointer-based lists. This one finally asks: what if we implemented the list ADT on a plain old array instead? The answer reshuffles the cost table. Array-based lists win on random access and cache performance, and lose on insertion/removal at the front. Neither approach is universally better --- they have complementary strengths.

The layout

::: center used unused capacity

[0] [1] [2] [3] --- --- --- --- 45 84 12 78
:::

length = 4, capacity = 8. Elements live at indices [0..length); the rest is reserved space that doesn’t need to be copied on the next append.

Append: amortized O(1)

Append to a dynamic array list

void append(List& L, int value) {
    if (L.length == L.capacity) {
        resize(L, L.capacity == 0 ? 1 : L.capacity * 2);
    }
    L.array[L.length++] = value;
}

void resize(List& L, size_t newCap) {
    int* p = new int[newCap];
    for (size_t i = 0; i < L.length; ++i) p[i] = L.array[i];
    delete[] L.array;
    L.array    = p;
    L.capacity = newCap;
}

A single append is usually $O(1)$ : assign into array[length], increment length. But when the array is full, the resize step is $O(n)$ : allocate, copy every element, free the old array. So is append $O(1)$ or $O(n)$ ?

Prepend and insert: the expensive operations

Appending is cheap because the free space lives at the end. Prepending is $O(n)$ because every existing element has to shift right by one to make room at index 0. Inserting after index $k$ shifts everything in $[k+1, \text{length})$ --- worst case $O(n)$ , best case (insert at the end) $O(1)$ .

Array prepend: linear shift

void prepend(List& L, int value) {
    if (L.length == L.capacity) resize(L, L.capacity * 2);
    for (size_t i = L.length; i > 0; --i) {
        L.array[i] = L.array[i - 1];       // O(n) shift
    }
    L.array[0] = value;
    ++L.length;
}

The full cost comparison

::: center Operation Array-based Linked list

append $O(1)^*$ $O(1)$ (with tail) prepend $O(n)$ $O(1)$ insert at index $k$ $O(n-k)$ $O(n)$ to find, $O(1)$ to insert remove at index $k$ $O(n-k)$ $O(n)$ to find, $O(1)$ to remove access by index $O(1)$ $O(n)$ search by value $O(n)$ $O(n)$ append (at end) $O(1)^*$ $O(1)$ Cache friendliness Excellent Poor Memory overhead per element 0—1 slot 1—2 pointers :::

$^*$ amortized

The two structures have complementary strengths. Array- based wins on index access, cache behavior, and append. Linked wins on front operations and interior insertion once the position is known. Picking between them is an algorithmic choice driven by what operations dominate.

List-variant decision matrix

The four realizations of the List ADT covered in this chapter — dynamic array (std::vector), singly linked list (SLL), doubly linked list (DLL), and sentinel DLL (or std::list) — trade cost in predictable ways. This matrix is the decision you’ll actually make on assignments.

Cost of each List-ADT operation

All entries are worst-case unless marked. $n$ = list length.

Operation Array SLL DLL Sentinel DLL

Access $v[i]$ $O(1)$ $O(n)$ $O(n)$ $O(n)$ Append (back) $O(1)^*$ amort. $O(1)$ w/ tail $O(1)$ w/ tail $O(1)$ Prepend (front) $O(n)$ shift $O(1)$ $O(1)$ $O(1)$ Insert after node $O(n)$ shift $O(1)$ $O(1)$ $O(1)$ Insert before node $O(n)$ shift $O(n)$ $O(1)$ $O(1)$ Remove node (have ptr) $O(n)$ shift $O(n)$ find prev $O(1)$ $O(1)$ Remove by value $O(n)$ $O(n)$ $O(n)$ $O(n)$ Reverse traversal $O(n)$ $O(n)$ reconstruct $O(n)$ $O(n)$ Memory per element $\sim$ 4—8 B + 1 pointer + 2 pointers + 2 pointers Cache friendliness excellent poor poor poor

Which variant, for which job?

Read top-down; take the first match.

Do you need $O(1)$ indexing ( $v[i]$ )? $\to$ array-based (std::vector). Nothing else gives you random access. Accept $O(n)$ middle inserts.

Is the data mostly appended/consumed at the ends only? (Stack: push/pop one end. Queue: enqueue one end, dequeue the other. Log buffer: append, scan.)
$\to$ array-based for stacks (std::stack $\to$ std::deque). Array-based deque or linked list for queues. std::queue uses std::deque.

Are you doing many mid-list inserts/removes, AND you already hold a pointer/iterator to the node (e.g., LRU cache, intrusive list in kernel code)?
$\to$ DLL (or sentinel DLL). This is the scenario linked lists win; every other scenario, arrays usually win.

Do you need bidirectional traversal? $\to$ DLL or sentinel DLL. SLL only walks forward; walking backward means rebuilding a reverse list.

Do you want insertBefore as a primitive, or do the empty/first/last cases in your code feel gross?
$\to$ sentinel DLL. The dummy head/tail nodes make every splice look the same; no special-casing.

Is every byte precious (embedded, cold cache)? $\to$ SLL, not DLL: one pointer per node, not two. And consider an array-based list anyway — contiguous memory often wins even on “slow at middle insert” workloads because of cache.

Still unsure? $\to$ array-based list (std::vector). It’s the right default. Linked lists are special-purpose; reach for them when you have a concrete reason (pointer stability, intrusive data, O(1) splicing).

What this connects to

Companion materials. Compact notes: chapters/ch_4/notes.tex (includes the decision matrix in compact form). Practice prompts (problem $\to$ pseudocode $\to$ C++): chapters/ch_4/practice.md.

4.1 The List ADT

The contract: operations

What the contract doesn’t say

List is the root ADT; stacks and queues restrict it

C++: std::list, std::vector, std::forward_list

What this chapter builds

4.2 Singly Linked Lists: Append and Prepend

The node type in C++

Append: add at the end

Prepend: add at the front

Cost summary

Language conventions for “null”

What’s coming next

4.3 Singly Linked Lists: Insert-After

The three cases

The algorithm

Why we need the curNode argument

Mapping to std::list

Cost

4.4 Singly Linked Lists: Remove

Why predecessor-based removal?

The three cases

The algorithm

Cost

Why we don’t have Remove(node) directly

All five SLL operations together

4.5 Linked List Search

The algorithm

Why return a pointer instead of an index

Cost

Linked-list search is hostile to CPU caches

Two common variations

What search gives you

4.6 Doubly Linked Lists

The node type in C++

Invariants

Append

Prepend

What the back-pointer unlocks

When the extra pointer is not worth it

Cost of the endpoint operations

std::list is a circular DLL

Where this is going

4.7 Doubly Linked Lists: Insert-After

The three cases

The algorithm

Picture of the interior splice

Why inserting before is now trivial

Cost

In the STL

4.8 Doubly Linked Lists: Remove

Four independent checks instead of three cases

The algorithm

Picture

The big comparison to SLL

Cost

Handling ownership in C++

Where this leaves the list ADT

4.9 Linked List Traversal

4.10 Sorting Linked Lists

4.11 Sentinel (Dummy) Nodes

4.12 Recursion on Linked Lists

4.13 Stack ADT

4.14 Stacks via Linked Lists

4.15 Queue ADT

4.16 Queues via Linked Lists

4.17 Deque ADT

4.18 Array-Based Lists

List-variant decision matrix

What this connects to

C++: `std::list`, `std::vector`, `std::forward_list`

Mapping to `std::list`

Why we don’t have `Remove(node)` directly

`std::list` is a circular DLL