Elementary Data Structures

Before we can balance trees or hash keys, we need the raw material they are made of. Every data structure in this course (every tree, heap, hash table, and graph) is ultimately stored one of two ways, and the choice echoes through everything built on top of it. You can lay the elements out contiguously, packed shoulder-to-shoulder in one block of memory, or you can scatter them and stitch them together with 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 assumes you already own.

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.¹

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, 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).

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 exactly 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.

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.

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)$. The price of amortized $O(1)$ is twofold: an occasional latency spike on the doubling step, and up to $2\times$ wasted capacity right after a resize.²

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.

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))\leftarrow next(x)$ and $prev(next(x))\leftarrow 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.³

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.

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.

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 $\text{Push}$ (add to the top), $\text{Pop}$ (remove the top), and $\text{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, and it is a stack in one line of intuition.

Queues and deques: first in, first out

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

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\leftarrow (tail+1)\mathrm{mod}m$, dequeue reads $A[head]$ and advances $head\leftarrow (head+1)\mathrm{mod}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.⁴ (When the buffer fills, resize and re-lay-out into a larger ring at amortized $O(1)$, exactly as for the dynamic array.)

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 exactly the latter.

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+\cdots +2^k<2n$. 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; a sentinel node erases the boundary cases so delete is two pointer writes.
• A stack is LIFO ($\text{Push}/\text{Pop}/\text{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 $\mathrm{mod}m$ for $O(1)$ ends; the deque generalizes both stack and queue to $O(1)$ operations at either end.