DataTerminology.comNEW
A graph representation listing each node’s neighbors, typically stored as lists or hash maps.
DESCRIPTION
An adjacency list represents a graph by associating each vertex with a list of adjacent vertices. It is memory-efficient for sparse graphs and supports fast iteration over neighbors. Many graph libraries and databases use adjacency lists or variants under the hood. Compared to adjacency matrices, it trades constant-time edge existence checks for reduced space usage.
ALTERNATIVE DEFINITIONS
Wikipedia
In graph theory, an adjacency list is a collection of unordered lists used to represent a finite graph.
Formal definition describing the representation as a collection of lists.
NetworkX
Read graph in adjacency list format.
Library function context indicating standard adjacency list format usage.
RELATED TERMS
Graph Sparse Graph Breadth-First Search Depth-First Search Topology Degree Connected Components Graph Database
COMPETING TERMS
RELATIONS
- Broader: List
KNOWLEDGE AREAS
Data Modeling Data Storage & Operations Software Engineering
TARGET AUDIENCE
Data Engineer Software Developer Data Modeler Data Architect
EXTERNAL SOURCES
- Wikipedia - Adjacency list
- NetworkX - Graph basics and representations
- Neo4j - How graphs are stored in Neo4j
TOP QUESTIONS
When is an Adjacency List preferable to an Adjacency Matrix?
Use adjacency lists for sparse graphs where the number of edges is much smaller than V², saving memory.
Category: Comparison
How does an Adjacency List support traversal?
It enables efficient neighbor iteration for BFS and DFS by storing direct neighbor lists.
Category: How-To
What is the space complexity of an Adjacency List?
O(V + E), which is efficient for sparse graphs compared to O(V²) matrices.
Category: Concepts
How do weighted edges fit in an Adjacency List?
Store tuples or objects per neighbor including weight, direction, or attributes.
Category: Techniques
What are common pitfalls with Adjacency Lists?
Slow edge existence checks without hashing and potential duplication in undirected graphs.
Category: Mistakes
How do graph databases relate to Adjacency Lists?
They often implement pointer-based adjacency, enabling fast neighbor queries similar to adjacency list traversal.
Category: Application
Can Adjacency Lists represent multigraphs?
Yes, by allowing multiple entries per neighbor or storing edge IDs with attributes.
Category: Concepts
How do I serialize an Adjacency List?
Use formats like edge lists, adjacency list text, JSON arrays, or GraphML converters.
Category: Operations
What’s a real-world example using Adjacency Lists?
Social networks model friendships as neighbor lists for each user, supporting feed and recommendation traversals.
Category: Example