What is Adjacency List: Simple Explanation and Example

An adjacency list is a way to represent a graph by storing each node and a list of its connected neighbors. It is efficient for graphs with fewer edges and helps quickly find which nodes are directly connected.

How It Works

Imagine a group of friends where each person keeps a list of their close friends. This list shows who they can directly talk to. An adjacency list works the same way for graphs: each node (like a person) has a list of nodes it connects to (its neighbors).

This method saves space because you only store connections that actually exist, unlike other methods that store all possible connections. It’s like having a phonebook where you only write down the numbers of people you actually call.

Example

This example shows a simple graph with 3 nodes and their connections using an adjacency list in Python.

python

graph = {
    'A': ['B', 'C'],
    'B': ['A'],
    'C': ['A']
}

for node, neighbors in graph.items():
    print(f"{node}: {', '.join(neighbors)}")

Output

A: B, C
B: A
C: A

When to Use

Use an adjacency list when you have a graph with many nodes but relatively few connections. It is ideal for social networks, road maps, or any system where you want to quickly find direct links without wasting memory on non-existent connections.

For example, in a social media app, each user can have a list of friends stored as an adjacency list to efficiently find who they are connected to.

Key Points

• An adjacency list stores each node with a list of its neighbors.
• It is memory efficient for sparse graphs.
• Easy to find all direct connections of a node.
• Commonly used in graph algorithms and network representations.

Key Takeaways

An adjacency list represents a graph by listing neighbors for each node.

It uses less memory than other methods when the graph has few edges.

Ideal for quickly finding direct connections in networks.

Commonly used in social networks, maps, and graph algorithms.