---
title: Elementary Data Structures
module: Data Structures
moduleNumber: 4
lessonNumber: 1
order: 401
summary: |
  Every container is built one of two ways: **contiguous** in an array, or
  **linked** through pointers. We trade cache-friendly random access against
  $O(1)$ splicing, derive the **amortized $O(1)$** append of a doubling dynamic
  array, and assemble the two ordered access disciplines — the LIFO **stack** and
  the FIFO **queue** (with its generalization, the **deque**) — on top of both.
topics: [Linear Structures]
sources:
  - book: CLRS
    ref: "Ch. 10 — Elementary Data Structures"
  - book: Skiena
    ref: "§3.1–3.2 — Contiguous vs. Linked Structures"
  - book: Erickson
    ref: "Ch. — Basic Data Structures"
practice:
  - title: 'Reverse Linked List'
    slug: reverse-linked-list
    difficulty: Easy
  - title: 'Valid Parentheses'
    slug: valid-parentheses
    difficulty: Easy
  - title: 'Implement Queue using Stacks'
    slug: implement-queue-using-stacks
    difficulty: Easy
  - title: 'LRU Cache'
    slug: lru-cache
    difficulty: Medium
  - title: 'Design Circular Deque'
    slug: design-circular-deque
    difficulty: Medium
---

Every data structure in this course (every tree, [heap](/algorithms/sorting/heaps-and-heapsort), [hash table](/algorithms/data-structures/hash-tables), and graph) is ultimately stored one of two ways, and the choice affects everything
built on top of it. Elements are laid out **contiguously**
in one block of memory, or scattered and joined
by **pointers**. This first lesson works out the two strategies
and the four ordered containers (array, linked list, stack, queue) that the
rest of the module builds on.

## Two ways to store a sequence

A **contiguous** structure stores its elements in a single block of memory, one
after another. An array of $n$ elements each of size $s$ occupies one run of $ns$
bytes, so element $i$ lives at a known offset from the start. A **linked**
structure stores each element in its own separately-allocated **node** and uses a
pointer in each node to find the next; the nodes may sit anywhere in memory.[^skiena-contig]

The contrast is sharp, and it drives every later choice:

- **Random access.** Contiguous wins outright. Element $i$ of an array is at
  address $base + i \cdot s$, computed with one multiply-add, so indexing is
  $O(1)$. In a linked list there is no address arithmetic; to reach the $i$-th
  node you must follow $i$ pointers, which is $O(n)$.
- **Splicing.** Linked wins outright. To insert or delete an element _given a
  pointer to its node_, a linked list rewires a constant number of pointers in
  $O(1)$; an array must shift every later element to keep the block contiguous,
  which is $O(n)$.
- **Cache locality.** Contiguous wins. A modern CPU reads memory in cache lines
  and prefetches sequentially, so a linear scan of an array is far faster than
  chasing pointers across scattered nodes, even though both are $\Theta(n)$
  comparisons. Constant factors, not [asymptotics](/algorithms/foundations/asymptotic-analysis), yet they are large.
- **Space overhead.** Linked pays per-element: every node carries one or two
  pointers besides its key. An array pays nothing per element but may reserve
  unused capacity (below).

> **Intuition.** Contiguous storage _is_ the random-access machine's native
> idiom — an array is just addressable memory with a type. Linked storage gets
> $O(1)$ structural edits by giving up the address arithmetic, at the cost of a
> pointer per node and a cache miss per hop.

$$
% caption: The same sequence $\langle 9,16,4\rangle$ stored two ways. Contiguous: one
%          block, element $i$ at $base + i\cdot s$, so indexing is address arithmetic.
%          Linked: three separately-allocated nodes scattered in memory, each pointing to
%          the next, so reaching element $i$ means following $i$ pointers.
\begin{tikzpicture}[
  cell/.style={draw, minimum width=10mm, minimum height=8mm, font=\small},
  node8/.style={draw, minimum width=8mm, minimum height=8mm, font=\small},
  >=stealth]
  \definecolor{acc}{HTML}{2348F2}
  % contiguous
  \node[font=\small, anchor=east] at (-0.4,0) {contiguous};
  \node[cell] (a0) at (0,0) {$9$};
  \node[cell, right=0mm of a0] (a1) {$16$};
  \node[cell, right=0mm of a1] (a2) {$4$};
  \node[font=\scriptsize, below=0.5mm of a0] {$base$};
  \node[font=\scriptsize, below=0.5mm of a1] {$+s$};
  \node[font=\scriptsize, below=0.5mm of a2] {$+2s$};
  % linked: scattered nodes
  \begin{scope}[yshift=-2.2cm]
    \node[font=\small, anchor=east] at (-0.4,0) {link\/ed};
    \node[node8] (b0) at (0.2,0.3) {$9$};
    \node[node8] (b1) at (2.4,-0.4) {$16$};
    \node[node8] (b2) at (4.3,0.2) {$4$};
    \draw[->, acc] (b0.east) to[bend right=18] (b1.north west);
    \draw[->, acc] (b1.east) to[bend left=18] (b2.south west);
    \node[font=\scriptsize] (hd) at (-1.1,0.3) {head};
    \draw[->, acc] (hd) -- (b0.west);
    \node[font=\scriptsize] at (5.7,0.2) {nil};
    \draw[->, acc] (b2.east) -- (5.35,0.2);
  \end{scope}
