정점별 목록
유향 간선 A→B와 A→C가 있다면 A의 목록에 B와 C를 넣을 수 있다. 정점 B,C에 나가는 간선이 없어도 정점 정보는 유지해야 한다. 간선이 없는 정점을 빠뜨리지 않는다.
무향 간선의 저장
무향 간선 A—B는 A의 목록에 B를, B의 목록에 A를 넣는 방식으로 표현하는 경우가 많다. 한 간선이 두 목록에 기록되므로 저장 항목 수를 셀 때 그래프의 실제 간선 수와 구별한다.
공간과 조회
희소 그래프에서는 모든 정점 쌍을 저장하는 행렬보다 공간을 절약할 수 있다. 다만 단순 목록에서 특정 간선의 존재를 확인하려면 해당 정점의 이웃들을 살펴야 할 수 있다. 저장 공간과 개별 조회 비용은 별도로 비교한다.
목록이라는 이름
반드시 연결 리스트만 사용해야 하는 것은 아니다. 동적 배열이나 집합 등으로 이웃을 저장할 수도 있다. 구체적인 자료 구조에 따라 삽입과 조회, 순회 비용이 달라진다.
관련 문서
인접 행렬 / 유향 그래프 / 무향 그래프 / 연결 리스트 / 동적 배열 / 그래프 (자료 구조) / 정점 (그래프 이론)