Fundamental Data Structures: Arrays, Linked Lists, Stacks and Queues

0. Key points

• A data structure is judged not by what it can do but by how fast each operation is. Arrays and linked lists represent the same kind of sequence, and the operations they are good at are exactly the opposite of one another.
• An array supports indexed access in $\Theta(1)$ time and insertion or deletion in the middle in $\Theta(n)$ time. A linked list, given a reference to the node marking the position, inserts or deletes right after it in $\Theta(1)$ time, but reaching the $k$-th element costs $\Theta(k)$ (Proposition 3.2, Proposition 4.2).
• A dynamic array that doubles its capacity has worst-case cost $\Theta(n)$ for a single push, yet the total over $n$ pushes stays below $3n$. The amortized cost is $O(1)$ (Theorem 3.3).
• “Amortized $O(1)$” does not mean “fast on average”. No probability distribution on the input is assumed; the bound on the total cost holds for every sequence of operations.
• A stack (LIFO) and a queue (FIFO) are abstract data types, specifiable by axioms without mentioning any implementation. The same axioms can be met by an array and by a linked list alike.
• A queue can be realised with worst-case $\Theta(1)$ operations by a ring buffer (Proposition 7.2), or with amortized $O(1)$ operations by two stacks (Theorem 8.2). We analyse the latter by the potential method.

1. Motivation

Most of the data a program handles is a sequence. Text is a sequence of characters, an image a sequence of pixels, an account history a sequence of transactions. How a sequence is laid out inside the machine is a matter of choice, and that choice can change the running time by orders of magnitude.

Let us start from a naive question. Why have two representations, the array and the linked list, both stayed in use for more than half a century? Because the operations they are good at are exactly complementary. An array is strong at “show me the $i$-th element” and weak at “squeeze something into the middle”. The linked list is the reverse. Had either one won on every operation, the other would have disappeared from history.

The two also arose from different demands. Arrays have existed as a language feature since the earliest high-level language, Fortran (1957). Linked lists came slightly later: around 1956 Allen Newell, Cliff Shaw and Herbert Simon designed the information processing language IPL for their theorem-proving program Logic Theorist, and IPL introduced them; LISP inherited them in 1958. What those authors needed was a representation in which an element could be inserted in the middle without shifting everything behind it.

In this article we take the $O$ and $\Theta$ notation of the previous chapter, Complexity and big-O notation (Definition 3.1［Complexity and Big-O Notation］), as our instrument, and begin by separating “what can be done” (the abstract data type) from “how it is realised” (the data structure). We then take up arrays, linked lists, stacks and queues, and determine the cost of each operation with proofs.

2. Preliminaries: the machine model and abstract data types

To prove anything about running time we must first fix what counts as one unit of time. In this article we use the word RAM model. It refines the uniform-cost RAM model（Definition 2.1）［Complexity and Big-O Notation］ of the previous chapter by making the addressing of memory explicit.

Memory is a sequence of words $M[0], M[1], \ldots$ indexed by addresses $0, 1, 2, \ldots$, and one word can hold a single integer or a single address. Reading or writing $M[i]$ for a given address $i$, and adding, subtracting, multiplying, dividing or comparing words, each takes one unit of time. This assumption — that a read or write at a given address is constant time — is what will justify the claim that indexed access into an array costs $\Theta(1)$.

Remark 2.1

The word RAM is an idealisation. Real machines have a hierarchy of caches, and the time to access one word is not constant. We still use the model because the essential differences between algorithms ($\Theta(n)$ versus $\Theta(\log n)$ versus $\Theta(1)$) are unaffected by the presence of caches. Measured differences between two $\Theta(n)$ procedures lie outside the model; we discuss them in Remark 5.1.

Next we introduce the basic distinction on which any discussion of data structures rests.

Definition 2.2（Abstract data type）

An abstract data type (ADT) is a triple, containing no internal representation of values whatsoever, consisting of:

1. a set of values;
2. the names of the operations, together with the types of their arguments and return values;
3. the properties the operations must satisfy. These may be written as preconditions and postconditions, or as equations (axioms) relating the operations to one another.

A realisation of an abstract data type by a concrete layout of memory together with concrete procedures is called a data structure.

This distinction earns its keep because one abstract data type can have many data structures. Which one to use is not settled by correctness; it is settled by how often each operation is used and what each operation costs.

3. Arrays and dynamic arrays

Definition 3.1（Array）

An array of length $n$ consists of $n$ cells of equal size $s$ (in words) placed at consecutive addresses starting from a base address $b$. The $i$-th element ($0 \le i \le n-1$) is written $A[i]$, and the starting address of its cell is

$$\mathrm{addr}(A[i]) = b + s \cdot i$$

This single formula in the definition determines both the strength and the weakness of the array. Since the address is a linear function of $i$, any element can be reached by arithmetic alone. On the other hand, squeezing in one element shifts the index $i$ of every later element by one, and hence shifts all of their addresses too. We now verify this in turn.

Proposition 3.2（Cost of the basic array operations）

For an array $A$ of length $n$, the following hold in the word RAM model.

1. Reading or writing the element at a given index $i$ ($0 \le i \le n-1$) takes $\Theta(1)$ time.
2. Deciding whether a given value $x$ occurs in $A$ takes $\Theta(n)$ time in the worst case, assuming nothing about the order of the elements. Linear search, comparing the elements from the front, attains this bound.
3. Insertion at position $i$ ($0 \le i \le n$) requires exactly $n - i$ moves of existing elements, and deletion of the element at position $i$ ($0 \le i \le n-1$) requires $n - 1 - i$ moves; both take $\Theta(n-i)$ time. In particular the worst case ($i = 0$) is $\Theta(n)$, and if the insertion position $i$ is uniformly distributed on $0, 1, \ldots, n$, the average number of moves is $n/2$.

Proof（Proposition 3.2）

1. By Definition 3.1, $\mathrm{addr}(A[i]) = b + s \cdot i$. Since $b$ and $s$ are fixed for a given array, this computation is one multiplication and one addition. In the word RAM an arithmetic operation and an addressed read or write each take one unit of time, so the total is constant, that is $\Theta(1)$. What matters is that it depends neither on $n$ nor on $i$.

2. The upper bound is given by linear search: for $i = 0, 1, \ldots, n-1$ read $A[i]$ and compare it with $x$, returning true on a match and false if none occurs. Each iteration is constant time by part 1, so the whole is $O(n)$.

For the lower bound we use an adversary argument. Suppose a correct algorithm $\mathcal{B}$, on an input $A$ not containing $x$, answers “not present” without ever reading some position $j$. Feed it $A'$, obtained from $A$ by replacing position $j$ by $x$. Since $\mathcal{B}$ never reads $j$, it follows the same computation and again answers “not present” — which is wrong, because $A'$ contains $x$. Hence all $n$ positions must be read, giving $\Omega(n)$, and together with the upper bound, $\Theta(n)$.

