Arrays, Linked Lists, Stacks, and Queues

The algorithms of the preceding chapters operate on arrays: contiguous blocks of memory indexed by integers. Arrays are powerful but they are only one of many ways to organize data. In this chapter we study the fundamental data structures that underpin nearly all of Computer Science: dynamic arrays, linked lists, stacks, queues, and deques. Each offers a different set of trade-offs between time complexity, memory usage, and flexibility. Understanding these structures deeply is essential, because every higher-level data structure, from hash tables to balanced trees to graphs, is built on top of them.

Arrays

An array is the simplest data structure: a contiguous block of memory divided into equal-sized slots, each identified by an integer index. Accessing any element by its index takes $O(1)$ time, because the memory address can be computed directly: if the array starts at address $b$ and each element occupies $s$ bytes, then element $i$ lives at address $b+i\cdot s$.

This direct addressing makes arrays extremely efficient for random access. However, arrays have a fundamental limitation: their size is fixed at creation time. If we need to store more elements than the array can hold, we must allocate a new, larger array and copy all existing elements, which is an $O(n)$ operation.

Static arrays in TypeScript

TypeScript (and JavaScript) arrays are actually dynamic; they resize automatically behind the scenes. But to understand the foundations, imagine a fixed-size array:

const fixed = new Array<number>(10); // 10 slots, all undefined
fixed[0] = 42;
fixed[9] = 99;
// fixed[10] would be out of bounds in a true static array

In languages like C or Java, going beyond the allocated size is either a compile-time error or a runtime crash. JavaScript's built-in arrays hide this complexity, but the cost of resizing is still there; it is just managed for us in the background. Let us see how by prodiving an implementation of dynamic arrays.

A note on faithfulness. The closest analogue to a true fixed-size, contiguous-memory array in TypeScript is a TypedArray such as Int32Array or Float64Array, which is backed by a raw ArrayBuffer of bytes. TypedArrays have a fixed length set at construction, cannot grow, and store elements of a single numeric type in a predictable, cache-friendly layout. The downside is that they only support numeric primitives, so they cannot hold a generic T. Because we want a reusable DynamicArray<T>, the implementation below uses a regular JavaScript array as the backing buffer and treats its slots as fixed by tracking capacity manually. Conceptually, every this.data[i] access should be read as "load the $i$-th word from a contiguous memory block of size capacity." If you want to see the same idea with a genuinely fixed-size store, swap the backing buffer for a Float64Array and drop the T | undefined typing; the resize logic stays identical.

Dynamic arrays

A dynamic array maintains an internal buffer that is larger than the number of elements currently stored. When the buffer fills up, the array allocates a new buffer of double the size and copies all elements over. This doubling strategy gives us amortized $O(1)$ appends while keeping worst-case access at $O(1)$. We will justify both bounds in the complexity and space analysis section below, once we have seen how the implementation grows the buffer.

The doubling strategy

Suppose our dynamic array has capacity $c$ and currently holds $n$ elements. When we append element $n+1$:

• If $n<c$: store the element in slot $n$. Cost: $O(1)$.
• If $n=c$: allocate a new buffer of size $2c$, copy all $n$ elements, then store the new element. Cost: $O(n)$.

The key insight is that expensive copies happen rarely. After a copy doubles the capacity to $2c$, we can perform another $c$ cheap appends before the next copy. This is essential for amortized analysis, which we will make precise after the implementation.

Implementation

Our DynamicArray<T> uses a plain JavaScript array as the backing buffer, with explicit capacity management. The initial capacity defaults to 4.

export class DynamicArray<T> implements Iterable<T> {
  private data: (T | undefined)[];
  private length: number;

  constructor(initialCapacity = 4) {
    this.data = new Array<T | undefined>(initialCapacity);
    this.length = 0;
  }

  get size(): number {
    return this.length;
  }

  get capacity(): number {
    return this.data.length;
  }

  get(index: number): T {
    this.checkBounds(index);
    return this.data[index] as T;
  }

  set(index: number, value: T): void {
    this.checkBounds(index);
    this.data[index] = value;
  }

  append(value: T): void {
    this.growIfFull();
    this.data[this.length] = value;
    this.length++;
  }

  insert(index: number, value: T): void {
    this.checkInsertBounds(index);
    this.growIfFull();
    for (let i = this.length; i > index; i--) {
      this.data[i] = this.data[i - 1];
    }
    this.data[index] = value;
    this.length++;
  }

