= Adjacency list storage and query costs
Write $n=|V|$ and $m=|E|$. Suppose each <vertex> identifier, list descriptor, link and optional <edge> weight occupies a constant number of <machine words>, and indexed <array> access and identifier comparison take constant time. There are $n$ list descriptors and $m$ directed, or $2m$ undirected, neighbour entries. Hence <adjacency lists> use $O(n+m)$ <machine words> in <Big O notation>. A full <adjacency matrix> has $n^2$ entries, regardless of $m$. These are counts under a storage model, not fixed byte sizes.<Recitation 19: Graph Representations and Traversals (Cornell course page)>[Recitation 19, The Adjacency List and The Adjacency Matrix: directed and undirected entry totals, linear list storage, and quadratic full-matrix storage]{ref}
Our undirected example has six list descriptors and fourteen neighbour entries, versus thirty-six full <adjacency matrix> entries. The numbers $20$ and $36$ count different kinds of logical items: they do not prove a particular byte saving. A <linked list> also needs links; an <array> may have unused capacity. Storing only half of a <symmetric matrix> changes its exact count while leaving quadratic growth. If identifiers or weights require growing numbers of <machine words>, their size must be included in the <space complexity>.
\Image[/adjacency-list-matrix-query-tradeoff.png]
{title=<Adjacency matrix> storage and queries compared with <adjacency lists> on the same six-<vertex> <graph>}
An unsorted <adjacency list> answers "does the <edge> $u\to v$ exist?" by <linear search> through $\mathrm{Adj}[u]$. In the worst case it inspects all $d$ entries, giving $O(1+d)$ time, or $O(d)$ for $d\geq1$. Even if $v$ is absent, an uninspected entry could still contain it, so arbitrary lists require the whole scan. On our example, looking for $CF$ in $C$'s list compares $F$ with $A,B,D$ and fails after three comparisons. A full <adjacency matrix> instead answers from its single $C,F$ entry in $O(1)$ time.<Recitation 19: Graph Representations and Traversals (Cornell course page)>[Recitation 19, The Adjacency List: edge-membership question; The Adjacency Matrix: constant-time edge-existence query]{ref}
Different promises change the query. A <sorted array> of neighbour identifiers permits <binary search> in $O(\log(d+1))$ time, but maintaining order after insertion may require shifting entries. A per-<vertex> <hash table> permits expected constant-time membership under the hashing and load assumptions of that <data structure>; it does not give that guarantee to an arbitrary <adjacency list>. A stored list length can likewise make a <vertex degree> query constant-time even though <neighbour enumeration> still has to visit its entries.
The advantage grows with scale. For a <graph path> on $n\geq2$ <vertices>, $m=n-1$, so there are $2n-2$ undirected neighbour entries and $n$ descriptors, versus $n^2$ full <adjacency matrix> entries. Such a family is a <sparse graph> with $m=O(n)$. For a <complete graph>, $m=n(n-1)/2$, so the undirected neighbour entries already number $n(n-1)$: the <adjacency list> advantage in growth rate disappears. Choose by the workload: following existing <edges> favours <adjacency lists>; many arbitrary pair-membership queries can favour a full <adjacency matrix>. The representation organizes the same <graph> for different questions.
Back to article page