3. We treat insertion. The array $A'$ after the insertion satisfies $A'[j] = A[j]$ for $j < i$, $A'[i] = x$, and $A'[j+1] = A[j]$ for $i \le j \le n-1$. Every element with $j \ge i$ has its address shifted back by $s$ without exception, so at least $n - i$ writes are necessary. Conversely, moving from the back — $A[j+1] \leftarrow A[j]$ for $j = n-1, n-2, \ldots, i$ — loses nothing to overwriting and uses exactly $n-i$ writes, after which one further write $A[i] \leftarrow x$ finishes the job. One move is constant time by part 1, so the total is $\Theta(n-i)$. Deletion is analogous: closing the gap forwards with $A[j-1] \leftarrow A[j]$ for $j = i+1, \ldots, n-1$ takes $n-1-i$ moves, that is $\Theta(n-i)$.

The worst case is $i = 0$, with $n$ moves, hence $\Theta(n)$. The average is

$$\frac{1}{n+1}\sum_{i=0}^{n}(n-i) = \frac{1}{n+1}\sum_{k=0}^{n}k = \frac{1}{n+1}\cdot\frac{n(n+1)}{2} = \frac{n}{2}$$

which is again $\Theta(n)$. Averaging offers no escape from $\Theta(n)$.

∎

Arrays have a second weakness: their length must be fixed in advance. If the number of elements grows at run time, a bare array cannot cope. The dynamic array (resizable array) solves this. The naive scheme — “each time one element is added, allocate an array one longer and copy everything” — incurs $\sum_{k=1}^{n} k = \Theta(n^2)$ copies over $n$ additions. Yet merely changing the growth rule from "$+1$" to "$\times 2$" brings the total down to linear.

Theorem 3.3（Amortized cost of the dynamic array）

Consider a data structure realising append-at-the-end, $\mathrm{push}$, by the following rule. It maintains an array $A$ of capacity $c$ and the current number of elements $n$ ($0 \le n \le c$), starting from $n = 0$, $c = 1$. The operation $\mathrm{push}(x)$ behaves as follows.

• If $n < c$, set $A[n] \leftarrow x$ and then $n \leftarrow n + 1$.
• If $n = c$, first allocate a new array of length $2c$, move the existing $c$ elements into it, set $c \leftarrow 2c$, and then perform the step above.

Then the total number of element writes performed by $n$ pushes ($n \ge 1$) starting from the empty state is less than $3n$. Hence the amortized cost per $\mathrm{push}$ is $O(1)$. The worst-case cost of an individual $\mathrm{push}$, however, is $\Theta(n)$.

Proof（Theorem 3.3）

We use the aggregate method: estimate the total cost directly and divide by the number of operations.

Split the writes into two kinds. The write $A[n] \leftarrow x$ at the end occurs exactly once in every $\mathrm{push}$, contributing $n$ writes in total.

The rest are the copies caused by capacity growth. Growth happens when $n = c$ just before a $\mathrm{push}$; since the capacity runs through the powers $1, 2, 4, \ldots$, this happens exactly when the number of elements just before is $2^k$ ($k = 0, 1, 2, \ldots$), and the number of copies is then exactly $2^k$. During $n$ pushes, the element count reaches $2^k$ only for those $k$ with $2^k < n$, so letting $K$ be the largest such $k$, the total number of copies is

$$\sum_{k=0}^{K} 2^{k} = 2^{K+1} - 1 < 2 \cdot 2^{K} \le 2n$$

where the last inequality uses $2^K < n$.

Hence the total number of writes is less than $n + 2n = 3n$. Since $n$ operations cost less than $3n$ in total, the amortized cost per operation is less than $3$, that is $O(1)$.

As for the worst case, a $\mathrm{push}$ in the state $n = c = 2^k$ performs $2^k = n$ copies, and by part 1 of Proposition 3.2 this takes $\Theta(n)$ time.

∎

Example 3.4（Counting ten pushes）

Let us count the writes made by ten pushes from the empty state. Growth occurs when the element count just before is $1, 2, 4, 8$, that is, at pushes number 2, 3, 5 and 9.

push number	$(n, c)$ before	capacity after growth	copies	total writes this time
1	$(0, 1)$	—	0	1
2	$(1, 1)$	2	1	2
3	$(2, 2)$	4	2	3
5	$(4, 4)$	8	4	5
9	$(8, 8)$	16	8	9
4, 6, 7, 8, 10	—	—	0	1 each

The total is $10 + (1 + 2 + 4 + 8) = 25$ writes, below the bound $3 \times 10 = 30$ guaranteed by the theorem. The ninth push alone needs 9 writes, but levelled out this is $2.5$ writes per operation.

Remark 3.5（Amortized is not average）

Amortized cost involves no probability at all. What Theorem 3.3 asserts is the deterministic guarantee that for every sequence of pushes the total is below $3n$. This differs in meaning and in strength from arguments that assume “if the input is uniformly distributed”, as in the average cost of a hash table (Theorem 5.3［探索アルゴリズム］). On this distinction see also Remark 6.5［探索アルゴリズム］.

The theorem also depends on the growth being by a constant factor, so that the number of copies forms a geometric series. With ”$+1$ each time”, the $k$-th push causes $k-1$ copies, for a total of $\sum_{k=1}^{n}(k-1) = \Theta(n^2)$, and amortized $O(1)$ collapses. Conversely the factor need not be $2$: as long as the ratio is a constant greater than $1$, the same argument goes through, whether the factor is $1.5$ or $1.125$.

4. Linked lists

The weakness of the array was that the address is determined by the index. Then let the elements carry their addresses themselves — that is the idea behind the linked list.

Definition 4.1（Singly linked list）

A node is a cell consisting of a field $\mathrm{value}$ holding a value and a field $\mathrm{next}$ holding either a reference to another node or $\mathrm{nil}$. When nodes $p_0, p_1, \ldots, p_{n-1}$ satisfy

$$p_j.\mathrm{next} = p_{j+1} \quad (0 \le j \le n-2), \qquad p_{n-1}.\mathrm{next} = \mathrm{nil}$$

this sequence is called a singly linked list, and the whole list is represented by a reference $\mathrm{head} = p_0$ to its first node. The empty list is represented by $\mathrm{head} = \mathrm{nil}$. If each node also has a field $\mathrm{prev}$ satisfying $p_{j+1}.\mathrm{prev} = p_j$, the list is called doubly linked.

There is no constraint at all on the addresses of the nodes. They may be scattered anywhere in memory; the links are carried entirely by the values of $\mathrm{next}$. This freedom is precisely what shapes the cost profile.

Proposition 4.2（Cost of the basic linked-list operations）

For a singly linked list of $n$ nodes, the following hold in the word RAM model.

1. Given a reference to a node $p$, inserting a new node immediately after $p$, and deleting the node immediately after $p$, each take $\Theta(1)$ time.
2. Reaching the $k$-th node counted from the front (zero-based, $0 \le k \le n-1$) requires exactly $k$ traversals of $\mathrm{next}$ and takes $\Theta(k)$ time. The worst case is $\Theta(n)$.
3. In a singly linked list, deleting $p$ itself takes $\Theta(n)$ time in the worst case even when a reference to $p$ is given. In a doubly linked list it takes $\Theta(1)$ time.

Proof（Proposition 4.2）

1. For insertion, prepare a new node $q$ and perform the two writes

$$q.\mathrm{next} \leftarrow p.\mathrm{next}, \qquad p.\mathrm{next} \leftarrow q$$

Afterwards $q$ follows $p$ and the original $p.\mathrm{next}$ follows $q$, so the linking condition of Definition 4.1 is preserved. For deletion, when $p.\mathrm{next} \ne \mathrm{nil}$, the single write