  remove(index: number): T {
    this.checkBounds(index);
    const value = this.data[index] as T;
    for (let i = index; i < this.length - 1; i++) {
      this.data[i] = this.data[i + 1];
    }
    this.data[this.length - 1] = undefined;
    this.length--;
    this.shrinkIfSparse();
    return value;
  }

  private growIfFull(): void {
    if (this.length === this.data.length) {
      this.resize(this.data.length * 2);
    }
  }

  private shrinkIfSparse(): void {
    if (
      this.length > 0 &&
      this.length <= this.data.length / 4 &&
      this.data.length > 4
    ) {
      this.resize(Math.max(4, Math.floor(this.data.length / 2)));
    }
  }

  private resize(newCapacity: number): void {
    const newData = new Array<T | undefined>(newCapacity);
    for (let i = 0; i < this.length; i++) {
      newData[i] = this.data[i];
    }
    this.data = newData;
  }

  private checkBounds(index: number): void {
    if (index < 0 || index >= this.length) {
      throw new RangeError(
        `Index ${index} out of bounds for size ${this.length}`
      );
    }
  }

  private checkInsertBounds(index: number): void {
    if (index < 0 || index > this.length) {
      throw new RangeError(
        `Index ${index} out of bounds for size ${this.length}`
      );
    }
  }
  // ... iterator, toArray, etc.
}

Notice that remove also implements shrinking: when occupancy falls below 25%, the buffer is halved (but never below 4). This prevents a long sequence of removals from wasting memory, and the halving threshold (1/4 rather than 1/2) avoids thrashing, a pathological pattern where alternating appends and removes near the boundary trigger repeated resizes.

Complexity and space analysis

Now that we have seen the implementation, we can return to the claim made at the start of this section: a dynamic array supports append in amortized $O(1)$ time while keeping get and set at $O(1)$ in the worst case.

Indexed read and write stay $O(1)$

The backing store is a single contiguous JavaScript array, so the slot for element $i$ lives at a fixed offset within it. Computing that offset is constant work, independent of $n$. Once we have the offset, both reading the slot (get(i)) and writing to it (set(i, v)) take constant time.

Note that neither get nor set ever triggers a resize. They do not change the number of elements stored, so the buffer never needs to grow or shrink as a result of them; only append, insert, and remove change the size and therefore interact with the resize logic. get and set simply address an existing slot.

Resizing does not break this invariant: the new buffer is also contiguous, so after the copy the slot for element $i$ is again at a fixed offset. Therefore get(i) and set(i, v) are both $O(1)$ in the worst case, not just on average.

Amortized analysis of append

A single append can cost $O(n)$ when it triggers a resize, but resizes are rare enough that the average cost per append, taken over a long sequence of operations, is $O(1)$. This kind of averaging is what amortized analysis captures.

We use the aggregate method. Starting from an empty array with initial capacity 1, suppose we perform $n$ appends. Resizes happen when the size reaches 1, 2, 4, 8, ..., up to the largest power of 2 not exceeding $n$. The total number of element copies across all resizes is therefore

$$1+2+4+8+\cdots +2^{\lfloor {\log }_{2}n\rfloor }\le 2n.$$

To see why this bound holds, recall the multiply-by-$r$-and-subtract derivation we used in Chapter 6 (in the box explaining $n+n/2+n/4+\cdots =2n$). Applied to a finite sum $S_k=1+r+r^2+\cdots +r^k$ with $r\ne 1$, the same algebra gives $S_k-r{S}_k=1-r^{k+1}$, hence

$$S_k=\frac{r^{k+1}-1}{r-1}.$$

Specializing to $r=2$ and $k=\lfloor {\log }_{2}n\rfloor$, the sum of copies is exactly $2^{k+1}-1=2\cdot 2^k-1$. By definition of the floor, $2^k\le n$, so

$$1+2+4+\cdots +2^k=2\cdot 2^k-1\le 2n-1<2n.$$

The intuition that "the last term dominates the sum" is precisely the statement that, reading the series backward and factoring out $2^k$, the remaining factor $1+\frac{1}{2}+\frac{1}{4}+\cdots +\frac{1}{2^k}=2-2^{-k}$ approaches its limit of $2$ but never reaches it, so the whole sum is always strictly less than $2\cdot 2^k$.

So the total work for $n$ appends is at most $n$ writes plus $2n$ copies, giving $3n$ in total. The amortized cost per append is $3n/n=O(1)$.

