Overview
An adjacency list provides a mechanism for representing a graph as a collection of unordered lists, one for each vertex in the graph. The main alternative to the adjacency list for graph representation is the adjacency matrix.
Concept
The adjacency list works by listing each vertex in the graph, followed by a collection of each of the edges that vertex is connected to.
Algorithmic Complexity
Big-O
| Node/Edge Management | Storage | Add Vertex | Add Edge | Remove Vertex | Remove Edge | Query |
|---|---|---|---|---|---|---|
| Adjacency List | O(|V|+|E|) | O(1) | O(1) | O(|V| + |E|) | O(|E|) | O(|V|) |
Implementation
Java Implementation
Coming soon!
References
Wikipedia: Adjacency list