DSA Linear Structures

Arrays

The ranking service stores n = 10⁷ scored posts in order and must fetch post i for a feed page in constant time. A linked list walk would burn linear work per click. An array turns the index into an address: base + i × width.

Arrays are sequences with . Keep and separate, and remember that middle inserts pay for preserving order.

What happens first?

Fix the layout

Static fixed capacity, or dynamic buffer with length/capacity?

Index → address arithmetic for a[i].

Live values sit in 0..length−1 with no gaps.

Growth policy

Geometric resize keeps append amortized Θ(1).

What actually happens

Naive idea: store posts in a singly linked list “because inserts look cheap.” Fetching the i-th feed item then walks i nodes every time.

Break: at n = 10⁷ and many page views, those walks dominate. Middle insert into an array is Θ(n) too, but index reads stay Θ(1). The wrong structure makes the hot path pay for the wrong operation.

Better idea: use a buffer when integer-indexed reads and scans dominate. Grow geometrically so append is Θ(1). Reach for a deque or map only when the hot path is front edits or arbitrary keys.

Invariant

Live values occupy indices 0 .. length − 1 with no gaps in the logical sequence. Spare slots from length through capacity − 1 are not part of the sequence. Every mutating API that claims to preserve order must keep this true.

How to choose an array

1. Do you need integer-indexed random access? If yes, arrays (or typed buffers) are the default. Linked lists lose here.

2. Where do inserts and deletes happen? Mostly at the end: dynamic array. Both ends: deque. Middle edits dominate: consider another structure.

3. Is locality part of the budget? Sequential scans benefit from . Pointer-heavy graphs of tiny objects often do not.

Quantitative check

n = 10⁷ appends with capacity doubling copy fewer than 2n elements total (about 2 × 10⁷ moves), so append is Θ(1) amortized. Growing by one slot each time copies 1 + 2 + … + n ≈ 5 × 10¹³ moves: Θ(n²) and unusable at that scale.

From index to address

Representation invariant

Live values occupy indices 0 through length - 1, with no gaps in the logical sequence. Physical spare slots may exist from length through capacity - 1.

Constant-time access

For fixed-width elements, locating a[i] uses a fixed amount of arithmetic regardless of i or n. O(1) does not mean one CPU cycle; cache misses and bounds checks still matter.

What is contiguous?

In an array of values, the values are adjacent. In an array of references, the references are adjacent, while the referenced objects may be scattered elsewhere.

address(a[i]) = base(a) + i × sizeof(element)

Interactive memory and resizing lab

Select cells to connect an index with its address and fetched neighborhood, then switch modes to expose the expensive operation behind a capacity-changing append.

Array memory laboratory

Connect constant-time indexing to addresses, then inspect the occasional linear-time resize hidden inside an append.

Index expression

a[5]

Address

0x1000 + 5 × 4 = 0x1014

Fetched demo line

indices 4–7

One multiplication and one addition locate the cell.

The highlighted neighboring values model spatial locality. Real cache-line size and element width vary; this lab groups four integers to make the transfer visible.

Operation costs and the reason behind them

Operation	Best	Worst	Why
Read or overwrite a[i]	Θ(1)	Θ(1)	Address is computed directly from the index.
Traverse all values	Θ(n)	Θ(n)	Every element must be visited.
Search by value	Θ(1)	Θ(n)	Best case is the first cell; unsorted data gives no elimination rule.
Append with spare capacity	Θ(1)	Θ(1)	Write at a[length], then increment length.
Append to a full dynamic array	Θ(n)	Θ(n)	Allocate and copy before writing the new value.
Insert/delete near the middle	Θ(n)	Θ(n)	A suffix shifts to preserve order and contiguity.
Pop from the end	Θ(1)	Θ(1)	Decrease length; no shifting is needed.

These bounds assume an array already exists and order must be preserved. Deleting by swapping with the last element can be Θ(1), but only when order is irrelevant and the index is already known.

Dynamic arrays: expensive sometimes, cheap on average

A dynamic array stores a pointer to a buffer plus length and capacity. An append with room is Θ(1). When full, it allocates a geometrically larger buffer, copies or moves all live elements, then frees the old buffer.

Why geometric growth matters

With capacity doubling, copies across n appends form 1 + 2 + 4 + …, which is less than 2n. Total work is Θ(n), so each append costs Θ(1) amortized. Growing by one slot instead produces 1 + 2 + … + n = Θ(n²) total work.

Geometric growth trades memory slack for speed. Common factors range roughly from 1.5× to 2×, but the exact policy is an implementation detail. A single append is still allowed to take Θ(n); amortized analysis is a guarantee over a sequence, not a per-call latency bound.

TypeScript

typescript

class DynamicArray<T> {
  private data: (T | undefined)[] = new Array(1);
  length = 0;

  push(value: T) {
    if (this.length === this.data.length) {
      const next = new Array<T | undefined>(this.data.length * 2);
      for (let i = 0; i < this.length; i++) next[i] = this.data[i];
      this.data = next;                 // old addresses may be invalid
    }
    this.data[this.length++] = value;
  }
}

Java

java

final class DynamicArray<T> {
    private Object[] data = new Object[1];
    private int size = 0;

    int size() {
        return size;
    }

    void add(T value) {
        if (size == data.length) {
            Object[] next = new Object[data.length * 2];
            System.arraycopy(data, 0, next, 0, size);
            data = next; // references to the old backing array are stale
        }
        data[size++] = value;
    }
}

Cache locality: why the same Big-O can run differently

CPUs transfer memory in blocks called cache lines (64 bytes is common on desktop/server processors, but it is not universal). A sequential array walk uses most bytes fetched and is easy for hardware prefetchers to predict. A linked structure can perform the same Θ(n) visits while waiting on unrelated addresses at every step.