Geometric growth is essential to this argument. If we instead grew the buffer by a constant amount $k$ at every resize, every $k$-th append would trigger an $O(n)$ copy, summing to $\Theta (n^2)$ work for $n$ appends and an amortized cost of $\Theta (n)$ per append. Doubling (or any growth factor strictly greater than 1) keeps the geometric sum bounded and the amortized cost constant.

Space overhead

There are two distinct sources of space overhead to account for, both absent from a fixed-size static array.

Steady-state slack. Between resizes, some of the allocated buffer is unused: capacity is at most twice the live size, and the shrink rule keeps occupancy above 25% (except for the small initial buffer). So at any moment outside of a resize, the unused capacity is at most a constant fraction of $n$, and the dynamic array's footprint is bounded by a small constant times the footprint of its static-array counterpart.

Transient resize overhead. Resizing is not free of memory cost either. When the buffer becomes full at size $n$, the implementation allocates a new buffer of capacity $2n$ and copies every live element into it before the old buffer can be freed. During the copy, both buffers coexist, so the peak memory usage of a single resize is $n+2n=3n$ slots, three times the live size, and strictly more than the steady-state bound. After the copy finishes and the old buffer is released, the footprint drops back to $2n$. A static array, in contrast, is allocated once at its final size and never has this transient spike.

For long-lived programs this transient is rarely a problem: it is local to the resize and reclaimed immediately. But it is worth being aware of in two situations. First, when memory is tight (embedded systems, large in-memory datasets close to physical limits), a doubling-resize on a buffer of size $n$ requires $3n$ slots free at the moment of the resize, even though the data structure "uses" only $n$. Second, the resize allocates a fresh contiguous block, which interacts with allocator fragmentation and (in garbage-collected runtimes like JavaScript) creates collectable garbage proportional to the old buffer's size.

Asymptotically, both sources of overhead are still $O(n)$. The dynamic array uses $O(n)$ space, with a small constant-factor overhead compared to a perfectly sized static array, but the constants differ between the steady-state ($\le 2n$) and the brief peak during a resize ($\le 3n$).

Summary

Linked lists

A linked list stores elements in nodes that are scattered throughout memory, with each node containing a value and a pointer (reference) to the next node. Unlike arrays, linked lists do not require contiguous memory, and inserting or removing an element at a known position takes $O(1)$ time, with no shifting required.

The trade-off is that random access is lost: using zero-based indexing as in the rest of the book, reaching the element at index $i$ (that is, the $(i+1)$-th node from the head) requires following $i$ next pointers from the head. The number of hops thus grows in proportion to the index, reaching $n-1$ for the last element, so accessing an arbitrary element is $O(n)$ in the worst case.

Singly linked lists

In a singly linked list, each node points to the next node. The list maintains a pointer to the head (first node) and, for efficiency, a pointer to the tail (last node).

Implementation

class SinglyNode<T> {
  constructor(
    public value: T,
    public next: SinglyNode<T> | null = null,
  ) {}
}

export class SinglyLinkedList<T> implements Iterable<T> {
  private head: SinglyNode<T> | null = null;
  private tail: SinglyNode<T> | null = null;
  private length: number = 0;

  get size(): number {
    return this.length;
  }

  prepend(value: T): void {
    const node = new SinglyNode(value, this.head);
    this.head = node;
    if (this.tail === null) {
      this.tail = node;
    }
    this.length++;
  }

  append(value: T): void {
    const node = new SinglyNode(value);
    if (this.tail !== null) {
      this.tail.next = node;
    } else {
      this.head = node;
    }
    this.tail = node;
    this.length++;
  }

  // Remove the node after `prev`, or the head when `prev` is null. This is
  // the single place where the border cases live: removing the head
  // (prev === null), removing the tail (the tail moves back to `prev`, which
  // is null when the list becomes empty), and removing from an empty list.
  private removeAfter(prev: SinglyNode<T> | null): T | undefined {
    const node = prev === null ? this.head : prev.next;
    if (node === null) return undefined;

    if (prev === null) {
      this.head = node.next;
    } else {
      prev.next = node.next;
    }
    if (node === this.tail) {
      this.tail = prev;
    }
    this.length--;
    return node.value;
  }

  removeFirst(): T | undefined {
    return this.removeAfter(null);
  }

