Arrays and Linked Lists

Every data structure you will ever study is, at its lowest level, built from one of two primitives: a contiguous block of memory, or a collection of separately-allocated nodes stitched together with pointers. Everything else — stacks, queues, trees, graphs, hash tables — is a policy layered on top of one of those two foundations. Understanding the foundations deeply, rather than just memorising the complexity table for each, is what lets you reason confidently about data structures you’ve never seen before. That is what this chapter is actually about.

Memory Layout: The One Fact That Drives Every Trade-Off

Your computer’s memory is a long, flat sequence of bytes, each with a numbered address. An array stakes out a contiguous claim on that sequence: if the first element sits at address base, and each element occupies size bytes, then element i sits at address base + i × size. The CPU computes this in a single arithmetic operation — no traversal, no following of pointers, just arithmetic. This is why array access is O(1): the address of any element is equally quick to compute, regardless of which element it is or how large the array is.

A linked list takes the opposite approach: each element lives in its own separately-allocated node, scattered anywhere in memory. The node holds the element’s value and a pointer to the next node — without that pointer, there’d be no way to find the next element at all. To reach element i, you must follow i pointers in sequence. There is no shortcut — you cannot compute where element i lives without visiting all the elements before it.

That single difference — “compute the address arithmetically” versus “follow a chain of pointers” — is the source of every trade-off this chapter discusses. Keep it in focus.

Arrays

Traversal and Access

Random access is O(1): arr[i] is syntactic sugar for *(arr + i), which the compiler lowers to a single load instruction from a computed address. Iterating the whole array is simply computing arr + 0, arr + 1, …, arr + n-1 in sequence — consecutive memory addresses, which the CPU’s hardware prefetcher handles beautifully.

#include <stdio.h>

/* print all elements and return the index of the first occurrence of target,
   or -1 if not found */
int linear_search(const int arr[], int n, int target) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
        if (arr[i] == target) {
            printf("\nFound at index %d\n", i);
            return i;
        }
    }
    printf("\nNot found\n");
    return -1;
}

Insertion and Deletion

Inserting at the end (if space remains) is O(1): write the value at index n, increment n. Inserting anywhere else requires shifting every element from the insertion point to the end one position to the right — O(n) in the worst case:

/* insert val at position `at`, shifting elements right.
   Assumes arr has room for one more element. */
void array_insert(int arr[], int *n, int at, int val) {
    for (int i = *n; i > at; i--) {
        arr[i] = arr[i - 1];          /* shift right, starting from the end */
    }
    arr[at] = val;
    (*n)++;
}

/* delete the element at position `at`, shifting elements left */
void array_delete(int arr[], int *n, int at) {
    for (int i = at; i < *n - 1; i++) {
        arr[i] = arr[i + 1];          /* shift left */
    }
    (*n)--;
}

The shift starts from the end on insertion (to avoid overwriting before copying) and from the target on deletion — a subtle but important direction detail. Getting it backwards corrupts data.

Dynamic Arrays

A static array’s size is fixed at declaration. A dynamic array grows on demand: when the backing store is full, allocate a new block (typically twice the current size), copy all elements over, and free the old block.

#include <stdlib.h>

typedef struct {
    int *data;
    int  size;
    int  capacity;
} DynArray;

void da_init(DynArray *a) {
    a->capacity = 4;
    a->data = malloc(a->capacity * sizeof(int));
    a->size = 0;
}

void da_push(DynArray *a, int val) {
    if (a->size == a->capacity) {
        a->capacity *= 2;
        a->data = realloc(a->data, a->capacity * sizeof(int));
    }
    a->data[a->size++] = val;
}

int da_pop(DynArray *a) {
    return a->data[--a->size];
}

void da_free(DynArray *a) {
    free(a->data);
    a->data = NULL;
    a->size = a->capacity = 0;
}

The doubling strategy keeps the amortised cost of da_push at O(1). Occasional O(n) copies happen, but they happen exponentially rarely — by the time you’ve pushed n elements, you’ve copied at most 2n elements total across all resizes, giving O(1) average per push. This is the same argument the Complexity Analysis chapter made for IntVector.