\end{tikzpicture}
$$

## Arrays and dynamic arrays

A fixed-size **array** is the contiguous structure in its purest form: allocate
$n$ slots up front, index any of them in $O(1)$. Its limitation is that
$n$ is fixed at allocation. Real programs rarely know the final size in advance,
so we want a structure that grows.

A **dynamic array** (C++ `vector`, Python `list`, Java `ArrayList`) keeps a
contiguous backing block of some **capacity** $\ge$ the current **size**, and
appends into the spare room. When the block fills, it allocates a _larger_ block,
copies the elements over, and frees the old one. The design decision that matters is
_how much_ larger, and the answer is to **double** the capacity.

```algorithm
caption: $\textsc{Append}(A, x)$ — push $x$, doubling the backing block on overflow
if $size(A) = capacity(A)$ then
  $cap' \gets \max(1, 2 \cdot capacity(A))$
  allocate new block $B$ of capacity $cap'$
  copy $A[0\,..\,size(A)-1]$ into $B$ // the $O(n)$ resize
  free old block; $store(A) \gets B$; $capacity(A) \gets cap'$
$A[size(A)] \gets x$
$size(A) \gets size(A) + 1$
```

A single append is usually $O(1)$, writing into spare room and bumping the size, but
the appends that trigger a resize cost $\Theta(n)$ because they copy the whole
array. The worst case of one operation is therefore $O(n)$. Yet the _average_
cost over a sequence of appends is $O(1)$, and this is worth proving.

$$
% caption: A resize on overflow. The full block of capacity $4$ cannot take a fifth
%          element, so a new block of capacity $8$ is allocated, the four elements are
%          copied over (the $\Theta(n)$ step, accented arrows), $x$ is written into the first spare
%          slot, and the old block is freed. The four trailing slots are
%          reserved-but-unused capacity.
\begin{tikzpicture}[
  >=stealth,
  cell/.style={draw, minimum width=8mm, minimum height=8mm, font=\small},
  empty/.style={draw, minimum width=8mm, minimum height=8mm}]
  \definecolor{acc}{HTML}{2348F2}
  % old full block (capacity 4, size 4)
  \node[font=\small, anchor=east] at (-0.65,0) {old, full};
  \node[cell] (o0) at (0,0) {$9$};
  \node[cell, right=0mm of o0] (o1) {$16$};
  \node[cell, right=0mm of o1] (o2) {$4$};
  \node[cell, right=0mm of o2] (o3) {$7$};
  \node[font=\scriptsize, right=2mm of o3] {capacit\/y $4$: full};
  % new block (capacity 8)
  \begin{scope}[yshift=-2.0cm]
    \node[font=\small, anchor=east] at (-0.65,0) {new};
    \node[cell, fill=acc!15] (n0) at (0,0) {$9$};
    \node[cell, fill=acc!15, right=0mm of n0] (n1) {$16$};
    \node[cell, fill=acc!15, right=0mm of n1] (n2) {$4$};
    \node[cell, fill=acc!15, right=0mm of n2] (n3) {$7$};
    \node[cell, draw=acc, very thick, right=0mm of n3] (n4) {$x$};
    \node[empty, right=0mm of n4] (n5) {};
    \node[empty, right=0mm of n5] (n6) {};
    \node[empty, right=0mm of n6] (n7) {};
    \node[font=\scriptsize, below=0.5mm of n1.south east] {capacit\/y $8$};
    \node[font=\scriptsize, below=0.5mm of n6.south] {spare};
  \end{scope}
  % copy arrows (the O(n) step)
  \foreach \i in {0,1,2,3} {
    \draw[->, acc] (o\i.south) -- (n\i.north);
  }
  \node[font=\scriptsize, acc, align=center] at (5.3,-1.0) {copy $4$\\elements};
\end{tikzpicture}
$$

> **Lemma (amortized append).** Starting from an empty dynamic array, any sequence
> of $n$ $\textsc{Append}$ operations runs in $O(n)$ total time, i.e. $O(1)$ **amortized**
> per append.

> **Proof (aggregate method).** Ignore the cheap per-append writes (clearly $O(n)$
> total) and count only the copying done by resizes. Doubling from empty, resizes
> happen when the size passes $1, 2, 4, 8, \dots$, and the resize at size $2^k$
> copies $2^k$ elements. Across $n$ appends the largest resize is at most $2^{\lceil
> \log_2 n\rceil}\le 2n$, so the total copying cost is
>
> $$
> 1 + 2 + 4 + \dots + 2^{\lfloor \log_2 n\rfloor}
> \;=\; 2^{\lfloor \log_2 n\rfloor + 1} - 1 \;<\; 2n.
> $$
>
> Total work is therefore $O(n)$ for the $n$ appends, or $O(1)$ amortized each.
> $\qed$

