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

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

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

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