Adjacency List Representation in DSA Python

Mental Model

We store each node's neighbors in a list so we can quickly see who it connects to.

Analogy: Imagine a group of friends where each person keeps a list of their close friends' names. To find who someone knows, you just look at their list.

0 -> [1, 2]
1 -> [0, 3]
2 -> [0]
3 -> [1]

Dry Run Walkthrough

Input: Graph with edges: 0-1, 0-2, 1-3

Goal: Build an adjacency list showing neighbors for each node

Step 1: Add edge 0-1 by adding 1 to 0's list and 0 to 1's list

0 -> [1]
1 -> [0]
2 -> []
3 -> []

Why: We record that 0 and 1 are connected both ways

Step 2: Add edge 0-2 by adding 2 to 0's list and 0 to 2's list

0 -> [1, 2]
1 -> [0]
2 -> [0]
3 -> []

Why: We record that 0 and 2 are connected both ways

Step 3: Add edge 1-3 by adding 3 to 1's list and 1 to 3's list

0 -> [1, 2]
1 -> [0, 3]
2 -> [0]
3 -> [1]

Why: We record that 1 and 3 are connected both ways

Result:

0 -> [1, 2]
1 -> [0, 3]
2 -> [0]
3 -> [1]

Annotated Code

DSA Python

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj_list = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.adj_list[u].append(v)  # add v to u's list
        self.adj_list[v].append(u)  # add u to v's list for undirected graph

    def print_graph(self):
        for i in range(self.V):
            neighbors = ', '.join(str(x) for x in self.adj_list[i])
            print(f"{i} -> [{neighbors}]")

# Driver code
vertices = 4
edges = [(0, 1), (0, 2), (1, 3)]
graph = Graph(vertices)
for u, v in edges:
    graph.add_edge(u, v)
graph.print_graph()

self.adj_list[u].append(v) # add v to u's list

add neighbor v to node u's adjacency list

self.adj_list[v].append(u) # add u to v's list for undirected graph

add neighbor u to node v's adjacency list to keep undirected edges

for i in range(self.V):

iterate over all nodes to print their neighbors

neighbors = ', '.join(str(x) for x in self.adj_list[i])

convert adjacency list of node i to string for display

print(f"{i} -> [{neighbors}]")

print node and its neighbors in adjacency list format

Output

0 -> [1, 2]

1 -> [0, 3]

2 -> [0]

3 -> [1]

Complexity Analysis

Time: O(V + E) because we create a list for each vertex and add each edge twice

Space: O(V + E) because adjacency lists store all vertices and edges explicitly

vs Alternative: Compared to adjacency matrix which uses O(V^2) space, adjacency list is more efficient for sparse graphs

Edge Cases

Empty graph with zero vertices

No adjacency lists are created; printing shows nothing

DSA Python

self.adj_list = [[] for _ in range(vertices)]

Graph with vertices but no edges

Each vertex has an empty adjacency list

DSA Python

self.adj_list = [[] for _ in range(vertices)]

Adding duplicate edges

Duplicates appear in adjacency lists as repeated entries

DSA Python

self.adj_list[u].append(v)

When to Use This Pattern

When you need to represent a graph efficiently and quickly find neighbors, use adjacency list because it stores only existing edges.

Common Mistakes

Mistake: Forgetting to add the edge in both directions for undirected graphs
Fix: Add v to u's list and u to v's list to keep connections two-way

Summary

Stores each node's neighbors in a list for quick access.

Use when you want an efficient graph representation especially for sparse graphs.

The key is storing only existing edges, not all possible pairs.

Practice

1. What does an adjacency list represent in graph data structures?

easy

A. A list of all nodes without connections

B. A matrix showing distances between nodes

C. A list of nodes sorted by their values

D. A list where each node stores its connected neighbors

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each node with a list of nodes it connects to directly.

2. Step 2: Compare options with definition

   Only A list where each node stores its connected neighbors correctly describes this structure as neighbors stored per node.