The geometric growth is what makes this work: each resize is twice as expensive
as the last but happens half as often, so the costs telescope into a constant per
operation. Growing by a _fixed_ increment instead of doubling would make the same
$n$ appends cost $\Theta(n^2)$. Amortized $O(1)$ has two costs: an
occasional latency spike on the doubling step, and up to $2\times$ wasted capacity
right after a resize.[^clrs-amort]

$$
% caption: Doubling growth over $16$ appends: the capacity staircase (accent) jumps
%          $1\!\to\!2\!\to\!4\!\to\!8\!\to\!16$, while the size (filled) rises by one each
%          append. Each jump is a $\Theta(n)$ copy, and the gap above the fill is the
%          reserved-but-unused capacity.
\begin{tikzpicture}[>=stealth, x=0.46cm, y=0.2cm]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->] (0,0) -- (17.5,0) node[right, font=\small] {appends $n$};
  \draw[->] (0,0) -- (0,18) node[above, font=\small] {slots};
  \foreach \y in {1,2,4,8,16} {
    \draw[black] (0,\y) -- (16,\y);
    \node[font=\scriptsize, left=1mm] at (0,\y) {\y};
  }
  % size bars: height = n after n-th append
  \foreach \n in {1,...,16} {
    \fill[acc!22] ({\n-0.82},0) rectangle ({\n-0.18},\n);
  }
  % capacity staircase
  \draw[acc, very thick]
    (0,1) -- (1,1) -- (1,2) -- (2,2) -- (2,4) -- (4,4)
    -- (4,8) -- (8,8) -- (8,16) -- (16,16);
  \node[acc, font=\scriptsize, above left] at (8,16) {capacit\/y};
\end{tikzpicture}
$$

### The trace, append by append

The lemma's algebra is worth checking on a concrete trace.
Start from an empty array with capacity $1$ and run $16$ appends, counting one
unit per element written or copied:

| append | capacity before | resize? | copies | cost |
| --- | --- | --- | --- | --- |
| $1$ | $1$ | no | $0$ | $1$ |
| $2$ | $1$ | grow to $2$ | $1$ | $2$ |
| $3$ | $2$ | grow to $4$ | $2$ | $3$ |
| $4$ | $4$ | no | $0$ | $1$ |
| $5$ | $4$ | grow to $8$ | $4$ | $5$ |
| $6$–$8$ | $8$ | no | $0$ | $1$ each |
| $9$ | $8$ | grow to $16$ | $8$ | $9$ |
| $10$–$16$ | $16$ | no | $0$ | $1$ each |

The total is $16$ writes plus $1 + 2 + 4 + 8 = 15$ copies: $31$ units for $16$
appends, under $2$ per operation, matching the aggregate bound. The
spikes at appends $2, 3, 5, 9$ (and next at $17, 33, \dots$) double in height
each time but arrive half as often, which is the telescoping made visible.

$$
% caption: Per-append cost for the same $16$ appends. Cheap appends (muted) cost one
%          write; the resizing appends at $2,3,5,9$ (accent) pay a copy of $1,2,4,8$ on
%          top. Spikes double in height but halve in frequency, so the running total never
%          crosses the $3$-credit budget line (dashed).
\begin{tikzpicture}[>=stealth, x=0.52cm, y=0.34cm]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->] (0,0) -- (17.5,0) node[right, font=\small] {append};
  \draw[->] (0,0) -- (0,10.5) node[above, font=\small] {cost};
  \foreach \y in {1,3,5,9} {
    \draw[black] (0,\y) -- (16.5,\y);
    \node[font=\scriptsize, left=1mm] at (0,\y) {\y};
  }
  % cheap appends
  \foreach \n in {1,4,6,7,8,10,11,12,13,14,15,16} {
    \fill[acc!22] ({\n-0.8},0) rectangle ({\n-0.2},1);
  }
  % resizing appends: cost 2, 3, 5, 9
  \foreach \n/\c in {2/2,3/3,5/5,9/9} {
    \fill[acc!80] ({\n-0.8},0) rectangle ({\n-0.2},\c);
  }
  \draw[black, dashed] (0,3) -- (16.5,3);
  \node[black, font=\scriptsize, above] at (13.5,3) {budget: 3 per append};
  \foreach \n in {1,5,9,16} { \node[font=\scriptsize, below] at ({\n-0.5},0) {\n}; }
\end{tikzpicture}
$$

The aggregate proof above sums costs after the fact. The **accounting method**
explains the same bound as a budget you could enforce up front: charge every
append $3$ credits. One credit pays for writing the new element. The other two
are banked on the element itself. When a resize hits at capacity $2k$, the $k$
elements appended since the previous resize each hold $2$ banked credits, enough
to pay for copying themselves _and_ one element from the older half of the
array, which spent its own credits at an earlier resize. Every copy is prepaid,
so no operation ever draws on future income, and $3n$ credits cover any $n$
appends.[^clrs-amort]

