A linked list stores a sequence as separate nodes connected by references rather than requiring the elements to occupy one contiguous block of memory.

A singly linked node contains a value and a reference to the next node:

[value | next] → [value | next] → [value | next] → null

Traversal

To reach the $i$th element, the list must follow the links from an earlier node. Random indexed access is therefore linear in the distance traversed.

Insertion and removal

If a reference to the relevant node is already known, inserting or removing a neighboring node can require only a small constant number of link changes.

Finding that position may still require traversal.

Doubly linked lists

A doubly linked list stores both next and previous references, allowing traversal in either direction at the cost of additional memory and link maintenance.

Abstract cost versus physical cost

Linked lists can have attractive asymptotic insertion properties while performing poorly in traversal-heavy workloads because nodes may be scattered throughout memory. Each node also carries reference overhead.

This contrast between abstract operation counts and physical memory access is one reason data-structure choice cannot be reduced to Big-O notation alone.