Arrays and
Linked Lists

Memory layout

Base address: 0x1000
Element size: 4 bytes (int32)

Index:   [  0  ] [  1  ] [  2  ] [  3  ] [  4  ]
Address: 0x1000  0x1004  0x1008  0x100C  0x1010
Value:      10      25      37      42      58

Declaration examples

int scores[5] = {10, 25, 37, 42, 58};   // stack
int *heap_arr = malloc(5 * sizeof(int)); // heap

Characteristics

Why O(1) access matters

The formula base + index * element_size is a single arithmetic operation. No matter the array size, access time is constant.

Spatial locality

Accessing arr[i] loads an entire cache line (64 bytes). If arr[i+1] is next, it is already in L1 cache — a cache hit.

Cache line (64 bytes) loaded on access to arr[3]:
┌────┬────┬────┬────┬────┬────┬────┬────┐
│ [0]│ [1]│ [2]│ [3]│ [4]│ [5]│ [6]│ [7]│
└────┴────┴────┴────┴────┴────┴────┴────┘
               ▲ requested
        entire line loaded into L1

Cache hierarchy latency

Growth strategy

When the array is full and a new element must be added:

• Allocate a new array of k * current_capacity (typically k = 2)
• Copy all existing elements to the new array
• Free the old array and insert the new element

Size vs capacity

Capacity: 8    Size: 5

[ 10 ][ 25 ][ 37 ][ 42 ][ 58 ][    ][    ][    ]
                                ▲ size       ▲ capacity

Key operations

*Amortised — resize triggers full copy

The doubling argument

When capacity doubles on overflow, the total cost of n push-back operations is O(n), giving an amortised cost of O(1) per operation.

Proof sketch (aggregate method)

Operations: 1  2  3  4  5  6  7  8  9
Cost:       1  1  1  1  1  1  1  1  1  (inserts)
Resize at:        +2    +4          +8 (copies)

Total for n inserts:
  n (inserts) + 1 + 2 + 4 + ... + n
= n + (2n - 1)
= 3n - 1 = O(n)

Amortised per insert = O(n)/n = O(1)

Growth factor trade-offs

Node structure

struct Node {
    int   data;
    Node* next;
};

Memory layout

Characteristics

• O(n) access — must traverse from head to reach element i
• O(1) insert/delete at head — just update the head pointer
• O(n) insert/delete at position — must traverse to predecessor
• No wasted capacity — each node allocated individually
• Extra 8 bytes per node (one pointer on 64-bit)
• No reallocation — the list never copies elements

Insertion at head — O(1)

Node* insert_head(Node* head, int value) {
    Node* n = malloc(sizeof(Node));
    n->data = value;
    n->next = head;
    return n;  // new head
}

Insertion after a given node — O(1)

void insert_after(Node* prev, int value) {
    Node* n = malloc(sizeof(Node));
    n->data = value;
    n->next = prev->next;
    prev->next = n;
}

Deletion after a node — O(1)

void delete_after(Node* prev) {
    Node* target = prev->next;
    prev->next = target->next;
    free(target);
}

Traversal — O(n)

void print_list(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

Node structure

struct DNode {
    int    data;
    DNode* prev;
    DNode* next;
};

Memory layout

Advantages over singly linked

• O(1) delete given a node pointer — no need to find predecessor
• Backward traversal — iterate from tail to head
• O(1) insert before a given node — direct access to predecessor
• Easier LRU cache, undo/redo implementation

Cost

• Two pointers per node — 16 bytes overhead on 64-bit
• More complex updates — four pointer changes per insert/delete

Without sentinel

Every operation must check for empty list, head insert, and tail insert as special cases.

With sentinel

Empty list:
  sentinel.next = sentinel
  sentinel.prev = sentinel

After inserting 10, 25, 37:
  SEN ──▶ 10 ──▶ 25 ──▶ 37 ──▶ SEN
  SEN ◀── 10 ◀── 25 ◀── 37 ◀── SEN

Simplified insertion

// Insert after any node — no NULL checks
void insert_after(DNode* node, int val) {
    DNode* n = malloc(sizeof(DNode));
    n->data       = val;
    n->next       = node->next;
    n->prev       = node;
    node->next->prev = n;
    node->next       = n;
}

Singly circular

Traversal

void print_circular(Node* start) {
    if (!start) return;
    Node* curr = start;
    do {
        printf("%d -> ", curr->data);
        curr = curr->next;
    } while (curr != start);
}

Use cases

Structure

How it works

• Level 0 is a standard sorted linked list containing all elements
• Each higher level is a "fast lane" containing a random subset
• A node is promoted with probability p (typically 0.5)
• Expected height: O(log n)

Why skip lists?

• Simpler to implement than balanced BSTs
• Lock-free variants are easier than lock-free trees
• Expected O(log n) search, insert, delete
• No rotations — balancing is probabilistic

Search — expected O(log n)

Start at the highest level. Move right while the next node's key is less than the target. Drop down one level and repeat.

Search for 33:

L3: H ─────────────── 42 (too far, drop)
L2: H ────── 17 ───── 42 (too far, drop)
L1: ... 17 ── 25 ──── 42 (too far, drop)
L0: ... 25 ── 33 FOUND

Insert

• Search for position (track predecessors at each level)
• Flip a coin repeatedly to determine the new node's height
• Splice the node into each level up to its height

Complexity

Delete

• Search for the node (track predecessors at each level)
• Remove the node from every level it appears in
• If top level is now empty, reduce max level

The trick

Each node stores:
  link = prev_addr XOR next_addr

Forward traversal:
  next = prev_addr XOR node->link

Backward traversal:
  prev = next_addr XOR node->link

Example

Node A         Node B         Node C
link = 0^B     link = A^C     link = B^0
     = B            = A^C          = B

Forward from A (prev=0):
  next = 0 XOR B = B
From B (prev=A):
  next = A XOR (A^C) = C
From C (prev=B):
  next = B XOR B = 0 (end)

Trade-offs

Structure

How it works

• Each node holds an array of up to B elements (block size, e.g. 4–16)
• Nodes are linked together like a standard linked list
• Overflow: node splits into two half-full nodes
• Underflow: node merges with a neighbour

Performance comparison

Why arrays dominate in benchmarks

The linked list cache problem

• Each node may reside on a different cache line — pointer chasing defeats prefetch
• Allocator scatters nodes across pages — poor TLB hit rate
• Small nodes waste most of a 64-byte cache line
• Traversal can be 10–100x slower than array traversal

Mitigations

• Arena/pool allocators — allocate nodes from a contiguous block; restores locality
• Unrolled linked lists — amortise pointer overhead across multiple elements
• Intrusive lists — embed the link inside the data structure (Linux kernel pattern)

Key takeaways

• Arrays provide O(1) access and excellent cache performance — the default choice
• Dynamic arrays give O(1) access + amortised O(1) append
• Linked lists trade cache performance for O(1) insert/delete at known positions
• Doubly linked lists enable O(1) deletion given a node pointer — essential for LRU caches
• Skip lists offer O(log n) expected performance with simpler concurrency than balanced trees
• XOR and unrolled linked lists are niche optimisations — know they exist
• Cache locality dominates real-world performance — profile before choosing a linked structure
• Arena allocators can restore locality to linked structures when needed

Recommended reading