Adjacency List or Matrix¶
A graph representation — instantiates Operation-Weighted Data Structure Design
Stores a graph as per-vertex neighbour lists or a full vertex-by-vertex matrix, trading space for the speed of the traversal and edge-tests the workload leans on.
Adjacency List or Matrix is the representation for data whose shape is connectivity — vertices and the edges between them — offered in two dual forms. An adjacency list gives each vertex a short list of its actual neighbours; an adjacency matrix is a V×V grid holding a bit for every possible pair. Its defining question is not which fields to store but which of these two forms to commit to, and that choice is governed almost entirely by graph density and by whether the workload walks neighbours or tests specific edges. Unlike the keyed and tabular siblings, this mechanism exists to put a graph operation — neighbour expansion or edge lookup — on the cheap path.
Example¶
A routing engine for a city holds the road network as a graph: intersections are vertices, road segments are edges. The dominant operation, run millions of times inside shortest-path search, is "expand this intersection's outgoing roads," over a sparse network where each intersection connects to only ≈2–5 of hundreds of thousands of others. An adjacency list gives each intersection a short neighbour list, so expansion touches only real roads and the whole graph fits in memory at Θ(V+E). Had the team chosen a matrix, a Θ(V²) grid of almost-entirely-empty cells would blow the space budget for no gain — the engine never asks "is there a direct road between these two arbitrary intersections?", the one edge-existence test a matrix answers in O(1). Matching the representation to sparse-traversal access kept routing fast and the footprint small.
How it works¶
- Pick the dual form by density and access: lists for sparse graphs and neighbour iteration; a matrix for dense graphs or constant-time edge-existence tests.
- Lists store, per vertex, only its actual neighbours (Θ(V+E) space); a matrix stores a cell for every possible pair (Θ(V²)).
- The form fixes what is cheap: lists make "walk my neighbours" cheap; a matrix makes "is edge (u,v) present?" cheap.
What distinguishes it: the mechanism is the list-versus-matrix bargain, keyed to sparsity — not a general record store.
Tuning parameters¶
- List vs matrix — the master dial: neighbour-iteration plus space thrift (list) against O(1) edge-tests and dense-graph simplicity (matrix).
- Directedness / symmetry — store both directions or one. An undirected matrix is symmetric and can be halved; a directed list needs explicit reverse edges to support backward traversal.
- Edge payload — bare adjacency versus weights or attributes carried on each edge (a weighted matrix cell or richer list entry), buying more expressive traversal at more space.
- Neighbour ordering — keep each list sorted (faster within-list edge-test, ordered expansion) versus insertion order (cheaper mutation).
When it helps, and when it misleads¶
Its strength is that it puts exactly the graph operation the workload leans on — neighbour expansion or edge-testing — on the cheap path, and the list form keeps sparse graphs compact enough to hold entirely in memory.
Its classic failure is a dense V×V matrix for a large sparse graph, where Θ(V²) space is spent storing mostly-absent edges;[n1] the mirror-image waste is scanning a matrix row to find a handful of neighbours a list would have handed over directly. Run backwards — choosing the form you already have tooling for and asserting the workload fits it — is how a graph store ends up mismatched to its own traversal. The discipline is to size V and E and name the dominant graph operation before committing to a form.
How it implements the components¶
Adjacency List or Matrix fills the access-and-cost side of the archetype for graph-shaped data — the components a concrete representation actually sets:
access_pattern_map— it encodes which graph accesses are cheap: neighbour iteration (lists) or edge-existence (matrix).cost_tradeoff_model— list-versus-matrix is an explicit space-for-time bargain, made legible so the displaced cost is chosen rather than stumbled into.space_time_budget— density sets the footprint (Θ(V+E) versus Θ(V²)); the form is bounded by the space the graph may occupy.
It fixes no caller-facing contract — that's Abstract Data Type Interface — and it profiles none of the workload it is tuned to, which is Workload Benchmark and Trace's job.
Related¶
- Instantiates: Operation-Weighted Data Structure Design — it supplies the graph representation weighted to traversal or edge-test.
- Consumes: Workload Benchmark and Trace — the density and access profile that decides list versus matrix.
- Sibling mechanisms: Abstract Data Type Interface · Hash Table or Key-Value Store · Tree or B-Tree Index · Columnar or Row Layout · Entity-Relationship Schema · Materialized View or Cache · Normalized / Denormalized Schema Pair · Serialization Format and Codec · Schema Migration Runbook · Workload Benchmark and Trace
Editorial Notes¶
Form Classification¶
Form family: Representation, Specification & Plan
Rationale: The mechanism stores a graph as per-vertex neighbour lists or a full vertex-by-vertex matrix, trading space for the speed of the traversal and edge-tests the workload leans on, so its operative form is a static or prospective information artifact.
Independent corroboration: The frozen evidence defines Adjacency List or Matrix as 'Stores a graph as per-vertex neighbour lists or a full vertex-by-vertex matrix, trading space for the speed of the traversal and edge-tests the workload leans on', so its operative form is Representation, Specification & Plan.
Review outcome: Independent reviewer agreement; high confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Choosing adjacency lists or matrices by graph density and dominant operation is foundational data-structure and algorithms practice.
Related originating lineages:
- Mathematics — Graph theory defines the vertices, edges, and matrix representation being stored.
Review resolution: Both records exactly classify the list-versus-matrix graph representation as a specialized computer-science lineage grounded in mathematics. The ambiguity is terminological overlap with the separate mathematical adjacency-matrix template, not unresolved provenance.
Review outcome: Reconciled after independent review; high confidence.
Notes¶
[n1] For V vertices and E edges, an adjacency matrix occupies Θ(V²) space regardless of E, while adjacency lists occupy Θ(V+E). On a sparse graph (E ≪ V²) the matrix wastes space and pays off only when constant-time edge-existence tests dominate the workload — a standard textbook result. ↩