隣接行列
しかしながら、大きな疎グラフ(英語版)では、隣接リストの方が必要とする格納空間が小さい。これは、隣接リストは存在「しない」辺を表わすためのいかなる空間も無駄にしないためである。
隣接行列の別形式(しかし、より大きな空間量を必要とする)は行列の個々の要素中の数を(辺が存在する時は)辺オブジェクトへのポインタあるいは(辺が存在しない時は)ヌルポインタで置き換える。また、辺の重みを隣接行列の要素中に直接格納することも可能である。
空間のトレードオフに加えて、異なるデータ構造は異なる操作をも容易にする。隣接リスト中の任意の頂点に隣接する全ての頂点を探すことはリストを読むのと同じぐらい単純であり、隣の数の比例した時間がかかる。隣接行列を使うと、代わりに全行をスキャンしなければならず、これはグラフ全体の中の頂点の数に比例したより長い時間がかかる。一方、任意の2つの頂点間に辺が存在するかどうかを調べるのは隣接行列を使うと瞬時に決定することができるのに対して、隣接リストを使うと2つの頂点の最小次数に比例した時間を要する。