Lesson 1 · Linear structures

Array

Arrays place elements in a contiguous logical sequence, making indexed access predictable and iteration cache-friendly. Dynamic arrays add growth while preserving that model.

Why indexing is constant time

If each element occupies a fixed width, the address of index i is base + i × width. The computer does not scan earlier elements. That arithmetic is why arrays support O(1) random access.

Contiguous layout also makes sequential scans efficient: nearby elements arrive in the same cache lines. This practical advantage explains why arrays often outperform linked structures even when both operations are O(n).

A C++ vector<int> and a Java int[] store their integer values in a continuous block. A Python list stores a continuous block of references to Python objects; the integer objects themselves may live elsewhere. The indexing idea remains the same, but the stored item is a reference rather than the integer bytes.

Valid indices run from 0 to length − 1
Reading and replacing by index are O(1)
Searching an unsorted array remains O(n)

Length, capacity, and resizing

A dynamic array reserves capacity beyond its current length. When the storage fills, it allocates a larger block and copies existing elements. Growing geometrically—commonly by a factor near two—keeps append O(1) amortized.

Growing by one slot each time would copy the entire prefix on every append, producing quadratic total work. Geometric growth trades unused capacity for far fewer copies.

Length counts stored elements
Capacity counts available slots
A resize invalidates references into the old storage in low-level languages

Key reference

Terms, operations, and practical uses

Memory model

Base addressThe location of the first slot in the contiguous block.
IndexA zero-based offset used in base + index × element width.
LengthThe number of logical elements currently stored.
CapacityThe number of slots available before another allocation is required.

Costs that matter

Indexed readConstant time because address arithmetic jumps directly to a slot.
Middle insertionLinear time when the suffix must shift right to preserve order.
Dynamic appendAmortized constant time; an occasional resize copies the existing prefix.

Common uses

Prefix summaryStore information about everything before an index to answer later range questions quickly.
Sliding windowTrack one contiguous region while its left and right boundaries move.
Binary searchDiscard half of an ordered search interval after each comparison.

Code example

Insert 25 into a dynamic array

arr = [10, 20, 30, 40]
arr.insert(2, 25)
print(arr)

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> arr = {10, 20, 30, 40};
    arr.insert(arr.begin() + 2, 25);
    for (int value : arr) cout << value << ' ';
}

import java.util.ArrayList;
import java.util.Arrays;

class Main {
    public static void main(String[] args) {
        ArrayList<Integer> arr = new ArrayList<>(
            Arrays.asList(10, 20, 30, 40)
        );
        arr.add(2, 25);
        System.out.println(arr);
    }
}

Input[10, 20, 30, 40], insert 25 at index 2

Output[10, 20, 25, 30, 40]

Example

Run the example step by step

Output

Insertion, deletion, and stable order

Inserting at the end is cheap when capacity remains. Inserting at the front or middle shifts a suffix to preserve order, so it costs O(n). Deletion has the same issue unless order may be discarded and the removed value can be replaced by the last element.

Ask whether order is semantically required. That one constraint often decides whether an array update must shift many elements.

Append: O(1) amortized
Insert or erase at index: O(n)
Pop from end: O(1)
Membership: O(n), unless another index is maintained

Core array reasoning patterns

Two pointers classify an active range; a sliding window maintains a contiguous segment; prefix sums replace repeated range addition with subtraction of two summaries. Sorting can expose monotonic structure and enable binary search.

Each technique works because a compact invariant replaces repeated scanning. State what the indices or prefix value mean before writing the loop.

Two pointers for paired or partitioned scans
Sliding windows for evolving contiguous ranges
Prefix sums for repeated range queries
Binary search for monotonic boundaries