$$p.\mathrm{next} \leftarrow p.\mathrm{next}.\mathrm{next}$$

suffices. In both cases the number of reads and writes depends neither on $n$ nor on $k$, so the time is $\Theta(1)$. Part 3 of Proposition 3.2 required $n-i$ moves for an insertion at position $i$; here not a single element has been moved.

2. The upper bound is given by the procedure that starts at $\mathrm{head}$ and follows $\mathrm{next}$ $k$ times. Each traversal reads one word and so is constant time, giving $\Theta(k)$ in total.

For the lower bound we use the fact that in this model there are only two ways to learn the address of a node: reading $\mathrm{head}$, and reading the $\mathrm{next}$ field of an already reached node. Unlike the array of Definition 3.1, there is no formula computing the address of the $k$-th node from $k$. Hence the set of reached nodes grows by at most one per traversal, and at least $k$ traversals are needed to arrive at $p_k$. This gives $\Theta(k)$.

3. Deleting $p$ itself requires finding the preceding node $p'$ and setting $p'.\mathrm{next} \leftarrow p.\mathrm{next}$. In a singly linked list one cannot get from $p$ to $p'$, so the only option is to walk from $\mathrm{head}$ looking for the node whose $\mathrm{next}$ equals $p$, which by part 2 is $\Theta(n)$ in the worst case. In a doubly linked list $p' = p.\mathrm{prev}$ is available in constant time, so the two writes

$$p.\mathrm{prev}.\mathrm{next} \leftarrow p.\mathrm{next}, \qquad p.\mathrm{next}.\mathrm{prev} \leftarrow p.\mathrm{prev}$$

suffice, giving $\Theta(1)$ time (the case analysis for $\mathrm{nil}$ at the two ends can be removed by the sentinel of Remark 4.4).

∎

Example 4.3（Running insertion and deletion）

We check part 1 of Proposition 4.2 in Python.

class Node:
    __slots__ = ("value", "next")

    def __init__(self, value, next=None):
        self.value = value
        self.next = next


def insert_after(p: Node, x) -> Node:
    """Insert a node with value x right after p and return it."""
    q = Node(x, p.next)   # q.next <- p.next
    p.next = q            # p.next  <- q
    return q


def delete_after(p: Node) -> None:
    """Delete the node right after p; do nothing if there is none."""
    if p.next is not None:
        p.next = p.next.next


def to_list(head: Node) -> list:
    out, cur = [], head
    while cur is not None:
        out.append(cur.value)
        cur = cur.next
    return out


head = Node(3, Node(1, Node(4)))
print(to_list(head))           # [3, 1, 4]
insert_after(head, 5)
print(to_list(head))           # [3, 5, 1, 4]
delete_after(head.next)
print(to_list(head))           # [3, 5, 4]

The body of insert_after is two lines and that of delete_after is one, and neither contains a loop depending on the length of the list. That is what $\Theta(1)$ amounts to. By contrast to_list follows $\mathrm{next}$ to the end and therefore costs $\Theta(n)$; even merely learning the length requires a full traversal (keeping a separate element count makes it $\Theta(1)$).

Remark 4.4（Sentinel nodes）

Implementations commonly place one dummy node carrying no value (a sentinel) at the front and keep a reference to the sentinel instead of $\mathrm{head}$. Then “insert at the front” and “delete the first element” both become “insert or delete right after the sentinel”, and part 1 of Proposition 4.2 applies verbatim. Testing for the empty list becomes testing whether the sentinel’s $\mathrm{next}$ is $\mathrm{nil}$. Fewer cases mean fewer bugs, so it is a good idea to start from a sentinel when implementing.

5. Comparing the two representations

Let us line up the results so far. First compare how the two look in memory.

Memory layout of an array and of a linked list. Array addresses are computed from the index; linked-list nodes can only be reached by following references.

Collecting Proposition 3.2, Proposition 4.2 and Theorem 3.3 gives the following table. The linked list is assumed to keep a reference to its last node as well.

operation	dynamic array	singly linked list
read or write the $i$-th element	$\Theta(1)$	$\Theta(i)$ (worst case $\Theta(n)$)
search by value (no order assumed)	$\Theta(n)$	$\Theta(n)$
search by value (sorted)	$\Theta(\log n)$ (binary search)	$\Theta(n)$
insert at the front, delete the first	$\Theta(n)$	$\Theta(1)$
append at the end	amortized $\Theta(1)$	$\Theta(1)$
delete the last element	$\Theta(1)$	$\Theta(n)$ (needs the preceding node)
insert or delete at a position given by index $i$	$\Theta(n-i)$	$\Theta(i)$
insert or delete right after a node in hand	$\Theta(n-i)$	$\Theta(1)$
memory beyond the elements themselves	unused capacity (up to about the element count)	one reference per node

The second-to-last row captures the characters of the two most sharply. “Put something next to where I am” is $\Theta(1)$ for the linked list and $\Theta(n-i)$ for the array. Conversely “jump to the $i$-th element” is $\Theta(1)$ for the array and $\Theta(i)$ for the linked list. The choice is decided by how often each of these two kinds of operation is used.

Caution

One sometimes hears that “arrays search in $O(1)$”, which is not accurate. What is $O(1)$ is indexed access $A[i]$. Searching for the location of a value $x$ costs $\Theta(n)$ unless something is assumed about the order (part 2 of Proposition 3.2). A sorted array admits binary search in $\Theta(\log n)$ (Theorem 3.3［探索アルゴリズム］), but only because the middle element can be reached in constant time; the same trick is unavailable in a linked list. For how to keep an array sorted see Sorting algorithms, and for the details of searching see Search algorithms.

Remark 5.1（Constant factors and the cache）

The $\Theta$ notation hides constant factors, and in measurements what is hidden can matter. Modern CPUs fetch main memory not word by word but in cache lines (typically 64 bytes), so scanning an array from the front loads several elements into the cache per fetch. In a linked-list traversal the address of the next node is unknown until the current one has been read, and the more the nodes are scattered in memory, the more cache misses occur.

As a result, the judgement “many insertions in the middle, therefore a linked list” is sometimes contradicted by measurement up to element counts in the thousands. When in doubt, write it with a dynamic array first, measure, and then decide.

6. Stacks

From here we move to the side of abstract data types. A stack is a type specified by one thing only: what goes in last comes out first (last in, first out, LIFO).

Definition 6.1（Stack）

A stack is the abstract data type with the following operations. Write $X$ for the type of values and $\mathcal{S}$ for the set of stacks.

• $\mathrm{empty} \in \mathcal{S}$ (the empty stack)
• $\mathrm{push} : \mathcal{S} \times X \to \mathcal{S}$ (put on top)
• $\mathrm{pop} : \mathcal{S} \to \mathcal{S}$ (remove the top)
• $\mathrm{top} : \mathcal{S} \to X$ (read the top)
• $\mathrm{isEmpty} : \mathcal{S} \to \{\mathrm{true}, \mathrm{false}\}$

These satisfy the following axioms for all $S \in \mathcal{S}$ and $x \in X$.

$$\begin{aligned} &\mathrm{isEmpty}(\mathrm{empty}) = \mathrm{true}, \qquad \mathrm{isEmpty}(\mathrm{push}(S, x)) = \mathrm{false}, \\ &\mathrm{top}(\mathrm{push}(S, x)) = x, \qquad \mathrm{pop}(\mathrm{push}(S, x)) = S. \end{aligned}$$

