List or Matrix? Guess Before You Look, and Watch the Answer Flip

The traversal lab walks a graph without ever saying how the graph is stored. That turns out to matter more than the traversal does, and the usual guidance — lists for sparse graphs, matrices for dense ones — is true enough to repeat and too vague to act on.

The reason it is vague is that there are two dials, not one. The winner depends on how dense the graph is and on what you keep asking it, and either dial can overturn the other.

Commit before you look

Set the density and the question mix, then predict. The counts stay hidden until you answer.

That pair is the whole article. On ten edge checks and five neighbour walks, the adjacency lists win at 20 edges and lose at 30. Nothing changed but density, and any fixed rule you were carrying got one of the two wrong.

Why each one is fast at what it is fast at

A matrix reserves a cell for every possible edge, so is there an edge between u and v is address arithmetic — one cell, immediately, regardless of the graph. The price is that the cells for edges you do not have are reserved anyway: a node’s neighbours are not stored together, they are scattered across a row of mostly-empty cells, so finding them means scanning the whole row.

Adjacency lists store only edges that exist, so a node’s neighbours are exactly what is written next to it — nothing to scan, nothing to skip. The price is the mirror image: checking one specific edge means walking that node’s neighbours looking for the other end, and that walk gets longer as the graph gets denser.

Neither is faster. Each has made the other’s cheap operation expensive.

The numbers, on both dials

V = 10


def edges_for(count):
    """Deterministic, degree-even edge set: rings at distance 1, then 2, then 3...

    Taking pairs in a fixed order keeps every density reproducible, and going ring by ring keeps
    the degrees within one of each other, so no single node distorts the averages.
    """
    pairs = []
    for step in range(1, V // 2 + 1):
        for i in range(V):
            j = (i + step) % V
            a, b = min(i, j), max(i, j)
            if (a, b) not in pairs:
                pairs.append((a, b))
    return pairs[:count]


def adjacency(count):
    adj = {i: [] for i in range(V)}
    for a, b in edges_for(count):
        adj[a].append(b)
        adj[b].append(a)
    for i in adj:
        adj[i].sort()
    return adj


def workload(edge_checks, neighbour_walks):
    """A fixed query mix. Nodes are chosen by a fixed stride so the mix is reproducible."""
    queries = []
    for n in range(edge_checks):
        queries.append(("has_edge", n % V, (n * 3 + 1) % V))
    for n in range(neighbour_walks):
        queries.append(("neighbours", (n * 7) % V, None))
    return queries


def cost(adj, queries):
    """Element touches. List: walk the neighbours. Matrix: index directly, or scan a whole row."""
    as_list = as_matrix = 0
    for kind, u, v in queries:
        if kind == "has_edge":
            row = adj[u]
            as_list += (row.index(v) + 1) if v in row else len(row)
            as_matrix += 1                 # one indexed cell, whatever the graph looks like
        else:
            as_list += len(adj[u])         # the neighbours are the list
            as_matrix += V                 # scan the whole row to find which cells are set
    return as_list, as_matrix


MIXES = [("edge checks only", 16, 0), ("mixed 10:5", 10, 5), ("neighbour walks only", 0, 16)]

print(f"{'edges':>6} {'avg degree':>11}  " + "  ".join(f"{name:>22}" for name, _, _ in MIXES))
print(f"{'':>6} {'':>11}  " + "  ".join(f"{'list / matrix   winner':>22}" for _ in MIXES))
for count in (10, 20, 30, 45):
    adj = adjacency(count)
    avg = sum(len(a) for a in adj.values()) / V
    cells = []
    for _, checks, walks in MIXES:
        lst, mat = cost(adj, workload(checks, walks))
        winner = "list" if lst < mat else ("matrix" if mat < lst else "tie")
        cells.append(f"{lst:>5} / {mat:<6} {winner:<7}")
    print(f"{count:>6} {avg:>11.1f}  " + "  ".join(f"{c:>22}" for c in cells))

print()
print(f"{'edges':>6} {'matrix cells':>13} {'list entries':>13}   memory ratio")
for count in (10, 20, 30, 45):
    matrix_cells = V * V
    list_entries = V + 2 * count        # one head per node, one entry per direction
    print(f"{count:>6} {matrix_cells:>13} {list_entries:>13}   {matrix_cells / list_entries:>4.1f}x")

 edges  avg degree        edge checks only              mixed 10:5    neighbour walks only
                    list / matrix   winner  list / matrix   winner  list / matrix   winner
    10         2.0     28 / 16     matrix      28 / 60     list        32 / 160    list   
    20         4.0     52 / 16     matrix      54 / 60     list        64 / 160    list   
    30         6.0     59 / 16     matrix      70 / 60     matrix      96 / 160    list   
    45         9.0     73 / 16     matrix      95 / 60     matrix     144 / 160    list   

 edges  matrix cells  list entries   memory ratio
    10           100            30    3.3x
    20           100            50    2.0x
    30           100            70    1.4x
    45           100           100    1.0x

Read the columns rather than the rows.

Edge checks only: the matrix wins at every density, and its cost never moves — 16 steps for 16 questions, on a graph of 10 edges or 45. Nothing you do to the graph changes indexing a cell.

Neighbour walks only: the lists win at every density, but the margin collapses. At 10 edges it is 32 against 160; at 45 it is 144 against 160. When almost every edge exists, “only the edges that exist” stops being a saving.

The mixed column is where the flip lives. List, list, matrix, matrix. This is the column no rule of thumb survives, and it is also the column that looks most like real code, because real code asks more than one kind of question.

The memory table underneath makes the same point about the argument people are surest of. Lists use a third of the matrix’s memory at 10 edges and exactly the same at 45, because a complete graph has to store every edge somewhere no matter how you write it down.

What actually decides it in practice

Real graphs are usually very sparse — a road network, a social graph, a dependency tree all have average degrees in the single digits while having millions of nodes — and a matrix is V² regardless. At a million nodes that is a trillion cells for perhaps ten million edges, which settles the question before any workload is considered.

That is why adjacency lists are the default and matrices are the special case, and it is a different reason from the one the step counts give. The step counts say it depends on your questions. Scale says the matrix may not fit at all. Both are true, and at real sizes the second one usually answers first.

What this page simplifies

• Undirected and unweighted. A directed graph halves the matrix’s redundancy; weights change what each cell or list entry has to hold.
• Unsorted neighbour lists. These are sorted for reproducibility, but a linear scan is still used. Real code that checks edges often keeps a set per node, which buys matrix-like edge checks at some memory cost — a third representation this page does not score.
• Steps, not seconds. As everywhere in this cluster, cache behaviour is not modelled, and it favours the matrix: a row is contiguous memory, a list is pointer-chasing.
• A bit matrix is much smaller than this implies. Counting cells, not bytes, hides that a matrix can pack one edge per bit — which pushes the density at which a matrix becomes attractive lower than the memory table suggests.