Overview
An adjacency list stores outgoing or incident neighbors for each vertex. It is compact for sparse graphs and efficient for iterating over neighbors.
FoundationSource checked
Graph Adjacency List
Represents a graph by storing each node with the neighbors reachable from it.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Data Structures
- Difficulty
- Beginner
- Family
- Graph Representation
- Tier
- Foundation
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 5
- Code example
- Ready
- Visualization
- Ready
Core Concepts
neighbor listsparse graphedge directionweighted edge
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(degree)
Average
O(V + E)
Worst
O(V + E)
Space
O(V + E)
When to Use
- Use it for sparse graphs where each node has relatively few neighbors.
- Use it when algorithms need to iterate over neighbors.
- Use weighted neighbor records when edge costs are needed.
When Not to Use
- Avoid it when constant-time edge-existence checks dominate and the lists are not indexed.
- Avoid it when the graph is dense enough that a matrix is simpler.
- Avoid ambiguous direction conventions in directed graphs.
What It Does
- Stores neighbors per vertex
- Supports traversal over outgoing or incident edges
Use Cases
- Sparse graph traversal
- Shortest-path algorithms
- Network and dependency graph representation
Inputs
- Items
- Keys or indexes
- Operations to support
Outputs
- Stored structure
- Query results
- Updated state
Pseudocode
- 1.Prepare the inputs and state needed for Graph Adjacency List.
- 2.Apply the neighbor list step while the stopping condition has not been met.
- 3.Update intermediate state and discard invalid candidates.
- 4.Return stored structure.
Canonical Example
- Input
- edges = [(A, B), (A, C), (B, C)]
- Output
- {A: [B, C], B: [C], C: []} for a directed graph
- Explanation
- Each key stores the nodes reached by outgoing edges.
Implementation Notes
- Represent each neighbor as either a node id or a pair containing node id and edge data.
- For undirected graphs, update both endpoint lists together.
- Keep vertex ids and array indices clearly separated if they differ.
Common Pitfalls
- Forgetting to add both directions for undirected graphs.
- Storing weights inconsistently across neighbor records.
- Mutating neighbor lists while traversing them.
Interactive Mechanism Walkthrough
Graph Frontier & Edge RelaxationShow the structure layout and how operations move through or update it.
Step 1 of 4: Prepare the inputs and state needed for Graph Adjacency List.
data-structures-mechanismNotes
Adjacency lists are the default representation for many sparse graph algorithms.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookReference for Graph Adjacency List adjacency-list graph storage and traversal complexity.
Explore Next
Good next jumps from the relationship graph, ranked for useful discovery.
AlternativesEdge List Representation
Data Structures · Foundation
Adjacency lists organize the same graph around neighbor queries instead of edge scans.
Compare with thisAlternative toGraph Adjacency Matrix
Data Structures · Core
Adjacency lists are sparse graph representations compared with adjacency matrices.
Compare with thisRelationships
View full relationship pageUsed byBreadth-First Search
BFS commonly iterates outgoing neighbors from adjacency lists.
Alternative toGraph Adjacency Matrix
Adjacency lists are sparse graph representations compared with adjacency matrices.
Related Algorithms
Tags
Data StructureGraphGraph RepresentationTraversal