Primary Hub
Data / Knowledge library
Adjacency List
Stores each graph vertex with a collection of its neighboring edges
Why learn Adjacency List?
It represents sparse graphs with space proportional to actual connections
The problem it solves
It avoids allocating entries for every absent vertex pair
Where it came from
Adjacency List is a data structure that stores each graph vertex with a collection of its neighboring edges. Its guarantees and tradeoffs depend on the concrete implementation and operating context.
Build your understanding
Work through these exercises in order. Try the task before opening a reference.
- Define Adjacency List and distinguish it from a neighboring concept.
- Choose a realistic task where Adjacency List is appropriate.
- Identify a failure mode caused by misusing Adjacency List.
- Interpret a small design or result involving Adjacency List.
- Explain one tradeoff or limitation of Adjacency List.
Documentation and sources
- NIST Dictionary of Algorithms and Data Structures (xlinux.nist.gov)
Connect the ideas
Explore next
Real World Example
Supply Chain Logistics Network Mapping
Global logistics providers managing complex distribution centers and transport routes.
The business problem
High computational overhead when querying specific neighbor connections in massive, sparse transport networks using traditional matrix representations.
How this topic solves it
An adjacency list stores each graph vertex with a collection of its neighboring edges, allowing efficient traversal of only existing routes rather than scanning empty matrix cells.
- Define a vertex structure representing a distribution center.
- Initialize a hash map or array where each key is a vertex ID.
- Map each vertex to a linked list or dynamic array containing its direct neighbors.
- Insert edges by appending the destination vertex to the source vertex's neighbor list.
Nodes represent distribution centers, and edges represent transport routes between them.
Regional Center
Local Depot
- Warehouse A → 1:N Route → Warehouse B
- Warehouse A → 1:N Route → Warehouse C
Expected business outcome
Improved performance for route discovery and pathfinding algorithms in sparse networks.
Limitations and checks
The adjacency list structure incurs higher memory overhead for dense graphs and lacks O(1) edge existence checks, which requires scanning the neighbor list.