$\mathrm{top}(\mathrm{empty})$ and $\mathrm{pop}(\mathrm{empty})$ are undefined (an implementation raises an error).

The axiom $\mathrm{pop}(\mathrm{push}(S, x)) = S$ is LIFO itself: push $x$ and then remove it, and you are back exactly where you started. Nowhere in these four equations do arrays or nodes appear. Whatever the implementation, if it satisfies them it is a stack. There are two implementations, and the cost of each can be read off from results we already have.

Implementation by a dynamic array. Store the elements as $A[0], \ldots, A[n-1]$ with the top at $A[n-1]$. Then $\mathrm{push}$ is an append at the end and so is amortized $\Theta(1)$ (Theorem 3.3), while $\mathrm{pop}$ is $n \leftarrow n-1$ and $\mathrm{top}$ is a read of $A[n-1]$, both worst-case $\Theta(1)$ (part 1 of Proposition 3.2). The element moves demanded by part 3 of Proposition 3.2 do not arise, because at the end $n - i = 0$.

Implementation by a linked list. Let the top be the first node, with $\mathrm{push}$ an insertion at the front and $\mathrm{pop}$ a deletion of the first node. With a sentinel, both reduce to part 1 of Proposition 4.2 and are worst-case $\Theta(1)$. Since this is $\Theta(1)$ in the worst case rather than amortized, it is preferable where a bound on the latency of a single operation is required. The price is one reference per node of extra space.

Let us look at one use of a stack in a form we can prove: deciding whether brackets match.

Theorem 6.2（Recognising balanced bracket strings）

Let the alphabet be $\Sigma = \{\,\texttt{(}\,,\,\texttt{)}\,,\,\texttt{[}\,,\,\texttt{]}\,\}$ and define the set $B \subseteq \Sigma^{*}$ of balanced bracket strings as the smallest set generated by the following three rules.

$$\varepsilon \in B, \qquad w \in B \implies \texttt{(} w \texttt{)} \in B \ \text{and}\ \texttt{[} w \texttt{]} \in B, \qquad u, v \in B \implies uv \in B.$$

Consider the following algorithm $\mathcal{A}$ on an input $w \in \Sigma^{*}$. Start with an empty stack $S$ and read $w$ one symbol at a time from the left.

• If the symbol read is an opening bracket, $\mathrm{push}$ it onto $S$.
• If it is a closing bracket, reject immediately if $S$ is empty; otherwise read $\mathrm{top}$, $\mathrm{pop}$, and reject if the symbol removed is not the opening bracket of the same kind as this closing bracket.

When all symbols have been read, accept if $S$ is empty and reject otherwise. Then $\mathcal{A}$ accepts $w$ if and only if $w \in B$. Moreover the running time of $\mathcal{A}$ is $\Theta(|w|)$.

Proof（Theorem 6.2）

Preliminary (relativity of the stack). $\mathcal{A}$ consults only the top of the stack, and it rejects the moment it tries to $\mathrm{pop}$ an empty stack. Hence a run processing $u$ from an initial stack $\sigma$ and a run processing the same $u$ from the empty stack undergo exactly the same changes above $\sigma$, except in the case where the latter rejects because of a ”$\mathrm{pop}$ from empty”. We use this fact repeatedly below.

($\Rightarrow$) If $w \in B$ then $\mathcal{A}$ accepts. We prove the following stronger statement by structural induction on the generation rules of $B$.

If $w \in B$ then, from any initial stack $\sigma$, processing $w$ causes $\mathcal{A}$ not to reject, and the stack afterwards is again $\sigma$.