Pause and think: Why double (×2) rather than grow by a fixed amount (say, +10 slots each time)? If you grow by a constant, pushing n elements triggers O(n) resizes, each copying O(n) elements — O(n²) total work. If you double, there are only O(log n) resizes, and their copy costs sum to O(n). The factor of 2 isn’t magic — any factor > 1 gives amortised O(1); the choice is a memory-vs-speed trade-off, and real implementations often use 1.5× or 2× depending on the workload.

Two-Dimensional Arrays

A 2D array is a rectangular grid identified by two indices: row and column. In C, A[ROWS][COLS] is stored in row-major order — all of row 0 first, then row 1, and so on. Element A[i][j] sits at offset i × COLS + j from the base address, giving the same O(1) arithmetic access as 1D.

#define ROWS 3
#define COLS 4

void fill_matrix(int A[ROWS][COLS]) {
    for (int i = 0; i < ROWS; i++)
        for (int j = 0; j < COLS; j++)
            A[i][j] = i * COLS + j;
}

void insert_row(int A[][COLS], int *n_rows, int at, const int new_row[COLS]) {
    for (int i = *n_rows - 1; i >= at; i--)
        for (int j = 0; j < COLS; j++)
            A[i + 1][j] = A[i][j];
    for (int j = 0; j < COLS; j++)
        A[at][j] = new_row[j];
    (*n_rows)++;
}

void delete_row(int A[][COLS], int *n_rows, int at) {
    for (int i = at; i < *n_rows - 1; i++)
        for (int j = 0; j < COLS; j++)
            A[i][j] = A[i + 1][j];
    (*n_rows)--;
}

Inserting or deleting a row costs O(ROWS × COLS). Column operations are the same arithmetic cost but stride through memory in COLS-sized steps — one element per row — rather than sequentially. This kills cache performance for large matrices. When you reshape 2D data frequently, the choice of row-major vs. column-major layout (which languages like Fortran use) directly determines which dimension’s operations are fast.

Linked Lists

Singly Linked List

Each node holds a value and a pointer to the next node:

#include <stdlib.h>
#include <stdio.h>

typedef struct Node {
    int val;
    struct Node *next;
} Node;

Node *node_new(int val) {
    Node *n = malloc(sizeof(Node));
    n->val  = val;
    n->next = NULL;
    return n;
}

/* traverse the whole list, printing every value */
void list_print(const Node *head) {
    for (const Node *cur = head; cur != NULL; cur = cur->next)
        printf("%d → ", cur->val);
    printf("NULL\n");
}

/* return a pointer to the first node whose value equals target, or NULL */
Node *list_search(Node *head, int target) {
    for (Node *cur = head; cur != NULL; cur = cur->next)
        if (cur->val == target) return cur;
    return NULL;
}

Insertion and Deletion

Given a pointer to the predecessor node, insertion and deletion are O(1) — just rewire two pointers:

void insert_after(Node *pred, int val) {
    Node *new_node = node_new(val);
    new_node->next = pred->next;
    pred->next     = new_node;
}

/* delete the node immediately after pred */
void delete_after(Node *pred) {
    if (pred->next == NULL) return;
    Node *doomed  = pred->next;
    pred->next    = doomed->next;
    free(doomed);
}

/* insert at the front of the list — O(1) */
Node *prepend(Node *head, int val) {
    Node *n = node_new(val);
    n->next = head;
    return n;            /* caller must update their head pointer */
}

Finding the predecessor still costs O(n). The O(1) benefit only materialises when you already hold the right pointer — for example, when iterating and modifying simultaneously, or when building a stack.

Doubly Linked List

Adding a prev pointer enables O(1) removal of any node you already have a pointer to — not just the one after a known predecessor:

typedef struct DNode {
    int val;
    struct DNode *prev;
    struct DNode *next;
} DNode;

/* insert new_node before anchor */
void dlist_insert_before(DNode **head, DNode *anchor, int val) {
    DNode *n = malloc(sizeof(DNode));
    n->val   = val;
    n->next  = anchor;
    n->prev  = anchor ? anchor->prev : NULL;
    if (n->prev)  n->prev->next = n;
    if (anchor)   anchor->prev  = n;
    if (!n->prev) *head = n;    /* inserted before the old head */
}

