Преимущества использования списка смежности для представления графа:

• Эффективное использование памяти. 1 Список смежности требует O(V + E) памяти, где V — количество вершин, E — количество рёбер, что делает его более подходящим для разреженных графов. 1
• Лёгкость обхода. 1 Список смежности удобен для выполнения операций обхода графа (например, поиск в ширину или в глубину). 1

Недостатки использования списка смежности для представления графа:

• Более сложный доступ. 1 Проверка наличия ребра между двумя вершинами требует O(k) времени, где k — количество соседей вершины. 1
• Менее очевидная структура. 1 Список смежности более сложен в реализации и понимании по сравнению с матрицей смежности. 1
• Количество вершин графа должно быть известно заранее. 2
• Для взвешенных графов приходится хранить список, элементы которого должны содержать два значащих поля, что усложняет код. 2