What is a Linked List

A linked list is a sequence of nodes scattered throughout memory, where each node holds a value and a pointer (reference) to the next node. Unlike an array, the elements are not stored contiguously — they can live anywhere in memory, connected only by pointers.

How it works

Each node contains two things: the data and a pointer to the next node. The last node points to null, marking the end of the list.

[data|next] → [data|next] → [data|next] → null

Insertion is O(1) if you already have a reference to the position. To insert a new node, allocate it anywhere in memory, set its pointer to the next node, and update the previous node's pointer. No shifting required — you just rewire two pointers.

Access is O(n) because there is no formula to jump to the fifth element. You must start at the head and follow pointers one by one: first node, second node, third, fourth, fifth. Random access that takes one step in an array takes five steps here.

A doubly linked list adds a pointer to the previous node as well, enabling traversal in both directions. This makes deletion O(1) when you have a reference to the node, since you can reach both neighbors to rewire the links.

null ← [prev|data|next] ⇄ [prev|data|next] ⇄ [prev|data|next] → null

The cache performance of linked lists is poor compared to arrays. Because nodes are scattered in memory, traversing them causes frequent cache misses — each pointer chase may load an entirely new cache line.

Why it matters

Linked lists are the natural choice when you need frequent insertion and deletion at arbitrary positions but rarely need random access. They're the building blocks behind many higher-level structures — hash maps use linked lists for chaining collisions, stacks and queues can be implemented with linked lists, and graphs use them to store adjacency lists.

See How Arrays and Linked Lists Work for a detailed side-by-side comparison.