• Case $w = \varepsilon$. Nothing is read, so there is no rejection and the stack remains $\sigma$.
• Case $w = \texttt{(} u \texttt{)}$ with $u \in B$. Reading the initial $\texttt{(}$ makes the stack $\sigma\texttt{(}$. Applying the induction hypothesis to $u$ with initial stack $\sigma\texttt{(}$, there is no rejection and the stack afterwards is again $\sigma\texttt{(}$. Reading $\texttt{)}$ next, the stack is non-empty and its top is $\texttt{(}$, so the $\mathrm{pop}$ matches in kind and there is no rejection. The stack afterwards is $\sigma$. The case $w = \texttt{[} u \texttt{]}$ is identical.
• Case $w = uv$ with $u, v \in B$. Applying the induction hypothesis to $u$ with initial stack $\sigma$, there is no rejection and the stack returns to $\sigma$. Applying the same hypothesis to $v$, again there is no rejection and the stack is $\sigma$.

Taking $\sigma$ to be the empty stack in particular, $\mathcal{A}$ does not reject, and the stack after reading everything is empty, so it accepts.

($\Leftarrow$) If $\mathcal{A}$ accepts then $w \in B$. We argue by strong induction on $|w|$. If $w = \varepsilon$ then $w \in B$ by the first rule. Suppose $|w| \ge 1$.

If $w_1$ were a closing bracket, the stack would be empty at that moment and $\mathcal{A}$ would reject, contradicting the hypothesis. So $w_1$ is an opening bracket; write it $c$ and write $\bar{c}$ for the matching closing bracket. The symbol $c$ is pushed at position 1, and since the stack is empty on acceptance, it is popped somewhere. Say this happens when the $j$-th symbol is read.

Since $c$ sits at the bottom of the stack and is removed for the first time at position $j$, it remains on the stack throughout the processing of positions $2, \ldots, j-1$. That is, the processing of $u = w_2 \cdots w_{j-1}$ takes place entirely above $c$, and the stack immediately before position $j$ consists of exactly the one symbol $c$. By the preliminary observation, processing $u$ from an empty stack likewise causes no rejection and ends with an empty stack. Since $|u| < |w|$, the induction hypothesis gives $u \in B$.

At position $j$ the symbol $c$ is popped, and since $\mathcal{A}$ did not reject, $w_j = \bar{c}$. The processing of the remainder $v = w_{j+1} \cdots w_{|w|}$ starts from an empty stack, and since the whole input is accepted, it ends with an empty stack. As $|v| < |w|$, we get $v \in B$. Hence $w = c\,u\,\bar{c}\,v$, and the second rule gives $c u \bar{c} \in B$ while the third gives $w \in B$.

Cost. Each symbol causes at most one $\mathrm{push}$ or one $\mathrm{pop}$ together with at most one $\mathrm{top}$, and with the linked-list implementation these are worst-case $\Theta(1)$ (part 1 of Proposition 4.2). Hence the total is $\Theta(|w|)$.

∎

Example 6.3（Running the recogniser）

We trace $\mathcal{A}$ on $w = \texttt{([])()}$. The stack is written with its bottom on the left.

symbol read	action	stack afterwards
$\texttt{(}$	push	$\texttt{(}$
$\texttt{[}$	push	$\texttt{([}$
$\texttt{]}$	pop (matches $\texttt{[}$)	$\texttt{(}$
$\texttt{)}$	pop (matches $\texttt{(}$)	empty
$\texttt{(}$	push	$\texttt{(}$
$\texttt{)}$	pop (matches $\texttt{(}$)	empty

The stack is empty at the end of the input, so the string is accepted. Indeed $\texttt{([])} \in B$ and $\texttt{()} \in B$, so the third rule gives $w \in B$. By contrast, for $w' = \texttt{(]}$ the $\mathrm{pop}$ at the second symbol yields $\texttt{(}$, a different kind from $\texttt{]}$, so the string is rejected. For $w'' = \texttt{(()}$ no rejection occurs during the scan, but one $\texttt{(}$ is left on the stack at the end, so it is rejected. The implementation is as follows.

def is_balanced(w: str) -> bool:
    partner = {")": "(", "]": "["}
    stack = []
    for c in w:
        if c in "([":
            stack.append(c)
        elif c in ")]":
            if not stack or stack.pop() != partner[c]:
                return False
        else:
            raise ValueError(f"unexpected symbol: {c!r}")
    return not stack


print(is_balanced("([])()"))   # True
print(is_balanced("(]"))       # False
print(is_balanced("(()"))      # False

The final return not stack corresponds to the acceptance condition “the stack is empty at the end”. Forget that one line and "(((" is accepted.

This recogniser has the same shape as depth-first search and as the management of recursive calls. Wherever the structure “close what has been opened in the reverse order of opening” appears, a stack is usually there.

7. Queues

A queue is the type in which what goes in first comes out first (first in, first out, FIFO). It obeys the same discipline as a line at a counter, which is why it is also called a waiting line.

Definition 7.1（Queue）

A queue is the abstract data type with the following operations. Write $X$ for the type of values and $\mathcal{Q}$ for the set of queues.

• $\mathrm{empty} \in \mathcal{Q}$ (the empty queue)
• $\mathrm{enqueue} : \mathcal{Q} \times X \to \mathcal{Q}$ (add at the back)
• $\mathrm{dequeue} : \mathcal{Q} \to \mathcal{Q}$ (remove the front)
• $\mathrm{front} : \mathcal{Q} \to X$ (read the front)
• $\mathrm{isEmpty} : \mathcal{Q} \to \{\mathrm{true}, \mathrm{false}\}$

These satisfy the following axioms for all $Q \in \mathcal{Q}$ and $x \in X$.

$$\begin{aligned} &\mathrm{isEmpty}(\mathrm{empty}) = \mathrm{true}, \qquad \mathrm{isEmpty}(\mathrm{enqueue}(Q, x)) = \mathrm{false}, \\[2pt] &\mathrm{front}(\mathrm{enqueue}(Q, x)) = \begin{cases} x & (Q = \mathrm{empty}) \\ \mathrm{front}(Q) & (Q \ne \mathrm{empty}) \end{cases} \\[2pt] &\mathrm{dequeue}(\mathrm{enqueue}(Q, x)) = \begin{cases} \mathrm{empty} & (Q = \mathrm{empty}) \\ \mathrm{enqueue}(\mathrm{dequeue}(Q), x) & (Q \ne \mathrm{empty}) \end{cases} \end{aligned}$$

$\mathrm{front}(\mathrm{empty})$ and $\mathrm{dequeue}(\mathrm{empty})$ are undefined.

Compare this with Definition 6.1. For a stack, $\mathrm{pop}(\mathrm{push}(S,x)) = S$: what was just pushed comes straight back off. For a queue, $\mathrm{dequeue}$ slips past $\mathrm{enqueue}$ and burrows further in. This slipping past is what FIFO is, and it is why recursion appears on the right-hand side of the axioms.

The naive array implementation does not work. If the front is always kept at $A[0]$, then $\mathrm{enqueue}$ is an append at the end and so is amortized $\Theta(1)$, but $\mathrm{dequeue}$ is a deletion at position $0$, hence $\Theta(n)$ by part 3 of Proposition 3.2, giving $\Theta(n^2)$ over $n$ operations. The culprit is pinning the front to $A[0]$, so unpinning it solves the problem.

Proposition 7.2（Ring buffer）

Maintain an array $A[0..m-1]$ of capacity $m$, a front position $h$ ($0 \le h \le m-1$) and an element count $n$ ($0 \le n \le m$), with the operations defined as follows.

• $\mathrm{enqueue}(x)$: when $n < m$, set $A[(h + n) \bmod m] \leftarrow x$ and $n \leftarrow n + 1$.
• $\mathrm{dequeue}()$: when $n > 0$, return $A[h]$, then set $h \leftarrow (h + 1) \bmod m$ and $n \leftarrow n - 1$.
• $\mathrm{front}()$: when $n > 0$, return $A[h]$.

Then, writing the contents of the queue from the front as $q_0, q_1, \ldots, q_{n-1}$, the identity $q_i = A[(h + i) \bmod m]$ holds at all times, and the axioms of Definition 7.1 are satisfied. Moreover each of the three operations takes worst-case $\Theta(1)$ time.

Proof（Proposition 7.2）

We prove the asserted identity $q_i = A[(h+i) \bmod m]$ ($0 \le i \le n-1$) as an invariant, by induction on the number of operations.

In the initial state $n = 0$, so the condition holds vacuously.

Case $\mathrm{enqueue}(x)$. The new contents are $q_0, \ldots, q_{n-1}, x$ and $h$ is unchanged. We check that the target position $(h+n) \bmod m$ does not coincide with an existing position $(h+i) \bmod m$ ($0 \le i \le n-1$). From $0 \le i < n \le m-1$ the difference between $i$ and $n$ cannot be a multiple of $m$, so the two differ modulo $m$. Hence no existing element is destroyed, and the new last element satisfies the identity as the element with index $n$.

Case $\mathrm{dequeue}()$. The value returned is $A[h] = q_0$, the front of the queue. Renumbering the new contents $q_1, \ldots, q_{n-1}$ as $q'_0, \ldots, q'_{n-2}$ and setting $h' = (h+1) \bmod m$, we get

$$q'_i = q_{i+1} = A[(h + i + 1) \bmod m] = A[(h' + i) \bmod m]$$

so the invariant is preserved.

That $\mathrm{front}()$ returns $q_0$ is the case $i = 0$ itself. Hence $\mathrm{dequeue}$ and $\mathrm{front}$ always act on the front element while $\mathrm{enqueue}$ adds only at the back, so the axioms of Definition 7.1 are satisfied. As for the cost, each operation consists of a constant number of additions, remainders and comparisons together with one array access ($\Theta(1)$ by part 1 of Proposition 3.2), hence worst-case $\Theta(1)$.

∎

Example 7.3（A ring buffer of capacity 4）

Take $m = 4$ and start from $h = 0$, $n = 0$. Unused cells of $A$ are written _.

operation	cell written / read	$A$	$h$	$n$
$\mathrm{enqueue}(a)$	$A[(0+0) \bmod 4] = A[0]$	a _ _ _	0	1
$\mathrm{enqueue}(b)$	$A[1]$	a b _ _	0	2
$\mathrm{enqueue}(c)$	$A[2]$	a b c _	0	3
$\mathrm{dequeue}()$	$A[0] = a$	a b c _	1	2
$\mathrm{enqueue}(d)$	$A[(1+2) \bmod 4] = A[3]$	a b c d	1	3
$\mathrm{enqueue}(e)$	$A[(1+3) \bmod 4] = A[0]$	e b c d	1	4
$\mathrm{dequeue}()$	$A[1] = b$	e b c d	2	3

In the final state the queue contains $c, d, e$, and as the invariant demands, $A[(2+0) \bmod 4] = A[2] = c$, $A[3] = d$ and $A[(2+2) \bmod 4] = A[0] = e$. Writing $e$ runs off the right end of the array and wraps to the left end — hence the name “ring” — and not a single element has been moved.

Remark 7.4（Distinguishing full from empty, and growing the capacity）

Some implementations keep only $h$ and the position past the back, $t = (h+n) \bmod m$; but then $t = h$ both when $n = 0$ and when $n = m$, so full and empty cannot be told apart. There are two remedies: keep the element count $n$ explicitly, as in Proposition 7.2 above, or always leave one cell free so that the effective capacity is $m-1$.

When the buffer fills up, allocate an array of capacity $2m$ and repack the elements from the front. The cost and frequency of this growth have exactly the same form as in Theorem 3.3, so $\mathrm{enqueue}$ stays amortized $\Theta(1)$. With a linked-list implementation holding references to both the front and the back, both operations are worst-case $\Theta(1)$ by part 1 of Proposition 4.2.

Stacks drive depth-first search and queues drive breadth-first search. Both are central to Graph algorithms: that breadth-first search computes shortest distances correctly follows from the FIFO discipline of the queue (Theorem 3.2［グラフアルゴリズム］), and in depth-first search the vertices under processing form exactly a stack (Lemma 4.1［グラフアルゴリズム］). Dynamic programming, in turn, uses an array as a table and relies entirely on $\Theta(1)$ indexed access (Theorem 3.2［動的計画法］).

8. The potential method and a queue from two stacks

In Theorem 3.3 we counted the total cost directly (the aggregate method). When there are several kinds of operation that influence one another, such counting becomes hard. The tool for that situation is the potential method: represent the “accumulated work” stored in the data structure by a real-valued function and watch how it rises and falls with each operation.

Lemma 8.1（The potential method）

Let a sequence of states $D_0, D_1, \ldots, D_m$ of a data structure be given ($D_0$ the initial state and $D_i$ the state just after the $i$-th operation), together with the actual cost $c_i$ of the $i$-th operation. Suppose a real-valued function $\Phi$ on the set of states satisfies

$$\Phi(D_i) \ge \Phi(D_0) \qquad (i = 0, 1, \ldots, m)$$

Defining the amortized cost by $\hat{c}_i := c_i + \Phi(D_i) - \Phi(D_{i-1})$, we have

$$\sum_{i=1}^{m} c_i = \sum_{i=1}^{m} \hat{c}_i + \Phi(D_0) - \Phi(D_m) \le \sum_{i=1}^{m} \hat{c}_i$$

In particular, if some constant $a$ satisfies $\hat{c}_i \le a$ for all $i$, then the total cost of $m$ operations is at most $am$.

Proof（Lemma 8.1）

By definition,

$$\sum_{i=1}^{m} \hat{c}_i = \sum_{i=1}^{m} c_i + \sum_{i=1}^{m}\bigl(\Phi(D_i) - \Phi(D_{i-1})\bigr)$$

The second sum on the right telescopes: adjacent terms cancel, leaving $\Phi(D_m) - \Phi(D_0)$. Hence

$$\sum_{i=1}^{m} \hat{c}_i = \sum_{i=1}^{m} c_i + \Phi(D_m) - \Phi(D_0)$$

and rearranging gives the equality. By hypothesis $\Phi(D_m) \ge \Phi(D_0)$, that is $\Phi(D_0) - \Phi(D_m) \le 0$, so the inequality follows. The last assertion is immediate from $\sum \hat{c}_i \le am$.

∎

Think of $\Phi$ as the debt carried by the current state. Cheap operations run up a little debt at a time, and an expensive operation repays it all at once. At the moment of repayment the actual cost is large, but $\Phi$ drops sharply, so the amortized cost is small.

Theorem 8.2（A queue from two stacks）

Take two stacks all of whose operations are worst-case $\Theta(1)$ (for instance the linked-list implementation based on part 1 of Proposition 4.2), and call them $\mathrm{in}$ and $\mathrm{out}$. Define the operations as follows.

• $\mathrm{enqueue}(x)$: $\mathrm{push}$ $x$ onto $\mathrm{in}$.
• $\mathrm{dequeue}()$: if $\mathrm{out}$ is empty, repeat ”$\mathrm{pop}$ from $\mathrm{in}$ and $\mathrm{push}$ onto $\mathrm{out}$” until $\mathrm{in}$ is empty. Then, if $\mathrm{out}$ is empty raise an error; otherwise $\mathrm{pop}$ from $\mathrm{out}$ and return the result.
• $\mathrm{front}()$: perform the same transfer, then return the $\mathrm{top}$ of $\mathrm{out}$.

Then this implementation satisfies the axioms of Definition 7.1. Moreover the total cost of any sequence of $m$ operations starting from the empty state is at most $3m$, so the amortized cost per operation is $O(1)$. The worst-case cost of an individual $\mathrm{dequeue}$, however, is $\Theta(n)$, where $n$ is the number of elements at that moment.

Proof（Theorem 8.2）

Correctness. Write the contents of the queue from the front as $q_0, \ldots, q_{n-1}$ and take the following as the invariant.

There exists an $r$ ($0 \le r \le n$) such that reading $\mathrm{out}$ from the top to the bottom gives $q_0, q_1, \ldots, q_{r-1}$, and reading $\mathrm{in}$ from the bottom to the top gives $q_r, q_{r+1}, \ldots, q_{n-1}$.

Initially $n = 0$ and both stacks are empty, so the invariant holds with $r = 0$.

Under $\mathrm{enqueue}(x)$, reading $\mathrm{in}$ from the bottom gives $q_r, \ldots, q_{n-1}, x$, and the new contents of the queue are $q_0, \ldots, q_{n-1}, x$, so the invariant is preserved with the same $r$.

A transfer occurs when $\mathrm{out}$ is empty, that is when $r = 0$, and then reading $\mathrm{in}$ from the bottom gives $q_0, \ldots, q_{n-1}$. The order in which elements are popped from $\mathrm{in}$ is $q_{n-1}, \ldots, q_0$, and pushing them onto $\mathrm{out}$ in that order makes $\mathrm{out}$ read $q_{n-1}, \ldots, q_0$ from the bottom, that is $q_0, \ldots, q_{n-1}$ from the top. Since $\mathrm{in}$ is now empty, the invariant holds with $r = n$. The order is reversed twice and thereby restored: that is the trick of this implementation.

When $\mathrm{out}$ is non-empty ($r \ge 1$), its top is $q_0$ by the invariant, that is the front of the queue. Hence $\mathrm{front}$ returns $q_0$ and $\mathrm{dequeue}$ removes $q_0$. After the removal, $\mathrm{out}$ holds $q_1, \ldots, q_{r-1}$ from the top, so after renumbering the invariant is preserved with $r' = r - 1$. When $n = 0$ both stacks are empty, and $\mathrm{out}$ remains empty even after a transfer, so an error is raised — consistent with Definition 7.1 leaving $\mathrm{dequeue}(\mathrm{empty})$ undefined.

Amortized cost. Define the potential by

$$\Phi := 2 \cdot (\text{number of elements in } \mathrm{in})$$

Then $\Phi \ge 0$ and $\Phi(D_0) = 0$ in the initial state, so the hypothesis $\Phi(D_i) \ge \Phi(D_0)$ of Lemma 8.1 is met. We count one stack operation as cost 1 (by assumption it takes worst-case $\Theta(1)$ time).

• $\mathrm{enqueue}$: the actual cost is one $\mathrm{push}$, so $c = 1$. The number of elements in $\mathrm{in}$ grows by one, so $\Delta\Phi = 2$. Hence $\hat{c} = 1 + 2 = 3$.
• $\mathrm{dequeue}$ with $\mathrm{out}$ non-empty: the actual cost is one $\mathrm{pop}$, so $c = 1$. Nothing changes in $\mathrm{in}$, so $\Delta\Phi = 0$. Hence $\hat{c} = 1$.
• $\mathrm{dequeue}$ with $\mathrm{out}$ empty and $k \ge 1$ elements in $\mathrm{in}$: the transfer performs $k$ pops and $k$ pushes, and the subsequent pop is one more, so $c = 2k + 1$. The number of elements in $\mathrm{in}$ falls from $k$ to $0$, so $\Delta\Phi = -2k$. Hence $\hat{c} = 2k + 1 - 2k = 1$.
• $\mathrm{front}$: it only reads $\mathrm{top}$ instead of popping, so the same computations as in the previous two cases give $\hat{c} = 1$.

In every case $\hat{c} \le 3$. By Lemma 8.1, the total cost of $m$ operations is at most $3m$ and the amortized cost per operation is $O(1)$.

Worst case. A $\mathrm{dequeue}$ in the state where all $n$ elements are on $\mathrm{in}$ and $\mathrm{out}$ is empty performs $2n + 1$ stack operations, hence $\Theta(n)$. This does not contradict the amortized bound of $O(1)$, because before such an expensive $\mathrm{dequeue}$ can occur, $n$ enqueues are needed to pile up the $n$ elements.

∎

flowchart LR
E["enqueue x pushes onto in"] --> I["stack in (from the bottom: c, d, e)"]
I -->|"when out is empty, move until in is empty"| O["stack out (from the top: c, d, e)"]
O --> D["dequeue pops the top of out"]

A queue built from two stacks. Moving from in to out reverses the order, bringing the oldest element to the top of out.

Example 8.3（Running the two stacks）

Here is an implementation together with a trace following the changes in $\Phi$.

class TwoStackQueue:
    def __init__(self):
        self._in = []    # the last entry is the top
        self._out = []   # the last entry is the top

    def enqueue(self, x):
        self._in.append(x)

    def _transfer(self):
        while self._in:
            self._out.append(self._in.pop())

    def dequeue(self):
        if not self._out:
            self._transfer()
        if not self._out:
            raise IndexError("dequeue from empty queue")
        return self._out.pop()

    def front(self):
        if not self._out:
            self._transfer()
        if not self._out:
            raise IndexError("front of empty queue")
        return self._out[-1]

    def __len__(self):
        return len(self._in) + len(self._out)


q = TwoStackQueue()
for x in "abc":
    q.enqueue(x)
print(q.dequeue(), q.dequeue())   # a b
q.enqueue("d")
print(q.dequeue(), q.dequeue())   # c d

The actual cost $c$, the potential $\Phi = 2\,|\mathrm{in}|$ and the amortized cost $\hat{c} = c + \Delta\Phi$ of each operation come out as follows.

operation	$\mathrm{in}$ afterwards (from the bottom)	$\mathrm{out}$ afterwards (from the top)	$c$	$\Phi$	$\hat{c}$
initial state	—	—	—	0	—
$\mathrm{enqueue}(a)$	$a$	—	1	2	3
$\mathrm{enqueue}(b)$	$a, b$	—	1	4	3
$\mathrm{enqueue}(c)$	$a, b, c$	—	1	6	3
$\mathrm{dequeue}() = a$	—	$b, c$	7	0	1
$\mathrm{dequeue}() = b$	—	$c$	1	0	1
$\mathrm{enqueue}(d)$	$d$	$c$	1	2	3
$\mathrm{dequeue}() = c$	$d$	—	1	2	1
$\mathrm{dequeue}() = d$	—	—	3	0	1

The $\mathrm{dequeue}$ on the fourth row stands out with an actual cost of $7$ (three pops, three pushes, one pop), but $\Phi$ falls from $6$ to $0$, so its amortized cost is $1$. The total actual cost is $16$ over $8$ operations, below the bound $3 \times 8 = 24$ of Lemma 8.1.

9. Exercises

Exercise 9.1Easy

Using only the axioms of Definition 7.1, derive the following equation, stating explicitly which axiom is used at each step.

$$\mathrm{dequeue}\bigl(\mathrm{enqueue}(\mathrm{enqueue}(\mathrm{empty}, a), b)\bigr) = \mathrm{enqueue}(\mathrm{empty}, b)$$

Then use this result together with the axioms for $\mathrm{front}$ to confirm that removing one element from the queue built by inserting $a$ and then $b$ leaves $b$.

Solution

Put $Q := \mathrm{enqueue}(\mathrm{empty}, a)$. Applying the axiom $\mathrm{isEmpty}(\mathrm{enqueue}(Q', x)) = \mathrm{false}$ with $Q' = \mathrm{empty}$ and $x = a$ gives $Q \ne \mathrm{empty}$. Hence the second case of the $\mathrm{dequeue}$ axiom applies:

$$\mathrm{dequeue}(\mathrm{enqueue}(Q, b)) = \mathrm{enqueue}(\mathrm{dequeue}(Q), b)$$

Next, applying the first case of the same axiom (the inner argument being $\mathrm{empty}$) to $\mathrm{dequeue}(Q) = \mathrm{dequeue}(\mathrm{enqueue}(\mathrm{empty}, a))$ gives $\mathrm{dequeue}(Q) = \mathrm{empty}$. Substituting,

$$\mathrm{dequeue}(\mathrm{enqueue}(Q, b)) = \mathrm{enqueue}(\mathrm{empty}, b)$$

as required.

Furthermore, the first case of the $\mathrm{front}$ axiom gives $\mathrm{front}(\mathrm{enqueue}(\mathrm{empty}, b)) = b$. The element $a$, inserted first, left first: this is indeed FIFO. Carrying out the same computation with the axioms of Definition 6.1 gives $\mathrm{pop}(\mathrm{push}(\mathrm{push}(\mathrm{empty}, a), b)) = \mathrm{push}(\mathrm{empty}, a)$, leaving $a$. The difference in the axioms is exactly the difference in behaviour.

Exercise 9.2Standard

Write a procedure reversing a singly linked list in $\Theta(n)$ time and $O(1)$ additional space. Create no new nodes; only rewrite the $\mathrm{next}$ fields of the existing ones. State a loop invariant and use it to prove correctness.

Solution

Three variables suffice.

def reverse(head):
    prev = None
    cur = head
    while cur is not None:
        nxt = cur.next     # save it first, or we lose our way the moment next is overwritten
        cur.next = prev    # flip the direction
        prev = cur
        cur = nxt
    return prev

Invariant. Write the original list as $p_0, p_1, \ldots, p_{n-1}$. At the start of each iteration the following hold for some $k$ ($0 \le k \le n$).

• prev is the head of the list consisting of $p_{k-1}, p_{k-2}, \ldots, p_0$ in that order ($\mathrm{nil}$ when $k = 0$).
• cur is $p_k$ ($\mathrm{nil}$ when $k = n$).
• The two lists are disjoint and together comprise all the original nodes.

Initialisation. Just before entering the loop, prev = None and cur = head $= p_0$, so the invariant holds with $k = 0$.

Maintenance. Suppose the invariant holds with $k$ at the start of an iteration and cur $= p_k \ne \mathrm{nil}$. We save $p_{k+1}$ (or $\mathrm{nil}$ if it does not exist) in nxt. The assignment cur.next = prev makes $p_{k-1}$ follow $p_k$, so the list starting at prev becomes $p_k, p_{k-1}, \ldots, p_0$. The only thing lost by this assignment is the reference from $p_k$ to $p_{k+1}$, and that is safely stored in nxt. Finally prev = cur and cur = nxt make the invariant hold for $k+1$.

Termination. The loop ends when cur is $\mathrm{nil}$, that is when $k = n$. By the invariant, prev is the head of the list $p_{n-1}, \ldots, p_0$, which is the reversal of the original list.

Cost. The loop runs exactly once per node, $n$ times in total, and one pass through the body consists of four assignments, hence constant time (for the same reason as part 1 of Proposition 4.2). So the time is $\Theta(n)$. The extra memory is three variables, hence $O(1)$.

Note that omitting the save into nxt destroys any means of reaching $p_{k+1}$ after cur.next = prev, because, as the proof of part 2 of Proposition 4.2 shows, the address of a node can only be obtained by following references.

Exercise 9.3Hard

Add to the dynamic array of Theorem 3.3 an element removal $\mathrm{pop}$ together with a shrinking rule for returning memory.

1. With the rule “after a $\mathrm{pop}$, halve the capacity as soon as the element count drops to at most half the capacity”, amortized $O(1)$ fails. Construct an explicit sequence of operations for which $m$ operations cost $\Theta(m^2)$ in total.
2. With the rule “halve the capacity as soon as the element count falls below one quarter of the capacity”, the amortized costs of $\mathrm{push}$ and $\mathrm{pop}$ stay constant. Estimate how many operations must occur between two consecutive capacity changes, and explain why.

Solution

1. Start from capacity $c = m_0$ with $n = m_0$ elements (full) and alternate $\mathrm{push}$ and $\mathrm{pop}$.

• $\mathrm{push}$: the array is full, so the capacity grows to $2m_0$ and $m_0$ elements are copied. Afterwards $n = m_0 + 1$, $c = 2m_0$.
• $\mathrm{pop}$: afterwards $n = m_0$, and since $m_0 \le 2m_0/2 = m_0$, the shrinking rule fires, the capacity returns to $m_0$, and $m_0$ elements are copied.

This restores the initial state exactly, so the same thing repeats forever. Every two operations cause $2m_0$ copies, so the total cost is $\Theta(m \cdot m_0)$, which is $\Theta(m^2)$ if we take $m_0 = \Theta(m)$. The cause is that the threshold for growing and the threshold for shrinking sit at the same point.

2. Separating the thresholds means that immediately after a capacity change we land far from either boundary. Look at the state just after a change.

• Just after growing: capacity $c$, element count $n = c/2$.
• Just after shrinking: the capacity before was $2c$, and the count had just fallen below $2c/4 = c/2$, so $n = c/2$ (up to an error of one). The capacity is $c$.

In both cases $n \approx c/2$. For the next growth, $n$ must reach $c$, requiring at least $c/2$ pushes; for the next shrink, $n$ must fall below $c/4$, requiring at least $c/4$ pops. Hence at least $c/4$ operations lie between two consecutive capacity changes.

A capacity change at capacity $c$ costs $\Theta(c)$, and spreading this over the at least $c/4$ preceding operations gives a constant per operation. Formally, taking as the potential of Lemma 8.1

$$\Phi = \begin{cases} 2n - c & (n \ge c/2) \\ c/2 - n & (n < c/2) \end{cases}$$

one checks by cases on whether a growth or a shrink occurs that the amortized cost is bounded by a constant. The point is that both expressions vanish just after a capacity change ($n = c/2$) and grow as either boundary is approached.

References

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022 — Chapter 10 (Elementary Data Structures) covers arrays, linked lists, stacks and queues, and Chapter 16 (Amortized Analysis) covers the aggregate, accounting and potential methods. The analysis of the dynamic array (table doubling) is also in Chapter 16.
• D. E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd ed., Addison-Wesley, 1997 — §2.2 (Linear Lists). §2.2.1 treats stacks, queues and deques, §2.2.2 sequential allocation (arrays) and §2.2.3 linked allocation (linked lists), corresponding to §3 through §7 of this article. The historical background of linked lists is described in §2.6.
• A. V. Aho, J. E. Hopcroft, J. D. Ullman, Data Structures and Algorithms, Addison-Wesley, 1983 — Chapter 2 (Basic Abstract Data Types). The organisation of this article, fixing the abstract data type first and supplying implementations afterwards, follows the style of this book.
• R. E. Tarjan, “Amortized Computational Complexity”, SIAM Journal on Algebraic and Discrete Methods 6 (1985), 306–318. DOI: 10.1137/0606031 — the paper that systematically formulated amortized complexity and the potential method.
• R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley, 2011 — §1.3 (Bags, Queues, and Stacks). Implements stacks and queues both with resizing arrays and with linked lists, and compares measured running times.
• Ishihata Kiyoshi, Algorithm to Data Kōzō (Algorithms and Data Structures), Iwanami Shoten (Iwanami Lectures on Software Science 3), 1989 (in Japanese) — a well-regarded textbook available in Japanese, treating the various representations of linear lists in detail.

Appendix: Correspondence with the standard libraries of major languages

The data structures treated in this article are present as they stand in the standard libraries of the major languages. Since the names do not always reveal the implementation, we list the correspondences.

Dynamic arrays and linked lists. C++‘s std::vector, Java’s ArrayList and Python’s list are dynamic arrays. The growth factor differs by implementation: Java’s ArrayList uses roughly $1.5$, and CPython’s list roughly $1.125$ (the capacity grows as $0, 4, 8, 16, 25, 35, 46, 58, 72, 88, \ldots$); but as noted in Remark 3.5, any constant greater than $1$ preserves amortized $O(1)$. Linked lists appear as C++‘s std::list (doubly linked) and std::forward_list (singly linked), and Java’s LinkedList (doubly linked). Python’s standard library has no pure linked-list type because occasions calling for one are rare, and the circumstances of Remark 5.1 lie behind that too.

Stacks and queues. C++‘s std::stack and std::queue are adapters exposing only the interfaces of Definition 6.1 and Definition 7.1 over an existing container (std::deque by default), so the separation of abstract data type from implementation appears directly in the types. Java’s ArrayDeque is a ring buffer (Proposition 7.2) usable both as a stack and as a queue. In Python one uses list (with append and pop) for a stack and collections.deque (a doubly linked list of fixed-size blocks, with worst-case $O(1)$ addition and removal at both ends) for a queue. Using list as a queue via pop(0) costs $\Theta(n)$ per operation by part 3 of Proposition 3.2, hence $\Theta(n^2)$ over $n$ operations — a frequent cause of slowdowns in practice.