DSA Linked Structures
Linked Lists in Memory
The feed renderer walks 200,000 story nodes on every scroll tick. Big-O says Θ(n), but the UI still stutters: each next load misses cache while an array of the same payloads streams through a line.
A linked list separates from physical placement. That flexibility enables cheap splices and explains much of the real cost: , weaker , and overhead.
Memory journey
Order is reachability, not address arithmetic.
Next address appears only after the current load.
Placement
Scattered, pooled, arena, intrusive, or index links.
Who frees, who aliases, what survives unlink.
What actually happens
Naive idea: “lists use more memory than arrays by one pointer.” That undercounts headers, padding, allocator metadata, and the runtime cost of dependent loads when nodes are scattered.
Better idea: measure the representation you ship. Keep list semantics if splices dominate, but choose pools, arenas, or index links when and allocation dominate. State before mutating shared suffixes.
The improved design still fails when you pick a node-per-allocation list solely because “insert looks O(1)” while the workload is scan-heavy, or when stale handles outlive reclamation.
Invariant (logical vs physical)
Following links from head always recovers the intended sequence. Physical addresses may change (pools, moving GC) without changing that logical order, as long as every live reference is updated and no still-needed suffix is overwritten.
How to choose a memory layout
1. Scan vs splice? Dense scans favor arrays or pooled/unrolled nodes. Known-handle splices favor ordinary links.
2. Shared lifetime? Arenas reclaim together. Individual free lists need careful .
3. Evidence? Measure node size, allocation count, and end-to-end time. Big-O alone will not predict the stutter.
Quantitative check
Reaching index i on a list is i dependent loads. On n = 10⁶, a full scan is a million chases; an array of 8-byte values is about 8 MB of sequential traffic. If each missed node costs tens of nanoseconds extra, the list scan can be multiple× slower at the same Θ(n) label.
Logical contract
head identifies the first node; each link identifies the next. Following links, not address arithmetic: defines list order.
Storage contract
Nodes may be separate allocations. They can be adjacent by chance or by a pool, but ordinary list semantics do not require it.
Performance consequence
Reaching node i forms a dependent chain of i link reads. Big-O captures the count; locality and allocation policy shape the constant factors.
Trace the memory dependency
Choose a logical index, step through the list, and switch between scattered and pooled placement. The array reaches the same element by an address formula; the list cannot know the next node’s location until it reads the current node.
Addressing versus pointer chasing
Access the same logical index in a contiguous array and a linked list. The memory groups are illustrative, not fixed-size claims about a particular CPU cache.
Choose logical index i
Contiguous array
Compute the destination; no preceding element is part of the lookup.
Singly linked list
Each next reference reveals the location needed by the following step.
Illustrative physical allocation map
Each tile represents a node-sized allocator slot. Groups of four only model locality: real cache lines, pages, object movement, and allocator size classes depend on the runtime and machine.
Next links followed
0 of 4
List nodes read so far
1
Array predecessors read
0
At node 0; next is still unknown to the traversal.
Read this node’s next field before node 1 can be located.
Logical order is not physical order
If A.next = B, then B follows A logically. It does not imply that B is stored at the next numeric address. An allocator may place B earlier, later, nearby, on another page, or: under a moving garbage collector: at a different location later.
The logical chain
This is the abstraction algorithms reason about: reachability and sequence.
One possible physical placement
The links stored inside A and B recover the logical sequence from these unrelated locations.
What one node really costs
“Payload plus one pointer” is a useful first model, but not a byte-accurate measurement. The language ABI, runtime, allocator, field ordering, and node type all contribute.
| Component | Why it exists | Size rule |
|---|---|---|
| Payload | The value or a reference to the value owned by this node. | Depends on T and the language representation |
| Link field(s) | A next reference for a singly linked list; next and previous for a doubly linked list. | Usually one or two reference-width fields |
| Object header | Managed runtimes may store type, locking, or garbage-collector metadata with each object. | Runtime-specific; a C struct may have none |
| Padding / alignment | Rounds fields or the complete node to addresses the ABI and allocator support efficiently. | Depends on field order and alignment rules |
| Allocator metadata | A heap allocator can track size classes and free lists outside or adjacent to an allocation. | Allocator-specific and sometimes amortized per slab |
A cost model, not a universal sizeof
field layout = alignEach(header, payload, links)
node object ≈ roundUp(field layout, object alignment)
total list ≈ n × (node object + per-allocation overhead)
+ head/tail metadata
array buffer ≈ capacity × payload width
unused array space = (capacity − length) × payload widthConcrete example, with assumptions
On one common 64-bit C ABI, a struct containing a 4-byte integer and an 8-byte pointer may occupy 16 bytes after alignment. One million nodes would therefore use about 16 MB for the structs alone, before allocator overhead. A packed array of the same integers needs about 4 MB, plus any unused capacity.
Measure the actual build and allocator; do not promote this example to a language-wide guarantee.
Pointers, references, and indices
The link representation changes who manages lifetime and whether an address is observable. The abstract operation remains the same: resolve a link to find the next node.
C++ pointer
struct Node {
int value;
Node* next; // raw pointer: non-owning unless documented
};
Node* node_at(Node* head, std::size_t index) {
Node* current = head;
while (current != nullptr && index > 0) {
current = current->next; // next address depends on this load
--index;
}
return current; // nullptr means out of range
}A raw pointer does not say whether it owns the node. A production design needs an explicit owner, destruction policy, and mutation contract.
Java reference
final class LinkedNodes {
static final class Node<T> {
final T value;
Node<T> next; // managed reference, not a stable raw address
Node(T value) { this.value = value; }
}
static <T> Node<T> nodeAt(Node<T> head, int index) {
if (index < 0) throw new IndexOutOfBoundsException("negative index");
Node<T> current = head;
while (current != null && index-- > 0) {
current = current.next;
}
return current;
}
}Garbage collection reclaims unreachable nodes eventually; it does not make every reference valid or eliminate retained-memory leaks.
C++ pool index
struct Node {
int value;
std::uint32_t next; // index into a contiguous pool
};
constexpr std::uint32_t none = UINT32_MAX;
std::vector<Node> pool;
std::uint32_t node_at(std::uint32_t current, std::size_t index) {
while (current != none && index-- > 0)
current = pool[current].next;
return current;
}Indices can be narrower than machine pointers, serialize cleanly, and keep nodes dense. They require stable slot identities or a remapping strategy when the pool compacts.
Java pool index
import java.util.ArrayList;
import java.util.List;
final class IndexedNodePool {
static final int NONE = -1;
static final class Node {
final int value;
final int next; // index into a contiguous pool
Node(int value, int next) {
this.value = value;
this.next = next;
}
}
private final List<Node> pool = new ArrayList<>();
int nodeAt(int current, int index) {
if (index < 0) throw new IndexOutOfBoundsException("negative index");
while (current != NONE && index-- > 0) {
current = pool.get(current).next;
}
return current;
}
}The Java version uses −1 as the absent index. The pool owns nodes densely while links remain stable integer slot identifiers.
Allocation, release, and fragmentation
A list avoids asking for one n-node contiguous block, but “linked lists have no fragmentation problem” is false. Many small allocations can create their own overhead and fragmentation behavior.
Allocate
The allocator chooses a size class or block. This can involve free lists, synchronization, page growth, or a GC allocation region.
Initialize
Construct the payload and establish links without exposing a half-built node to readers or exception paths.
Unlink
Repair neighboring links first. Unlinking changes reachability; it does not necessarily release storage immediately.
Reclaim
Manual code destroys or returns the node. Managed runtimes reclaim it after it becomes unreachable and the collector runs.
External fragmentation
Free space exists in separate holes, but not as one sufficiently large block. Independent nodes tolerate scattered holes better than one large array allocation; they can also help create a fragmented heap.
Internal fragmentation
A node may consume an allocator slot larger than its requested size. Alignment and size-class rounding leave bytes inside the reserved block unused.
Temporal behavior
Allocation and collection costs can be bursty. Tail latency, allocator contention, and GC pauses matter even when the algorithmic allocation count is O(1) per insertion.
Why pointer chasing can be slow
Big-O says both an array scan and a list scan visit Θ(n) values. Hardware can still execute them very differently. Avoid assigning a universal cycle count: the result depends on layout, data size, CPU, runtime, allocator, and workload.
Cache locality
An array packs adjacent values, so one cache-line transfer often brings future loop inputs. Separate list nodes may waste most transferred bytes or evict useful data. A pool can improve this substantially.
Dependent loads
To fetch node k+1, the processor first needs the next field from node k. That serial dependency limits how far ordinary memory-level parallelism can look ahead.
Prefetching
Regular strides are easy for hardware prefetchers to recognize. Address sequences encoded in data are harder, although software prefetching or batched traversal can help in specialized workloads.
TLB and page pressure
Scattered nodes can touch more virtual-memory pages. That increases translation working-set pressure and may produce more TLB misses than a dense representation.
Branches
Traversal tests for null and often runs payload-dependent logic. The loop-exit branch alone may be predictable; irregular filtering or mutation can add less predictable branches.
Payload size matters
When payload processing dominates, link overhead may be minor. When nodes hold only a tiny scalar, references, padding, and memory stalls can dominate the useful work.
Complexity needs its preconditions
“Linked-list insertion is O(1)” means the insertion point is already known and a node is available or allocation is treated separately. Searching for the position first is still linear.
| Question | Dynamic array | Singly linked list |
|---|---|---|
| Locate element i | Address = base + i × width: Θ(1) | Follow i links and inspect node i: Θ(i + 1), worst Θ(n) |
| Sequential scan | Θ(n), usually strong spatial locality | Θ(n), dependent pointer chasing; locality varies |
| Insert at known index i | Shift the suffix: Θ(n − i); best Θ(1), worst Θ(n) | Relink fields: Θ(1) once the predecessor handle is known |
| Find the insertion position | Depends on the search strategy | Often Θ(n); relinking does not erase search cost |
| Memory per element | Payload plus spare capacity | Payload, links, padding, headers, and allocation overhead |
| Growth | Occasional allocation and Θ(n) copy/move | Typically one node allocation; allocator cost is not free |
| Address stability | Growth can relocate the whole buffer | A node often stays put, unless a moving runtime relocates it |
| Contiguous allocation | Required per backing buffer | Not required across independently allocated nodes |
Layout strategies that change the trade-offs
A “linked list” describes connectivity, not one mandatory allocator strategy. Keeping the interface while changing node placement can recover locality and reduce allocation overhead.
Object pool / slab
Reusable, similarly sized nodesGain: Allocates many nodes from dense chunks, amortizes metadata, and makes allocate/free operations predictable.
Cost: Needs a free-list policy, capacity management, and protection against stale handles.
Arena / region
Nodes sharing one lifetimeGain: Bump allocation is cheap and nodes are often close together; the whole region is reclaimed at once.
Cost: Individual deletion usually does not return space, and long-lived outliers can retain an entire arena.
Index-based list
Compact pools, persistence, and serializationGain: Links are integer indices or offsets, which can be smaller and remain meaningful after the backing buffer moves.
Cost: Requires bounds/generation checks and a plan for slot reuse or compaction.
Intrusive list
Systems with explicit ownership and no per-node wrapperGain: Stores link fields inside an existing object, avoiding a separate allocation for the list node.
Cost: Couples the object to list membership and makes ownership, multiple-list membership, and unlinking more delicate.
Ownership and lifetime hazards
Links encode reachability, not necessarily ownership. State the ownership model before implementing mutation, especially in manual-memory or concurrent code.
Dangling reference / use-after-free
A link or iterator still names a node whose storage has been reclaimed or reused.
Leak or retained chain
A node is never reclaimed, or an unintended root keeps an otherwise dead suffix reachable.
Double deletion
Two code paths both believe they own the same node and each attempts to destroy it.
Lost sublist
Overwriting a link before saving its old value can make the remainder of the chain unreachable.
Cycles
Reference counting alone cannot reclaim a cycle; traversal without detection can also loop forever.
Concurrent reclamation
Another thread can unlink and free a node while a reader still holds it; locks, epochs, hazards, or another scheme are required.
Safe mutation order: remove the node after prev
- 1. Preserve. Store
victim = prev.nextand validate that it exists. - 2. Relink. Set
prev.next = victim.next; update tail or size metadata if required. - 3. Reclaim. Destroy, return to a pool, or let reachability-based GC handle the now-unlinked node.
Questions before you commit
Use this before choosing a node-per-allocation list merely because insertion appears cheap.
Access pattern
Do you mostly scan, index by position, splice at known nodes, or search before every update?
Scale and payload
How many nodes exist, and how large is useful payload compared with references and headers?
Placement
Are nodes individually allocated, pooled, arena-backed, intrusive, or represented by indices?
Lifetime
Who owns each node? Can links form cycles? When and by whom is storage reclaimed?
Mutation contract
Which references or iterators survive insertion, unlinking, relocation, and concurrent access?
Performance target
Is throughput, memory footprint, latency variance, address stability, or implementation simplicity most important?
Runtime reality
Does the language use raw pointers, opaque references, compressed references, reference counting, or a moving GC?
Evidence
Can you measure actual node size, allocation count, cache behavior, and end-to-end workload time?
Simple rule of thumb
Arrays pay for contiguous capacity to gain arithmetic indexing and dense traversal. A conventional linked list pays per-node links, allocation, and dependent traversal to gain cheap relinking at a position already in hand. Pools, arenas, and index links let you move between those extremes. So reason about the concrete representation, not just the data-structure name.
Exercises
- Nodes A, B, C sit at addresses that are not increasing. Draw both the and one physical placement. Which diagram does a full scan follow?
- Estimate bytes per node for a 4-byte payload plus one 8-byte link, then add a plausible object header and padding. How does that change the density gap versus a packed array of ints?
- Two heads share a suffix. After unlinking through head1, what mistake can free a node still reachable from head2?
Primary sources
- Hennessy & Patterson, Computer Architecture: caches, locality, and the cost of irregular accesses.
- Drepper, “What Every Programmer Should Know About Memory” (pointer chasing and prefetch limits).
- Language ABI / runtime docs for object headers and compressed references (HotSpot, Go, etc.).
Takeaway
Logical order is a chain of references; physical placement decides the constants. Choose pools, arenas, or arrays when those constants dominate the story Big-O tells.