> **Invariant.** Between resizes, every element in the newer half of the block
> carries two unspent credits. At the moment the block fills, the banked credits
> total exactly the size of the block, the cost of the impending copy.

Doubling is essential, not incidental. Suppose the array instead grew by a fixed
increment $c$ each time it filled. Resizes would then occur at sizes $c, 2c,
3c, \dots$, and the resize at size $ic$ copies $ic$ elements, so $n$ appends
cost

$$
\sum_{i=1}^{n/c} ic \;=\; c \cdot \frac{(n/c)(n/c + 1)}{2} \;=\; \Theta\!\parens{\frac{n^2}{c}},
$$

which is $\Theta(n)$ _per append_ for any constant $c$. Concretely, $n = 10^6$
appends with $c = 1024$ perform about $4.9 \times 10^8$ copy operations where
doubling performs under $2 \times 10^6$. Any geometric factor works ($1.5\times$
trades a smaller memory overshoot for more frequent copies); arithmetic growth
does not.

The same discipline runs in reverse for a shrinking array. Popping elements
should eventually release memory, but halving the block the instant the array is
half full invites **thrashing**: alternating push/pop at the boundary would
resize on every operation. The standard fix is hysteresis, halving only when the
array falls to a _quarter_ full. After any resize, in either direction, the
array is exactly half full, so at least $\Theta(n)$ cheap operations must pass
before the next resize, and the amortized bound survives deletion too.

## Linked lists

A **linked list** threads elements through pointers. In a **singly linked list**
each node stores a $key$ and a $next$ pointer to its successor; a $head$ pointer
names the first node and the last node's $next$ is $\text{nil}$. A **doubly linked
list** adds a $prev$ pointer, so the list can be traversed in both directions and
a node can be removed knowing only itself.

$$
% caption: A doubly linked list; deleting the middle node is $O(1)$ pointer splicing
\begin{tikzpicture}[
  >=stealth,
  node distance=12mm,
  cell/.style={draw, minimum height=8mm, minimum width=7mm, inner sep=2pt},
  key/.style={draw, minimum height=8mm, minimum width=8mm, inner sep=2pt, font=\small}]
  % node A: [prev | key | next]
  \node[cell] (ap) {};
  \node[key, right=0mm of ap] (ak) {$9$};
  \node[cell, right=0mm of ak] (an) {};
  % node B
  \node[cell, right=12mm of an] (bp) {};
  \node[key, right=0mm of bp] (bk) {$16$};
  \node[cell, right=0mm of bk] (bn) {};
  % node C
  \node[cell, right=12mm of bn] (cp) {};
  \node[key, right=0mm of cp] (ck) {$4$};
  \node[cell, right=0mm of ck] (cn) {};
  % head pointer
  \node (head) [above=8mm of ak] {\small head};
  \draw[->] (head) -- (ak.north);
  % forward next pointers: straight horizontal arrows in the gap, riding the upper half
  \draw[->] ([yshift=2.2pt]an.east) -- ([yshift=2.2pt]bp.west);
  \draw[->] ([yshift=2.2pt]bn.east) -- ([yshift=2.2pt]cp.west);
  % backward prev pointers: straight horizontal arrows, riding the lower half
  \draw[->] ([yshift=-2.2pt]bp.west) -- ([yshift=-2.2pt]an.east);
  \draw[->] ([yshift=-2.2pt]cp.west) -- ([yshift=-2.2pt]bn.east);
  % nil grounds
  \node (lnil) [left=10mm of ap] {\small nil};
  \node (rnil) [right=10mm of cn] {\small nil};
  \fill (ap.center) circle (1.1pt);
  \fill (cn.center) circle (1.1pt);
  \draw[->] (ap.center) -- (lnil.east);
  \draw[->] (cn.center) -- (rnil.west);
\end{tikzpicture}
$$

The complexities follow directly from the pointer structure:

- **Insert / delete given the node.** $O(1)$. To delete node $x$ from a doubly
  linked list, set $next(prev(x)) \gets next(x)$ and $prev(next(x)) \gets
  prev(x)$, a constant number of pointer writes, no shifting. This is the linked
  list's signature advantage over an array.
- **Search by key, or index by position.** $O(n)$. There is no address
  arithmetic; you must walk the chain.

The boundary cases (deleting the head, deleting the tail, operating on an empty
list) force `nil` checks that clutter the code. A standard trick removes them: a
**sentinel** is a dummy node that is always present and never holds real data. Wrap
the list into a ring around one sentinel $nil$, with $next(nil)$ the first real
node and $prev(nil)$ the last; now _every_ node has a real predecessor and
successor, and delete needs no special cases.[^clrs-list]

```algorithm
caption: $\textsc{List-Delete}(x)$ — remove $x$ from a doubly linked list (sentinel form)
$next(prev(x)) \gets next(x)$
$prev(next(x)) \gets prev(x)$
```