/* remove a node given only a pointer to it — O(1) */
void dlist_remove(DNode **head, DNode *node) {
    if (node->prev) node->prev->next = node->next;
    else            *head            = node->next;
    if (node->next) node->next->prev = node->prev;
    free(node);
}

The extra prev pointer doubles pointer storage per node — a real cost for large lists of small values.

Circular Linked List

A circular linked list has its last node’s next point back to the head — a ring with no NULL. A single tail pointer gives O(1) access to both ends (tail for the last, tail->next for the first), making it natural for round-robin scheduling and fixed-size buffers.

void circular_insert(Node **tail, int val) {
    Node *node = node_new(val);
    if (*tail == NULL) {
        node->next = node;
    } else {
        node->next   = (*tail)->next;
        (*tail)->next = node;
    }
    *tail = node;
}

void circular_print(const Node *tail) {
    if (!tail) return;
    const Node *cur = tail->next;   /* head */
    do {
        printf("%d → ", cur->val);
        cur = cur->next;
    } while (cur != tail->next);
    printf("(back to head)\n");
}

The do-while is mandatory: there is no NULL to detect the end; the stopping condition is wrapping back to the starting node.

List Reversal

Reversing a singly linked list in place: one pass, three pointers, O(n) time, O(1) space.

Node *list_reverse(Node *head) {
    Node *prev = NULL;
    Node *cur  = head;
    while (cur != NULL) {
        Node *next = cur->next;   /* save next before overwriting */
        cur->next  = prev;
        prev = cur;
        cur  = next;
    }
    return prev;                  /* new head */
}

Saving cur->next before overwriting it is the entire trick — lose that pointer and you lose the rest of the list.

Cache Behaviour: Why Arrays Win in Practice

Arrays are cache-friendly: elements sit at consecutive addresses, so loading arr[0] pulls arr[0] through arr[15] (or however many fit in one cache line, typically 64 bytes) into the L1 cache simultaneously. arr[1] through arr[15] are then essentially free. Linked list nodes are scattered across the heap: each cur = cur->next dereferences a pointer that almost certainly points somewhere the CPU hasn’t prefetched. Each such access is a likely cache miss — a round-trip to main memory costing hundreds of nanoseconds.

In practice, iterating a linked list of a million elements is often 10–20× slower than iterating an array of equal size, even though both are O(n) asymptotically. Asymptotic complexity describes how performance scales; constant factors and cache behaviour determine the actual wall-clock time. For sequential-access workloads on modern hardware, that constant factor can easily dominate.

Operation Summary

*O(1) if a tail pointer is maintained. †With a tail pointer.

Choosing Between Them

Use an array when:

• You need random access by index
• You iterate sequentially — cache behaviour matters
• The size is roughly known or changes infrequently

Use a linked list when:

• You insert or delete at arbitrary positions frequently, and you hold pointers to the relevant nodes
• You need O(1) prepend regardless of size
• You are implementing other structures whose internal operations require pointer manipulation (stacks, queues, hash-table chaining)

Bringing It Together: Practice as a Problem-Solver

1. Predict, then measure. Implement both linear_search on an array and list_search on a linked list. Add a counter that increments on every comparison. Run both on a list of 10,000 elements, searching for the last element. The comparison counts will be identical — but time the actual wall-clock execution too. What does the timing gap reveal about what asymptotic analysis does and doesn’t capture?

2. Trace pointer rewiring by hand. Draw a singly linked list with nodes A → B → C → D → NULL. Trace through insert_after(B_ptr, X) step by step, redrawing the pointer diagram after each line. Now trace delete_after(B_ptr). Which line, if executed in the wrong order, would cause a memory leak or a dangling pointer?

3. Amortised analysis. Starting with a DynArray of capacity 1, push elements one at a time until you have 16 elements. Draw a table showing size, capacity, and whether a resize occurred at each push. Count the total number of individual element-copy operations across all resizes. Divide by 16. What does this per-push average tell you about the O(1) amortised claim?

4. Design challenge. You need a data structure that supports: O(1) push to the front, O(1) push to the back, O(1) pop from the front, and O(n) access by index. Which of the structures in this chapter comes closest — and what would you need to add or change to hit all four bounds simultaneously?