Adjacency List

What a waste!

An $n\times n$ matrix requires $n^2$ memory. Imagine a graph on a thousand vertices, with a handful of edges incident on each vertex. In the adjacency matrix, the row for each vertex would contain mostly zeroes except for a smattering of ones.

That’s wasteful as far as memory is concerned because if we know the neighbors of a vertex, it is easy to infer which of the vertices are not its neighbors. We don’t really need to store a zero against each nonneighbor.

For instance, the adjacency matrix for the shown graph has $64$ entries in all, but only $14$ are non-zero.