Adjacency List
The adjacency list is a computational representation of graphs based on linked lists (or equivalent structures).
Each vertex of the graph maintains a list containing all
vertices adjacent to it.
- Vertex: main node of the structure
- Link: points from one vertex to another adjacent vertex
- Each element: vertex + list of links
This representation is especially efficient for sparse graphs and is the most commonly used in practical implementations.
Example — Directed graph and adjacency list
Adjacency list corresponding to the graph:
A → B → C → D → NULL
B → C → E → NULL
C → D → NULL
D → E → NULL
E → NULL
Each line represents a vertex and the elements to the right are the vertices reachable via an outgoing edge.
Unlike matrices, the adjacency list stores only the existing connections,
reducing memory usage.