  delete(value: T): boolean {
    let prev: SinglyNode<T> | null = null;
    let current = this.head;
    while (current !== null) {
      if (current.value === value) {
        this.removeAfter(prev);
        return true;
      }
      prev = current;
      current = current.next;
    }
    return false;
  }

  contains(value: T): boolean {
    let current = this.head;
    while (current !== null) {
      if (current.value === value) return true;
      current = current.next;
    }
    return false;
  }
  // ... iterator, toArray, etc.
}

Removal is where singly linked lists are easy to get subtly wrong: the head has no predecessor, the tail pointer must move back when the last node goes, and an empty list must be handled gracefully. We funnel all the cases through a private method removeAfter(prev), which unlinks the node following prev, treating a null predecessor as "remove the head." Every border case lives in that one place: prev === null covers head removal, node === this.tail moves the tail back (to null when the list empties), and node === null handles the empty list. removeFirst is then just removeAfter(null), and delete walks the list carrying the predecessor so it can call the same removeAfterwith the correct node.

Tracing through an example

Starting with an empty singly linked list, let us perform a sequence of operations:

Notice that prepend and removeFirst are both $O(1)$ because they only touch the head pointer. Appending is $O(1)$ because we maintain a tail pointer. However, delete(value) requires a linear scan.

Complexity and space analysis

Having seen the implementation, let us account for the cost of each operation and for the memory a singly linked list consumes. The picture is almost the mirror image of the dynamic array: the operations that arrays do cheaply (indexed access) are expensive here, while the operations that arrays do in $O(n)$ time (insertion and removal at a known boundary) are cheap.

Indexing and search are $O(n)$

A linked list stores no contiguous block whose offset we can compute, so there is no $O(1)$ address arithmetic of the kind that makes array access constant-time. To reach the element at index $i$ we must start at head and follow $i$ next pointers, one node at a time, so the number of hops grows in proportion to the index. The worst case is the last element, at index $n-1$, which costs $n-1$ hops; reaching an arbitrary element is therefore $O(n)$.

The same reasoning applies to contains(value) and to the search phase of delete(value): both walk the list from the head comparing values, so each is $O(n)$ in the worst case, when the value is absent or sits at the tail, and $O(1)$ in the best case, when it is at or near the head. This is the fundamental trade-off of the structure: we gave up the array's constant-time random access, and in return gained constant-time updates at the list's ends. prepend, append, and removeFirst are all $O(1)$ with no element shifting, and once we already hold a pointer to a node, inserting after it is $O(1)$. For the front operations this is a genuine win over an array, which needs $O(n)$ shifting to open up or reclaim the slot at index $0$; append, by contrast, is $O(1)$ for both structures, though only amortized for the dynamic array.

Head- and tail-anchored operations are $O(1)$

The list keeps two pointers, head and tail, and every operation that touches only those endpoints runs in constant time, independent of $n$:

• prepend(value) allocates one node and rewires head (and tail when the list was empty). No traversal. $O(1)$.
• append(value) allocates one node and rewires tail.next and tail. The tail pointer is exactly what lets us skip the traversal that would otherwise be needed to find the end. $O(1)$.
• removeFirst() advances head to head.next and fixes tail when the list empties. $O(1)$.

These bounds are worst-case, not amortized: there is no buffer to resize and no block to copy, so the cost of an individual operation never spikes the way an append for a full dynamic array does. (we treat allocating a single node as constant work having $O(1)$ amortized cost.)

Why removing the tail is still $O(n)$

removeFirst is $O(1)$, but removing from the tail is not. To remove the last node we must set tail to the node before it, and a singly linked node carries no prev pointer. The only way to find the predecessor of the tail is to walk from the head until we reach the node whose next is the tail, a full traversal of $O(n)$ steps. So maintaining a tail pointer buys us a $O(1)$ append, while not really helping with the time complexity of the removal at the tail. This asymmetry is the singly linked list's defining limitation, and it is precisely what the doubly linked list of the next section repairs by giving every node a prev pointer.

Space overhead

A static or dynamic array stores its $n$ values in essentially $n$ contiguous slots. A linked list stores each value in a separately allocated node that also holds a next reference, so the per-element overhead is one pointer-sized field plus whatever per-object bookkeeping the runtime adds (in a JavaScript engine, an object header several words wide). The footprint is thus $O(n)$, the same asymptotic class as the array, but with a larger constant factor: every element pays for a pointer and an object header that the array does not.