With a sentinel there are no `nil` guards: even at the ends, $prev(x)$ and
$next(x)$ point at real nodes (possibly the sentinel itself), so the two
assignments always make sense.

### The splice, pointer by pointer

Watch the delete on a concrete list. Take $9 \leftrightarrow 16 \leftrightarrow
4$ and delete the node holding $16$; call it $x$. The first assignment,
$next(prev(x)) \gets next(x)$, rewrites the $next$ field of the $9$-node to
point at the $4$-node. The second, $prev(next(x)) \gets prev(x)$, rewrites the
$prev$ field of the $4$-node to point back at the $9$-node. Two writes and the
list reads $9 \leftrightarrow 4$ in both directions. Nothing was shifted,
nothing else was touched, and the cost is the same whether the list holds three
nodes or three million: that locality is the whole case for linked storage.

$$
% caption: Deleting the $16$-node from $9 \leftrightarrow 16 \leftrightarrow 4$. Before:
%          the chain runs through $x$. After: two pointer writes (accent) bypass it. The
%          unlinked node still points into the list (muted dashes), which is harmless;
%          it is simply unreachable and can be freed.
\begin{tikzpicture}[
  >=stealth,
  key/.style={draw, minimum height=7mm, minimum width=9mm, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % before
  \node[font=\scriptsize, anchor=east] at (-0.8,0) {before};
  \node[key] (a) at (0,0) {$9$};
  \node[key] (b) at (2.0,0) {$16$};
  \node[key] (c) at (4.0,0) {$4$};
  \draw[->] ([yshift=2pt]a.east) -- ([yshift=2pt]b.west);
  \draw[->] ([yshift=-2pt]b.west) -- ([yshift=-2pt]a.east);
  \draw[->] ([yshift=2pt]b.east) -- ([yshift=2pt]c.west);
  \draw[->] ([yshift=-2pt]c.west) -- ([yshift=-2pt]b.east);
  % after
  \begin{scope}[yshift=-2.6cm]
    \node[font=\scriptsize, anchor=east] at (-0.8,0) {after};
    \node[key] (a2) at (0,0) {$9$};
    \node[key, black] (b2) at (2.0,1.1) {$16$};
    \node[key] (c2) at (4.0,0) {$4$};
    \draw[->, acc, thick] ([yshift=2pt]a2.east) to[bend left=14] ([yshift=2pt]c2.west);
    \draw[->, acc, thick] ([yshift=-2pt]c2.west) to[bend left=14] ([yshift=-2pt]a2.east);
    \draw[->, black, dashed] (b2.west) to[bend right=20] (a2.north);
    \draw[->, black, dashed] (b2.east) to[bend left=20] (c2.north);
  \end{scope}
\end{tikzpicture}
$$

Insertion is the same idea with four writes instead of two. To splice a new
node $y$ in immediately after a node $x$:

```algorithm
caption: $\textsc{List-Insert-After}(x, y)$ — splice node $y$ in right after $x$
$next(y) \gets next(x)$ // $y$ learns its successor first
$prev(y) \gets x$
$prev(next(x)) \gets y$ // old successor points back at $y$
$next(x) \gets y$ // finally $x$ lets go of the old link
```

The _order_ of the writes is the classic pitfall. The first line reads
$next(x)$, so the last line, which overwrites $next(x)$, must come after it: swap
them and $y$'s successor becomes $y$ itself, quietly turning the tail of the
list into a self-loop. Run the trace on $9 \leftrightarrow 16 \leftrightarrow 4$,
inserting $y = 11$ after the $16$-node: line 1 points $next(y)$ at the $4$-node,
line 2 points $prev(y)$ at the $16$-node, line 3 rewrites the $4$-node's $prev$
to $y$, and line 4 rewrites the $16$-node's $next$ to $y$. The list now reads
$9 \leftrightarrow 16 \leftrightarrow 11 \leftrightarrow 4$, again in $O(1)$
regardless of length. Deleting the head or splicing at the tail is _still_ the
same code under a sentinel, which is why the sentinel is worth its one
node of overhead.

| operation | array | linked list |
| --- | --- | --- |
| index / random access | $O(1)$ | $O(n)$ |
| search (unsorted) | $O(n)$ | $O(n)$ |
| insert/delete at known position | $O(n)$ shift | $O(1)$ splice |
| insert/delete at end | $O(1)$ amortized | $O(1)$ |
| cache locality | excellent | poor |
| extra space per element | none | 1–2 pointers |

Neither structure dominates: choose contiguous when you index and scan, linked
when you splice in the middle and never need the $i$-th element by number.

::impl{algo="singly_linked_list,doubly_linked_list"}

## Stacks: last in, first out

A **stack** restricts access to one discipline: **LIFO**, last in, first out.
Only the most recently inserted element is reachable. The operations are
$\textsc{Push}$ (add to the top), $\textsc{Pop}$ (remove the top), and
$\textsc{Peek}$ (read the top without removing) — all $O(1)$.

A stack is trivial to back with a dynamic array: keep a $top$ index, push by
writing $A[top]$ and incrementing, pop by decrementing. (Amortized $O(1)$ if it
must grow.) Equally, a singly linked list with push/pop at the head is a stack
with worst-case $O(1)$ operations and no resize spikes.

Stacks appear wherever computation is _nested_: the **call stack** that holds
function activation records, **depth-first search**, evaluating arithmetic
expressions, and matching brackets. For brackets, push each opener, then pop and
check on each closer, accepting iff the stack ends empty. That last pattern is the
_Valid Parentheses_ problem.

::impl{algo="stack"}

## Queues and deques: first in, first out

A **queue** enforces the opposite discipline: **FIFO**, first in, first out, like
a line at a counter. $\textsc{Enqueue}$ adds at the **tail**; $\textsc{Dequeue}$
removes from the **head**. Both are $O(1)$.

$$
% caption: A stack is LIFO (one end, the top); a queue is FIFO (insert at tail, remove at
%          head)
\begin{tikzpicture}[
  >=stealth,
  box/.style={draw, minimum width=10mm, minimum height=7mm, inner sep=2pt}]
  \definecolor{acc}{HTML}{2348F2}
  % --- STACK: vertical, top marked ---
  \begin{scope}
    \node[box] (s2) at (0,0) {$c$};
    \node[box] (s1) at (0,-0.72) {$b$};
    \node[box] (s0) at (0,-1.44) {$a$};
    \node[font=\small] at (0,-2.3) {stac\/k (LIF\/O)};
    \node[font=\small, acc, right=3mm of s2] (top) {top};
    \draw[->, acc] (top.west) -- (s2.east);
    \draw[->, thick] (-1.4,0.55) -- node[above, font=\footnotesize] {push} (-0.55,0.1);
    \draw[->, thick] (-0.55,-0.1) -- node[below, font=\footnotesize] {pop} (-1.4,-0.55);
  \end{scope}
  % --- QUEUE: horizontal, head/tail marked ---
  \begin{scope}[xshift=4.2cm, yshift=-0.8cm]
    \node[box] (q0) at (0,0) {$a$};
    \node[box, right=0mm of q0] (q1) {$b$};
    \node[box, right=0mm of q1] (q2) {$c$};
    \node[font=\small] at (1.0,-1.0) {queue (FIF\/O)};
    \node[font=\small, acc, above=4mm of q0] (head) {head};
    \node[font=\small, acc, above=4mm of q2] (tail) {tail};
    \draw[->, acc] (head.south) -- (q0.north);
    \draw[->, acc] (tail.south) -- (q2.north);
    \draw[->, thick] (q0.west) -- node[below, font=\footnotesize, pos=1] {dequeue} (-1.7,0);
    \draw[->, thick] (3.7,0) -- node[below, font=\footnotesize, pos=0] {enqueue} (q2.east);
  \end{scope}
\end{tikzpicture}
$$

Backing a queue with an array needs care: if we always dequeued from index $0$ we
would shift the whole array each time, $O(n)$. The fix is a **circular buffer**.
Keep a fixed array of capacity $m$ and two indices, $head$ and $tail$; enqueue
writes $A[tail]$ and advances $tail \gets (tail + 1) \bmod m$, dequeue reads
$A[head]$ and advances $head \gets (head + 1) \bmod m$. The indices chase each
other around the ring, reusing freed slots, so both operations stay $O(1)$ with no
shifting and no wasted scanning.[^clrs-queue] (When the buffer fills, resize and re-lay-out
into a larger ring at amortized $O(1)$, exactly as for the dynamic array.)

$$
% caption: A circular buffer of capacity $8$ holding four elements: $head$ and $tail$
%          chase each other around the ring, and advancing past slot $7$ wraps to slot
%          $0$.
\begin{tikzpicture}[slot/.style={draw, circle, minimum size=8mm, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[slot] (s0) at (0,2.2) {0};
  \node[slot] (s1) at (1.56,1.56) {1};
  \node[slot, fill=acc!18] (s2) at (2.2,0) {2};
  \node[slot, fill=acc!18] (s3) at (1.56,-1.56) {3};
  \node[slot, fill=acc!18] (s4) at (0,-2.2) {4};
  \node[slot, fill=acc!18] (s5) at (-1.56,-1.56) {5};
  \node[slot] (s6) at (-2.2,0) {6};
  \node[slot] (s7) at (-1.56,1.56) {7};
  \node[font=\scriptsize] (hl) at (3.5,0) {$head$}; \draw[->] (hl) -- (s2);
  \node[font=\scriptsize] (tl) at (-3.5,0) {$tail$}; \draw[->] (tl) -- (s6);
  \node[font=\footnotesize, align=center] at (0,0) {enqueue at $tail$\\dequeue at $head$\\index (i+1) \texttt{mod}~8};
\end{tikzpicture}
$$

### Wraparound, index by index

The modular arithmetic deserves one full trace. Take capacity $m = 8$ and start
empty with $head = tail = 0$. Enqueue $a$ through $f$: each write lands at
$A[tail]$ and advances $tail$, leaving $a \dots f$ in slots $0$–$5$ with $head =
0$, $tail = 6$. Dequeue four times: the reads return $a, b, c, d$ in insertion
order while $head$ advances to $4$; slots $0$–$3$ still _contain_ the old
values, but they are logically free and are never erased. Now
enqueue $g$, $h$, $i$:

| operation | write | $tail$ update | state after |
| --- | --- | --- | --- |
| enqueue $g$ | $A[6] \gets g$ | $(6+1) \bmod 8 = 7$ | $head = 4$, $tail = 7$ |
| enqueue $h$ | $A[7] \gets h$ | $(7+1) \bmod 8 = 0$ | $head = 4$, $tail = 0$ |
| enqueue $i$ | $A[0] \gets i$ | $(0+1) \bmod 8 = 1$ | $head = 4$, $tail = 1$ |

The enqueue of $h$ is the wrap: $tail$ steps off the right end of the array and
the $\bmod$ folds it back to slot $0$, where the next write overwrites the
stale $a$. The queue now holds $e, f, g, h, i$, physically split across slots
$4$–$7$ and $0$ but logically contiguous around the ring. Dequeues would keep
reading $e, f, g, \dots$ in FIFO order, with $head$ making the same wrap three
steps later.

$$
% caption: The same ring, unrolled: three snapshots of the capacity-$8$ array. Top: six
%          enqueues f\/ill slots $0$-$5$. Middle: four dequeues advance $head$ past the
%          stale values (muted). Bottom: enqueuing $g,h,i$ runs $tail$ off the right end
%          and the modulus wraps it back to slot $0$ (accent arc), overwriting stale $a$.
\begin{tikzpicture}[
  >=stealth,
  slot/.style={draw, minimum width=7.5mm, minimum height=7mm, font=\small, inner sep=0}]
  \definecolor{acc}{HTML}{2348F2}
  % row 1: after enqueue a..f
  \begin{scope}
    \node[font=\scriptsize, anchor=east] at (-0.75,0) {enqueue a to f};
    \foreach \j/\v in {0/a,1/b,2/c,3/d,4/e,5/f} {
      \fill[acc!15] ({\j*0.75-0.375},-0.35) rectangle ({\j*0.75+0.375},0.35);
    }
    \foreach \j/\v in {0/a,1/b,2/c,3/d,4/e,5/f,6/,7/} {
      \node[slot] at ({\j*0.75},0) {\v};
    }
    \node[font=\scriptsize, acc, below] at (0,-0.4) {head 0};
    \node[font=\scriptsize, acc, above] at ({6*0.75},0.4) {tail 6};
  \end{scope}
  % row 2: after 4 dequeues
  \begin{scope}[yshift=-1.9cm]
    \node[font=\scriptsize, anchor=east] at (-0.75,0) {dequeue 4 times};
    \foreach \j in {4,5} {
      \fill[acc!15] ({\j*0.75-0.375},-0.35) rectangle ({\j*0.75+0.375},0.35);
    }
    \foreach \j/\v in {0/a,1/b,2/c,3/d} {
      \node[slot, text=black] at ({\j*0.75},0) {\v};
    }
    \foreach \j/\v in {4/e,5/f,6/,7/} {
      \node[slot] at ({\j*0.75},0) {\v};
    }
    \node[font=\scriptsize, acc, below] at ({4*0.75},-0.4) {head 4};
    \node[font=\scriptsize, acc, above] at ({6*0.75},0.4) {tail 6};
  \end{scope}
  % row 3: after enqueue g,h,i with wrap
  \begin{scope}[yshift=-4.3cm]
    \node[font=\scriptsize, anchor=east] at (-0.75,0) {enqueue g, h, i};
    \foreach \j in {0,4,5,6,7} {
      \fill[acc!15] ({\j*0.75-0.375},-0.35) rectangle ({\j*0.75+0.375},0.35);
    }
    \foreach \j/\v in {1/b,2/c,3/d} {
      \node[slot, text=black] at ({\j*0.75},0) {\v};
    }
    \foreach \j/\v in {0/i,4/e,5/f,6/g,7/h} {
      \node[slot] at ({\j*0.75},0) {\v};
    }
    \node[font=\scriptsize, acc, below] at ({4*0.75},-0.4) {head 4};
    \node[font=\scriptsize, acc, below] at ({1*0.75},-0.4) {tail 1};
    \draw[->, acc] ({7*0.75},0.45) to[bend right=30] node[above, font=\scriptsize, pos=0.5] {wrap} ({0*0.75},0.45);
  \end{scope}
\end{tikzpicture}
$$

One boundary case needs a decision. With only the two indices, $head = tail$
describes _both_ the empty queue and the full one, since a full ring's $tail$
has lapped all the way around to $head$. Either keep an explicit element count
alongside the indices, or declare the buffer full at $m - 1$ elements so the
two states stay distinguishable; both choices are $O(1)$ and both appear in
production code. Forgetting the ambiguity entirely is the classic circular-buffer
bug: the full buffer reports empty and silently drops a lap of data.

A **deque** (double-ended queue, pronounced "deck") generalizes both: it supports
$O(1)$ insert and delete at _both_ ends. A deque used at one end only is a stack;
used to push at one end and pop at the other, it is a queue, so the deque
subsumes everything in this lesson. A doubly linked list with a head and tail
sentinel implements a deque directly, and a circular buffer with both indices
movable in either direction does too; the _Design Circular Deque_ problem asks for
the latter.

::impl{algo="circular_queue,deque,doubling_array"}

## Elementary structures in practice

The textbook trade-off, contiguous versus linked, is only the starting point;
real systems adjust it in several ways.

**Growth factors.** The amortized argument
works for any geometric factor, and standard libraries pick different ones for
different reasons. Microsoft's and most C++ `std::vector` implementations double;
GCC's `libstdc++` also doubles, but Facebook's `folly::fbvector` grows by
$1.5\times$ precisely because doubling can never reuse the freed blocks. With a
factor below the golden ratio $\varphi \approx 1.618$, the sum of all previous
block sizes eventually exceeds the next block, so an allocator can place the new
array in the coalesced space the old ones left behind; doubling can never do
this. The choice is a genuine trade of memory footprint against copy frequency,
and both live in production.

**Bulk nodes for cache locality.** A plain linked list's one-node-per-
element layout has poor cache behavior, so practical "linked" structures store
_many_ elements per node. An **unrolled linked list** keeps a small array (say
$16$ to $64$ elements) in each node, recovering most of an array's locality while
keeping $O(1)$ splicing at node boundaries; this is the shape of many production
"rope" and "gap buffer" text structures. A **B-tree** or its cache-oblivious
cousins push the same idea to a full tree, which is why they
[dominate on disk](/algorithms/data-structures/b-trees).

**Standard-library deques.** Python's `collections.deque` and Java's
`ArrayDeque` are not linked lists but _blocked_ circular buffers, arrays of
fixed-size blocks, giving $O(1)$ push/pop at both ends _and_ cache-friendly
iteration. And in immutable/functional languages, the everyday "list" is a
**persistent** singly linked list whose shared tails make $O(1)$ prepend and
structural sharing cheap, a different sweet spot from the mutable dynamic array
that dominates imperative code.[^btb-elementary]

## Takeaways

- Every container is either **contiguous** (an array — $O(1)$ random access by
  address arithmetic, cache-friendly, $O(n)$ to splice) or **linked** (nodes
  joined by pointers — $O(1)$ splice given the node, $O(n)$ to index, a pointer of
  overhead per element). The choice is a trade, not a winner.
- A **dynamic array** appends in **amortized $O(1)$** by **doubling** capacity on
  overflow: the aggregate copy cost over $n$ appends is $1+2+\dots+2^k < 2n$, or
  by the accounting method, $3$ prepaid credits per append cover every copy.
  Fixed-increment growth costs $\Theta(n^2/c)$ instead; shrinking halves only at
  one-quarter full to avoid thrashing. The worst-case single append is still
  $O(n)$ on the resize step.
- A **doubly linked list** inserts and deletes in $O(1)$ given the node: delete
  is two pointer writes, insert-after is four, with write _order_ mattering (read
  $next(x)$ before overwriting it). A **sentinel** node erases the boundary cases.
- A **stack** is **LIFO** ($\textsc{Push}/\textsc{Pop}/\textsc{Peek}$, all $O(1)$)
  and underlies the call stack, DFS, expression evaluation, and bracket matching.
- A **queue** is **FIFO**, implemented as a **circular buffer** with $head$ and
  $tail$ indices advanced $\bmod\,m$ for $O(1)$ ends. Since $head = tail$ means
  both empty and full, keep a count (or cap at $m-1$ elements) to tell them
  apart. The **deque** generalizes both stack and queue to $O(1)$ operations at
  either end.

[^skiena-contig]: **Skiena**, §3.1–3.2, Contiguous vs. Linked Structures: the array-vs-pointer trade-off and its consequences for access, splicing, and locality.
[^clrs-amort]: **CLRS**, Ch. 10, Elementary Data Structures (with the amortized analysis of Ch. 16): geometric doubling gives $O(1)$ amortized table append.
[^clrs-list]: **CLRS**, Ch. 10, Elementary Data Structures (§10.2): doubly linked lists and the sentinel that removes boundary cases from insert/delete.
[^clrs-queue]: **CLRS**, Ch. 10, Elementary Data Structures (§10.1): stacks and the circular-array queue with head/tail indices taken $\bmod\,m$.
[^btb-elementary]: On sub-$\varphi$ growth factors reusing freed memory, see the folly `fbvector` design notes; on unrolled lists, Shao & Reps, "Unrolling lists" (1994); persistent lists are standard in Okasaki, _Purely Functional Data Structures_ (1998).