3. Final Answer:

   A list where each node stores its connected neighbors -> Option D

4. Quick Check:

   Adjacency list = neighbors per node [OK]

Hint: Adjacency list = nodes with their direct neighbors [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking it stores distances instead of neighbors
• Assuming it lists nodes without connections

2. Which of the following is the correct Python syntax to initialize an empty adjacency list for a graph with 3 nodes?

easy

A. graph = {0: [], 1: [], 2: []}

B. graph = [[], [], []]

C. graph = {0: None, 1: None, 2: None}

D. graph = [0, 1, 2]

Solution

1. Step 1: Understand adjacency list initialization

   An adjacency list is usually a dictionary with keys as nodes and values as lists of neighbors.

2. Step 2: Check each option

   graph = {0: [], 1: [], 2: []} correctly creates a dict with empty lists for each node. graph = [[], [], []] is a list of lists but lacks node keys. graph = {0: None, 1: None, 2: None} uses None instead of lists. graph = [0, 1, 2] is just a list of nodes, not adjacency lists.

3. Final Answer:

   graph = {0: [], 1: [], 2: []} -> Option A

4. Quick Check:

   Dict with empty lists = adjacency list init [OK]

Hint: Use dict with nodes as keys and empty lists as values [OK]

Common Mistakes:

• Using None instead of empty lists for neighbors
• Using list without node keys
• Confusing adjacency list with simple node list

3. What is the output of the following code?

graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: []}
print(graph[2])

medium

A. [1, 2]

B. [0, 3]

C. [2]

D. []

Solution

1. Step 1: Identify the adjacency list for node 2

   In the dictionary, key 2 maps to the list [0, 3].

2. Step 2: Print the value for key 2

   Printing graph[2] outputs [0, 3].

3. Final Answer:

   [0, 3] -> Option B

4. Quick Check:

   graph[2] = [0, 3] [OK]

Hint: Look up the key in dict to get neighbors list [OK]

Common Mistakes:

• Confusing keys and values
• Printing wrong node's neighbors
• Misreading list contents

4. The following code tries to add an edge from node 1 to node 3 in the adjacency list but causes an error. What is the error?

graph = {0: [1], 1: [2], 2: [0]}
graph[1].append(3)
print(graph)

medium

A. KeyError because node 3 does not exist in graph

B. IndexError because list index out of range

C. No error, code runs correctly

D. TypeError because append is used on a dict

Solution

1. Step 1: Check if node 1 exists in graph

   Node 1 is a key in graph with value [2], so graph[1] is a list.

2. Step 2: Append 3 to graph[1]

   Appending 3 to the list [2] is valid and updates graph[1] to [2, 3].

3. Final Answer:

   No error, code runs correctly -> Option C

4. Quick Check:

   Appending to list in dict value works [OK]

Hint: Appending to existing list key is valid, no error [OK]

Common Mistakes:

• Thinking node 3 must exist as key before adding
• Confusing append on list vs dict
• Expecting error when adding new neighbor

5. Given a graph represented by the adjacency list:

graph = {0: [1, 2], 1: [2], 2: [0], 3: [2]}

Which node(s) have no outgoing edges?

hard

A. None, all have outgoing edges

B. Node 1

C. Node 2

D. Node 3

Solution

1. Step 1: Check neighbors list for each node

   Node 0 connects to [1, 2], node 1 to [2], node 2 to [0], node 3 to [2].

2. Step 2: Identify nodes with empty neighbor lists

   Node 3 has neighbors [2], so it has outgoing edges. No node has an empty list, so none have no outgoing edges.

3. Final Answer:

   None, all have outgoing edges -> Option A

4. Quick Check:

   All adjacency lists non-empty = no node without edges [OK]

Hint: Check for empty neighbor lists to find no outgoing edges [OK]

Common Mistakes:

• Assuming node 3 has no edges because it appears last
• Confusing incoming edges with outgoing edges
• Ignoring non-empty lists