In exchange, the linked list avoids the two array-specific overheads analysed earlier. There are no reserved empty slots: the list allocates exactly one node per element and never keeps spare capacity, so it never holds the $\le 2n$ slots a dynamic array does between resizes. And there is no transient resize spike: nodes are added and removed one at a time, so the structure never holds two copies of the data at once and never needs the $3n$ slots free that a doubling resize momentarily requires. Memory is requested and released incrementally, in node-sized units.

There is also a subtler cost that arrays avoid. The nodes are scattered across the heap rather than laid out contiguously, so traversing a linked list has poor cache locality: following each next pointer may jump to an unrelated region of memory and miss the CPU cache, whereas a linear scan of an array streams through consecutive cache lines. Asymptotically both traversals are $O(n)$, but on real hardware the array is typically several times faster for the same $n$. The linked list trades raw scan speed and memory compactness for $O(1)$ endpoint updates and the absence of resizing.

Summary

Doubly linked lists

In a doubly linked list, each node has pointers to both the next and previous nodes. This enables $O(1)$ removal from both ends.

Implementation

class DoublyNode<T> {
  constructor(
    public value: T,
    public prev: DoublyNode<T> | null = null,
    public next: DoublyNode<T> | null = null,
  ) {}
}

export class DoublyLinkedList<T> implements Iterable<T> {
  private head: DoublyNode<T> | null = null;
  private tail: DoublyNode<T> | null = null;
  private length: number = 0;

  get size(): number {
    return this.length;
  }

  prepend(value: T): void {
    const node = new DoublyNode(value, null, this.head);
    if (this.head !== null) {
      this.head.prev = node;
    } else {
      this.tail = node;
    }
    this.head = node;
    this.length++;
  }

  append(value: T): void {
    const node = new DoublyNode(value, this.tail, null);
    if (this.tail !== null) {
      this.tail.next = node;
    } else {
      this.head = node;
    }
    this.tail = node;
    this.length++;
  }

  removeFirst(): T | undefined {
    if (this.head === null) return undefined;
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head !== null) {
      this.head.prev = null;
    } else {
      this.tail = null;
    }
    this.length--;
    return value;
  }

  removeLast(): T | undefined {
    if (this.tail === null) return undefined;
    const value = this.tail.value;
    this.tail = this.tail.prev;
    if (this.tail !== null) {
      this.tail.next = null;
    } else {
      this.head = null;
    }
    this.length--;
    return value;
  }

  private removeNode(node: DoublyNode<T>): void {
    if (node.prev !== null) {
      node.prev.next = node.next;
    } else {
      this.head = node.next;
    }
    if (node.next !== null) {
      node.next.prev = node.prev;
    } else {
      this.tail = node.prev;
    }
    this.length--;
  }
  // ... delete, contains, iterators, etc.
}

The critical advantage is removeLast: by following the tail's prev pointer, we can unlink the last node in $O(1)$ time without traversing the list. The removeNode helper detaches any node from the list in $O(1)$ once we have a reference to it.

The cost of this flexibility is extra memory: each node stores two pointers instead of one. For large collections of small values, this overhead can be significant.

Comparing arrays and linked lists

* Amortized

When to use which:

• Dynamic array when you need fast random access or are iterating sequentially (cache-friendly).
• Singly linked list when insertions and deletions at the front dominate.
• Doubly linked list when you need efficient removal from both ends or deletion of arbitrary nodes (given a reference).

These one-line rules follow directly from the table, but they hide an important practical truth: the table is correct about asymptotics and yet misleading about real-world speed. The next subsections explain why, when a linked list actually earns its place, and how both structures show up inside the data structures you use every day.

Why the complexity table does not predict real speed

Two costs that big-$O$ notation deliberately ignores dominate the actual running time on modern hardware.

The first is cache locality. An array is a single contiguous block, so iterating it streams through consecutive cache lines and the CPU's prefetcher can predict and load the next elements before they are needed. A linked list is a set of nodes scattered across the heap; each next hop is a dependent load (the CPU cannot compute the next node's address until the current node has arrived) and is therefore unpredictable and likely to miss the cache. Both traversals are $O(n)$, but on real hardware the array scan is commonly several times faster for the same $n$, as already noted in the singly linked list's space analysis.

