Arrays and Linked Lists

Two ways to store a sequence

Almost every program needs an ordered collection of values. The two foundational ways to store one — arrays and linked lists — make opposite tradeoffs between memory layout and flexibility.

Arrays: contiguous memory

An array allocates a single block of memory and places every element right next to the previous one. Because the address of element i is just base + i × size, the CPU can jump to any index instantly.

// Indexing is O(1) — instant random access
int[] nums = {10, 20, 30, 40};
nums[2];   // 30 — computed by address arithmetic

The cost is that inserting or deleting in the middle requires shifting every element that comes after, which is O(n). Arrays also need their size decided up front (or they must be resized by copying).

Linked lists: nodes and pointers

A linked list stores each value in a separate node that also holds a pointer to the next node. The nodes can live anywhere in memory; the pointers stitch them together.

class Node {
  int value;
  Node next;
}

Inserting at the head is O(1) — just create a node and point it at the old head. No shifting required. But you cannot jump to index 500: you must walk from the head, so random access is O(n).

The tradeoff

• Arrays win on random access and cache locality (CPU prefetching loves contiguous memory).
• Linked lists win on frequent insertions and deletions at known positions.

In practice, arrays (and their dynamic cousins like Python lists and JS arrays) win far more often. Cache locality and predictable access patterns usually matter more than theoretical insert speed.

Doubly linked lists

A doubly linked list gives each node a pointer to both the next and previous node, enabling O(1) deletion when you already hold a reference to the node. This is what Java's LinkedList and the internal structure of many deques use.