隣接リスト
隣接リストの代替としては隣接行列がある。疎らな隣接行列となるグラフの場合、隣接リストの方がメモリを無駄にしない。これは、隣接リストの方が存在しない辺を表すメモリ領域を全く必要としないためである。32ビットのコンピュータ上で単純な配列による隣接リスト実装をすると、無向グラフでは8eバイトのメモリを必要とする。ここで、eは辺の数で、隣接リストでは辺が1つあると2箇所にそれに対応したデータが必要で、1つを4バイトと計算している。
一方、隣接行列では1カ所には1ビットで済むため、非常にコンパクトに表現でき、n/8バイトしか要しない。ここで、nは頂点の数である。無駄な領域があるとしても、このコンパクトさは参照の局所性という点で好ましい。
n個の頂点のグラフでは、辺は最大でも(ループを許容しても)nであり、ここで d = e/n をグラフの密度とする。すると 8e > n/8、すなわち隣接リストが隣接行列よりもメモリを消費するのは d > 1/64 のときである。したがって隣接リスト表現がメモリ使用量という面で正当化されるには、グラフが十分に疎らでなければならない。しかし、以上の分析はグラフの連結構造だけを表現する場合の話で、その他の数値情報を格納する場合はまた別の考察が必要である。
メモリ使用量のトレードオフとは別に、データ構造にはそれぞれ適した操作が存在する。ある頂点に隣接する頂点群を探すことは隣接リスト表現では容易であり、単にその頂点の隣接リストを見ればよい。隣接行列では、1つの行全体をスキャンする必要があり、O(n) の時間がかかる。2つの頂点を結ぶ辺があるかどうかを知りたい場合、隣接行列では1回の操作で済むが、隣接リストでは、リストをたどって調べる必要がある。