Spatial locality

Nearby indices usually share a cache line, so one miss can supply several future elements.

Temporal locality

A recently used cell or line may remain cached when an algorithm revisits it soon.

Predictable stride

Forward, fixed-stride loops are easier to prefetch and vectorize than data-dependent pointer jumps.

Language caveat: JavaScript arrays are high-level objects, not guaranteed C-style buffers. Engines often optimize dense, same-shaped arrays, while sparse indices or mixed value kinds can change their internal representation. Use typed arrays such as Int32Array when packed numeric storage and fixed widths are part of the contract.

Two-dimensional arrays and traversal order

Address formulas

Row-major

Rows are laid out consecutively, as in C/C++ rectangular arrays and many numerical libraries.

offset = (row × columns + column) × width

Column-major

Columns are consecutive, as in Fortran and some mathematical environments.

offset = (column × rows + row) × width

Loop order

TypeScript

typescript

// Row-major storage: keep the column loop inside.
for (let row = 0; row < rows; row++) {
  for (let col = 0; col < cols; col++) {
    consume(matrix[row][col]);
  }
}

// Flattened index for a rectangular row-major buffer:
const value = buffer[row * cols + col];

Java

java

final class RowMajorTraversal {
    static void traverse(int[][] matrix) {
        for (int row = 0; row < matrix.length; row++) {
            for (int col = 0; col < matrix[row].length; col++) {
                consume(matrix[row][col]);
            }
        }
    }

    static int at(int[] buffer, int row, int col, int columns) {
        return buffer[row * columns + col];
    }

    private static void consume(int value) {
        // Process value.
    }
}

Match the inner loop to the contiguous dimension. JavaScript arrays of arrays and Java's int[][] both permit jagged rows; validate row lengths before applying a rectangular formula.

Array patterns worth recognizing

Prefix aggregates

Build Θ(n), query Θ(1)

Store prefix[i + 1] = prefix[i] + a[i]. Then sum(left..right) = prefix[right + 1] - prefix[left]. The extra leading zero removes a boundary branch.

Two pointers / sliding window

Usually Θ(n)

Represent a changing interval with indices instead of repeatedly copying subarrays. Prove why each pointer only moves forward or why a discarded region is impossible.

Frequency array

Θ(n + U) time, Θ(U) space

When keys are integers in a small known universe U, direct indexing can replace hashing and powers counting sort, histograms, and lookup tables.

In-place partition

Θ(n) time, Θ(1) extra space

Maintain regions with explicit meanings: processed, accepted, rejected, unknown, and swap the next value into the region required by the invariant.

Representation choices for data-heavy work

Array of structures (AoS)

Good when each operation consumes most fields of one record.

TypeScript

typescript

[{ x: 1, y: 2 }, { x: 4, y: 8 }]

Java

java

record Point(int x, int y) {}

final class AoSExample {
    static final Point[] POINTS = {
        new Point(1, 2),
        new Point(4, 8)
    };
}

Structure of arrays (SoA)

Good when a hot loop consumes one field across many records; useful for SIMD and columnar analytics.

TypeScript

typescript

{ x: [1, 4], y: [2, 8] }

Java

java

record Coordinates(int[] x, int[] y) {}

final class SoAExample {
    static final Coordinates POINTS = new Coordinates(
        new int[] {1, 4},
        new int[] {2, 8}
    );
}

Bitsets compress booleans into bits. Sparse matrix formats such as CSR store only non-zero values plus index metadata. Both save memory for the right data distribution, but give up the simplest one-cell-per-value representation.

Common failure modes

Off-by-one bounds

Valid indices are 0 through length - 1. Prefer half-open ranges [start, end), whose size is end - start.

Confusing length and capacity

Only indices below length hold live values. Spare capacity is an implementation resource, not part of the logical sequence.

Invalidated references

A resize can move the buffer. In languages with raw iterators or pointers, treat them as invalid after capacity-changing operations.

Accidental quadratic shifting

Repeatedly inserting or removing at the front of an array moves a growing suffix. Use a deque or a head index when front operations dominate.

Aliasing and slices

A view may share storage with its source while a copied slice does not. Know which contract the language or library provides before mutating.

Sparse or mixed JavaScript arrays

Large holes, named properties, and mixed shapes can forfeit packed-array optimizations. Choose Map or typed arrays when those semantics fit better.

How to choose the structure

Prefer an array when

integer-indexed random access and traversal dominate;
compact storage and predictable iteration matter;
insertion and deletion mostly happen at the end.

Consider an alternative when

lookup is by arbitrary key: hash map or ordered map;
both ends change frequently: deque or ring buffer;
ordered middle edits dominate: tree/rope, depending on access needs.

Exercises

For n = 10⁵ front-inserts into a dynamic array that shifts the suffix each time, estimate total element moves. What structure keeps those inserts cheap?
Prove (or sketch) why capacity doubling makes n appends Θ(n) total work. What goes wrong if capacity grows by +1 each resize?
A language returns a slice that aliases the backing buffer. After a capacity-changing append, which assumptions about the old view become false?

Primary sources

Cormen et al., Introduction to Algorithms (CLRS): aggregate analysis / amortized cost of table expansion.
Goodrich, Tamassia & Goldwasser: array-based lists and geometric resizing.
Language docs for ArrayList / std::vector growth policies and iterator invalidation.

Takeaway

Array performance follows directly from representation: arithmetic gives Θ(1) indexing, contiguity gives strong locality, preserving order makes middle edits Θ(n), and geometric spare capacity turns repeated append into amortized Θ(1).