Reprezentacja przez listę sąsiedztwa Zapamiętanie tablicy o rozmiarze jest dość kosztowne, zwłaszcza gdy bada się grafy rzadkie, tj. grafy o niewielkiej liczbie krawędzi w stosunku do grafu pełnego złożonego z tej samej liczby wierzchołków. W praktyce lista sąsiedztwa często okazuje się najefektywniejszą reprezentacją grafu.
Korzysta się z list – struktur danych, które przechowują różne wartości w komórkach zwanych węzłami. Tutaj w listach będziemy trzymać numery indeksów.
Tworzy się tablicę o rozmiarze równym liczbie wierzchołków, zawierającą wskaźniki na (początkowo puste) listy – kolejne elementy list oznaczać będą kolejnych sąsiadów danego wierzchołka, do którego lista jest przyporządkowana. Niech tablica nazywa się
Dla każdej krawędzi do listy wskazywanej przez dodaje się indeks wierzchołka
wskazuje teraz na listę zawierającą indeksy wszystkich sąsiadów wierzchołka
Aby usunąć krawędź wystarczy usunąć z listy indeks a z indeks
W przypadku grafów skierowanych stosuje się listy następników lub listy poprzedników – odpowiednio w tym wypadku zamiast dodawać sąsiadów, dodajemy do listy związanej z danym wierzchołkiem informacje o wierzchołkach, do których krawędź „wychodzi” lub z których krawędź „wchodzi” z tego, danego wierzchołka.