The second is that the array's "$O(n)$" insert and remove are deceptively cheap. Shifting elements is a memmove over a contiguous block: a tight, often vectorized copy that the hardware executes extremely fast. Shifting a few thousand elements can take less time than the pointer-chasing required merely to locate the corresponding position in a linked list. This exposes a hidden precondition in the table: the linked list's $O(1)$ insertion and removal assume you already hold a reference to the node. If you must first search for the position, the operation is $O(n)$ to find plus $O(1)$ to splice, and the search is exactly the cache-unfriendly traversal that arrays avoid.

The practical conclusion is the one most standard libraries have reached: the dynamic array is the right default, and a linked list pays off only when you already hold node references and never need random access or repeated scans.

When a linked list actually earns its place

Linked lists are rarely used as a general-purpose container. They shine in a handful of specific situations, almost all of which share the property that a reference to the relevant node is already in hand, so no traversal is needed:

• Splicing with a node reference in $O(1)$. The canonical example is an LRU (least-recently-used) cache: a hash table maps keys to nodes, and a doubly linked list keeps the nodes in recency order. Each access moves a node to the front in $O(1)$, and eviction drops the tail in $O(1)$, with no traversal because the hash table hands you the node directly. No array supports move-to-front in constant time.
• Intrusive lists with stable identity. In systems code (for example the Linux kernel's list_head), the link pointers live inside objects that were allocated anyway, so there is no separate node allocation, and a node's address never changes even as the list is reordered. An array cannot promise stable addresses because it relocates elements on resize and shifts them on insert.
• $O(1)$ concatenation and sublist splicing. Joining two linked lists, or moving a run of nodes from one list to another, is a few pointer assignments; the array equivalent is a copy.
• Persistent (immutable) lists. Functional languages use singly linked "cons" lists because prepend is $O(1)$ and the tail is shared between the old and new versions, so many versions coexist without copying. Arrays cannot share structure cheaply.
• As the engine of stacks and queues, exactly as the abstract data types later in this chapter are implemented.

The choice between singly and doubly linked then follows the access pattern. A singly linked list uses the least memory (one pointer per node) and suffices when you only ever touch the head or walk forward, which is why it backs stacks, hash-table buckets, and immutable lists. A doubly linked list spends one extra pointer per node to gain $O(1)$ removal of an arbitrary node you hold a reference to, which is what LRU caches, deques, and editor buffers require. The singly linked list's $O(n)$ tail removal, analysed earlier, is precisely why it is unsuitable for those bidirectional uses.

Hybrids: arrays and linked lists inside the same structure

In real systems the two are rarely an either/or choice; many widely used structures combine them to get the best of both:

• Hash tables with separate chaining. An array of buckets gives $O(1)$ indexing to a bucket, while a short linked list per bucket handles collisions. This is the most common array-plus-list hybrid, and it is exactly the structure the next chapter builds.
• Treeified buckets. Some implementations (such as Java's HashMap) start each bucket as a linked list and convert it to a balanced search tree once it grows past a threshold, falling back to a list when it shrinks again. This bounds a pathological bucket's lookup at $O(\log n)$ instead of $O(n)$: a list when small, a tree when large.
• Unrolled linked lists. Each node holds a small array of elements rather than a single value. This restores much of the array's cache locality and amortizes the per-element pointer overhead, while keeping list-style $O(1)$ splicing. It is the structure closest to the intuition of "small arrays joined by links."
• Chunked deques. Some standard-library deques (for example C++'s std::deque) store a sequence of fixed-size array chunks indexed by a small map, giving $O(1)$ push and pop at both ends together with mostly-contiguous, cache-friendly storage.

A related but distinct trick, the small-buffer optimization (as in many small_vector or short-string implementations), keeps up to a fixed number of elements inline in a small array and only spills to a heap-allocated array when that capacity is exceeded. This is array-to-array rather than array-to-list, but it is the other common way structures specialize their layout to the small case.

The lesson is that the array-versus-list decision is less often "which container do I pick" and more often "how do these two primitives combine," because contiguous storage and pointer-linked nodes solve complementary problems. In practice, arrays and dynamic arrays dominate due to cache locality; modern CPUs are optimized for accessing contiguous memory. Linked lists shine where elements are inserted or removed at known nodes without scanning, where stable node identity matters, or where the data is too large to copy during a resize.

Abstract data types: stacks, queues, and deques

The data structures above (arrays and linked lists) are concrete implementations. Now we turn to abstract data types (ADTs): specifications of behavior that can be implemented in multiple ways. A stack, for instance, defines what operations are available (push, pop, peek) and what they do, without prescribing how to store the elements.

Stacks

A stack is a Last-In, First-Out (LIFO) collection. The most recently added element is the first one to be removed, like a stack of plates.

Interface

interface IStack<T> {
  push(value: T): void;     // Add to top
  pop(): T | undefined;      // Remove and return top
  peek(): T | undefined;     // Return top without removing
  readonly size: number;
  readonly isEmpty: boolean;
}

Implementation

A stack is naturally implemented as a linked list where both push and pop operate on the head:

export class Stack<T> implements IStack<T>, Iterable<T> {
  private head: { value: T; next: unknown } | null = null;
  private length: number = 0;

  get size(): number { return this.length; }
  get isEmpty(): boolean { return this.length === 0; }

  push(value: T): void {
    this.head = { value, next: this.head };
    this.length++;
  }

  pop(): T | undefined {
    if (this.head === null) return undefined;
    const value = this.head.value;
    this.head = this.head.next as typeof this.head;
    this.length--;
    return value;
  }

  peek(): T | undefined {
    return this.head?.value;
  }
}

All three operations (push, pop, peek) are $O(1)$.

We could equally implement a stack with a dynamic array (push = append, pop = remove last). The array-based version has better cache locality, while the linked-list version avoids occasional resize costs. For most purposes in TypeScript, the built-in array with push/pop is the pragmatic choice; our implementation here serves pedagogical purposes.

Applications

Stacks appear throughout Computer Science:

• Function call stack. When a function is called, its local variables and return address are pushed onto the call stack. When it returns, they are popped. This is why recursive algorithms can overflow the stack with too many nested calls.
• Parenthesis matching. To check whether brackets are balanced in an expression like ((a + b) * c), push each opening bracket and pop when a matching closing bracket is found.
• Undo/redo. Text editors push each action onto an undo stack. Undoing pops the most recent action.
• Depth-first search. DFS uses a stack (often the call stack via recursion) to track which vertices to visit next.

Tracing through an example

Queues

A queue is a First-In, First-Out (FIFO) collection. Elements are added at the back and removed from the front, like a line of people waiting.

Interface

interface IQueue<T> {
  enqueue(value: T): void;    // Add to back
  dequeue(): T | undefined;   // Remove and return front
  peek(): T | undefined;      // Return front without removing
  readonly size: number;
  readonly isEmpty: boolean;
}

Implementation

A queue maps naturally onto a singly linked list with head and tail pointers: enqueue appends at the tail, dequeue removes from the head.

interface QueueNode<T> {
  value: T;
  next: QueueNode<T> | null;
}

export class Queue<T> implements IQueue<T>, Iterable<T> {
  private head: QueueNode<T> | null = null;
  private tail: QueueNode<T> | null = null;
  private length: number = 0;

  get size(): number { return this.length; }
  get isEmpty(): boolean { return this.length === 0; }

  enqueue(value: T): void {
    const node: QueueNode<T> = { value, next: null };
    if (this.tail !== null) {
      this.tail.next = node;
    } else {
      this.head = node;
    }
    this.tail = node;
    this.length++;
  }

  dequeue(): T | undefined {
    if (this.head === null) return undefined;
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head === null) this.tail = null;
    this.length--;
    return value;
  }

  peek(): T | undefined {
    return this.head?.value;
  }
}

All operations are $O(1)$.

An array-based queue is trickier: naively dequeuing from the front of an array is $O(n)$ because every element must shift. A circular buffer solves this by wrapping indices around modulo the capacity, giving $O(1)$ amortized enqueue and dequeue. Our linked-list implementation avoids this complexity altogether.

Applications

• Breadth-first search. BFS uses a queue to explore vertices level by level.
• Task scheduling. Operating systems use queues to schedule processes for CPU time.
• Buffering. Data streams (network packets, keyboard input) are buffered in queues.
• Level-order tree traversal. Visiting tree nodes level by level requires a queue.

Tracing through an example

Deques

A deque (double-ended queue, pronounced "deck") supports insertion and removal at both ends in $O(1)$ time. It generalizes both stacks and queues.

Implementation

A deque maps directly onto a doubly linked list:

interface DequeNode<T> {
  value: T;
  prev: DequeNode<T> | null;
  next: DequeNode<T> | null;
}

export class Deque<T> implements Iterable<T> {
  private head: DequeNode<T> | null = null;
  private tail: DequeNode<T> | null = null;
  private length: number = 0;

  get size(): number { return this.length; }
  get isEmpty(): boolean { return this.length === 0; }

  pushFront(value: T): void {
    const node: DequeNode<T> = { value, prev: null, next: this.head };
    if (this.head !== null) {
      this.head.prev = node;
    } else {
      this.tail = node;
    }
    this.head = node;
    this.length++;
  }

  pushBack(value: T): void {
    const node: DequeNode<T> = { value, prev: this.tail, next: null };
    if (this.tail !== null) {
      this.tail.next = node;
    } else {
      this.head = node;
    }
    this.tail = node;
    this.length++;
  }

  popFront(): T | undefined {
    if (this.head === null) return undefined;
    const value = this.head.value;
    this.head = this.head.next;
    if (this.head !== null) this.head.prev = null;
    else this.tail = null;
    this.length--;
    return value;
  }

  popBack(): T | undefined {
    if (this.tail === null) return undefined;
    const value = this.tail.value;
    this.tail = this.tail.prev;
    if (this.tail !== null) this.tail.next = null;
    else this.head = null;
    this.length--;
    return value;
  }

  peekFront(): T | undefined { return this.head?.value; }
  peekBack(): T | undefined { return this.tail?.value; }
}

All six operations (pushFront, pushBack, popFront, popBack, peekFront, peekBack) are $O(1)$.

Using a deque as a stack or queue

A deque subsumes both stacks and queues:

• As a stack: use pushFront / popFront (or pushBack / popBack).
• As a queue: use pushBack / popFront.

This flexibility makes the deque a useful building block when the access pattern is uncertain, or when both ends are needed.

Applications

• Sliding window maximum. In the classic interview problem "maximum in every window of size $k$," a deque holds indices of potential maximums. Elements are added at the back and removed from the front (when they fall out of the window) or from the back (when a larger element supersedes them).
• Work-stealing schedulers. Each thread has a deque of tasks. It pops from its own front, while idle threads steal from other deques' backs.
• Palindrome checking. Push characters from both ends; pop from both ends and compare.

Complexity comparison

* Amortized

Summary

This chapter introduced the foundational data structures upon which nearly everything else is built:

• Dynamic arrays provide $O(1)$ random access and $O(1)$ amortized append via the doubling strategy. Insert and remove at arbitrary positions cost $O(n)$ due to shifting.
• Singly linked lists offer $O(1)$ insertion and removal at the head, and $O(1)$ append with a tail pointer, but sacrifice random access and efficient removal from the tail.
• Doubly linked lists add back-pointers for $O(1)$ removal at both ends, at the cost of extra memory per node.
• Stacks (LIFO) are the workhorse of recursion, expression evaluation, and depth-first search.
• Queues (FIFO) power breadth-first search, task scheduling, and buffering.
• Deques generalize stacks and queues, supporting $O(1)$ operations at both ends.

The choice between arrays and linked lists comes down to access patterns. If you need random access or sequential iteration (where cache locality matters), use an array. If insertions and deletions at the endpoints dominate, use a linked list. When in doubt, the dynamic array is usually the right default; it is what most languages provide as their standard collection.

In the next chapter, we will use these building blocks to construct hash tables, which achieve expected $O(1)$ lookup by combining arrays with a hash function.

Exercises

Exercise 7.1. Implement a function isBalanced(expression: string): boolean that uses a Stack to determine whether the parentheses (), brackets [], and braces {} in an expression are properly balanced. For example, isBalanced("((a+b)*[c-d])") should return false (mismatched outer parentheses), while isBalanced("{a*(b+c)}") should return true.

Exercise 7.2. Implement a circular buffer–based queue. Use a fixed-size array and two indices (front and back) that wrap around using modular arithmetic. Compare its performance characteristics with our linked-list–based Queue.

Exercise 7.3. Implement a MinStack<T> that supports push, pop, peek, and an additional min() operation that returns the minimum element in the stack, all in $O(1)$ time. Hint: maintain a second stack that tracks minimums.

Exercise 7.4. Using only two Stacks, implement a Queue. Analyze the amortized time complexity of enqueue and dequeue. Hint: use one stack for enqueuing and another for dequeuing; transfer elements between them lazily.

Exercise 7.5. Implement a function slidingWindowMax(arr: number[], k: number): number[] that returns the maximum value in each window of size $k$ as the window slides from left to right across the array. Use a Deque to achieve $O(n)$ time complexity.