Adjacency List vs Matrix When to Choose Which in DSA Python - Trade-offs & Analysis

Mental Model

Graphs can be stored in two main ways: adjacency lists save space by listing neighbors only, adjacency matrices use a grid to show all connections.

Analogy: Think of a city map: adjacency list is like a list of roads from each city to others, adjacency matrix is like a big table showing if a direct road exists between every pair of cities.

Adjacency List:
0: 1 -> 2 -> null
1: 0 -> 3 -> null
2: 0 -> null
3: 1 -> null

Adjacency Matrix:
   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 0]
3 [0 1 0 0]

Dry Run Walkthrough

Input: Graph with 4 nodes and edges: 0-1, 0-2, 1-3

Goal: Show how adjacency list and matrix represent the graph and when each is better

Step 1: Create adjacency list by adding neighbors for each node

0: 1 -> 2 -> null
1: 0 -> 3 -> null
2: 0 -> null
3: 1 -> null

Why: Lists only store actual neighbors, saving space for sparse graphs

Step 2: Create adjacency matrix with 4x4 grid, mark 1 where edge exists

   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 0]
3 [0 1 0 0]

Why: Matrix shows all possible connections, easy to check if edge exists in O(1)

Step 3: Check if edge exists between 0 and 3 using list and matrix

List: 0's neighbors are 1 and 2, no 3
Matrix: cell (0,3) is 0
No edge found

Why: List requires scanning neighbors, matrix direct lookup

Step 4: Add edge 2-3 and update both structures

List:
2: 0 -> 3 -> null
3: 1 -> 2 -> null
Matrix:
   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 1]
3 [0 1 1 0]

Why: Both structures updated to keep graph consistent

Result:

Adjacency List:
0: 1 -> 2 -> null
1: 0 -> 3 -> null
2: 0 -> 3 -> null
3: 1 -> 2 -> null

Adjacency Matrix:
   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 1]
3 [0 1 1 0]

Annotated Code

DSA Python

class GraphAdjList:
    def __init__(self, n):
        self.n = n
        self.adj = [[] for _ in range(n)]

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

    def __str__(self):
        result = []
        for i in range(self.n):
            neighbors = ' -> '.join(str(x) for x in self.adj[i]) + ' -> null'
            result.append(f'{i}: {neighbors}')
        return '\n'.join(result)

class GraphAdjMatrix:
    def __init__(self, n):
        self.n = n
        self.matrix = [[0]*n for _ in range(n)]

    def add_edge(self, u, v):
        self.matrix[u][v] = 1  # mark edge u-v
        self.matrix[v][u] = 1  # mark edge v-u (undirected)

    def __str__(self):
        header = '   ' + ' '.join(str(i) for i in range(self.n))
        rows = []
        for i in range(self.n):
            row = ' '.join(str(x) for x in self.matrix[i])
            rows.append(f'{i} [{row}]')
        return header + '\n' + '\n'.join(rows)

# Driver code
n = 4
edges = [(0,1),(0,2),(1,3)]

# Create adjacency list graph
graph_list = GraphAdjList(n)
for u,v in edges:
    graph_list.add_edge(u,v)

print('Adjacency List:')
print(graph_list)

# Create adjacency matrix graph
graph_matrix = GraphAdjMatrix(n)
for u,v in edges:
    graph_matrix.add_edge(u,v)

print('\nAdjacency Matrix:')
print(graph_matrix)

# Add edge 2-3
graph_list.add_edge(2,3)
graph_matrix.add_edge(2,3)

print('\nAfter adding edge 2-3:')
print('Adjacency List:')
print(graph_list)
print('\nAdjacency Matrix:')
print(graph_matrix)

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

add neighbor v to node u's adjacency list

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

add neighbor u to node v's adjacency list for undirected graph

self.matrix[u][v] = 1 # mark edge u-v

mark presence of edge from u to v in matrix

self.matrix[v][u] = 1 # mark edge v-u (undirected)

mark presence of edge from v to u in matrix for undirected graph

Output

Adjacency List:

0: 1 -> 2 -> null

1: 0 -> 3 -> null

2: 0 -> null

3: 1 -> null



Adjacency Matrix:

   0 1 2 3

0 [0 1 1 0]

1 [1 0 0 1]

2 [1 0 0 0]

3 [0 1 0 0]



After adding edge 2-3:

Adjacency List:

0: 1 -> 2 -> null

1: 0 -> 3 -> null

2: 0 -> 3 -> null

3: 1 -> 2 -> null



Adjacency Matrix:

   0 1 2 3

0 [0 1 1 0]

1 [1 0 0 1]

2 [1 0 0 1]

3 [0 1 1 0]

Complexity Analysis

Time: O(1) to add an edge in adjacency matrix, O(1) amortized in adjacency list; O(n) to check edge in list, O(1) in matrix

Space: O(n^2) for adjacency matrix because it stores all possible edges, O(n + e) for adjacency list storing only actual edges

vs Alternative: Adjacency list is better for sparse graphs with fewer edges, adjacency matrix is better for dense graphs or when quick edge checks are needed

Edge Cases

Empty graph with no edges

Adjacency list has empty lists, matrix is all zeros

DSA Python

self.adj = [[] for _ in range(n)]

Graph with one node and no edges

List has one empty list, matrix is 1x1 zero

DSA Python

self.adj = [[] for _ in range(n)]

Adding duplicate edges

Adjacency list will have duplicates, matrix remains 1 at edge cell

DSA Python

self.adj[u].append(v)

When to Use This Pattern

When a problem involves graph representation and you need to choose storage, think adjacency list for space efficiency with sparse graphs and adjacency matrix for fast edge lookup in dense graphs.

Common Mistakes

Mistake: Using adjacency matrix for very large sparse graphs causing memory issues
Fix: Use adjacency list to save space by storing only existing edges

Mistake: Assuming adjacency list lookup for edge existence is O(1)
Fix: Remember adjacency list lookup is O(k) where k is neighbors count; use matrix if constant time needed

Summary

Stores graph connections either as lists of neighbors or a full grid of edges.

Use adjacency list for sparse graphs to save space, adjacency matrix for dense graphs or fast edge checks.

Adjacency list saves space by storing only actual edges, adjacency matrix uses fixed space but allows quick edge queries.

Practice

1. Which data structure is generally better for representing a graph with very few edges compared to the number of vertices?

easy

A. Adjacency List

B. Adjacency Matrix

C. Edge List

D. Incidence Matrix

Solution

1. Step 1: Understand graph density

   A graph with very few edges compared to vertices is called a sparse graph.

2. Step 2: Choose efficient representation for sparse graphs

   Adjacency lists store only existing edges, saving space for sparse graphs, unlike adjacency matrices which use space for all possible edges.

3. Final Answer:

   Adjacency List -> Option A

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graphs use adjacency lists for space efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes space
• Confusing edge list with adjacency matrix
• Assuming adjacency matrix is always better

2. Which of the following is the correct way to initialize an adjacency matrix for a graph with 4 vertices in Python?

easy

A. matrix = [[0 for _ in range(4)] for _ in range(4)]

B. matrix = [[0]*4]*4

C. matrix = [0]*4

D. matrix = [[None]*4 for _ in range(4)]

Solution

1. Step 1: Understand matrix initialization

   Using list comprehension with nested loops creates independent inner lists.

2. Step 2: Avoid shallow copies

   matrix = [[0]*4]*4 creates shallow copies causing all rows to reference the same list, leading to bugs.

3. Final Answer:

   matrix = [[0 for _ in range(4)] for _ in range(4)] -> Option A

4. Quick Check:

   Independent rows = matrix = [[0 for _ in range(4)] for _ in range(4)] [OK]

Hint: Use nested list comprehension for independent rows [OK]

Common Mistakes:

• Using [[0]*4]*4 causes all rows to be the same object
• Initializing with single list for matrix
• Using None instead of 0 for adjacency matrix

3. Consider the following Python code for a graph with 3 vertices using adjacency list representation:

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

What is the output?

medium

A. [1, 2]

B. []

C. [2]

D. KeyError

Solution

1. Step 1: Understand adjacency list structure

   Key 1 maps to list [2], meaning vertex 1 connects to vertex 2.

2. Step 2: Print value for key 1

   graph[1] returns [2], so print outputs [2].

3. Final Answer:

   [2] -> Option C

4. Quick Check:

   graph[1] = [2] [OK]

Hint: Access adjacency list by vertex key [OK]

Common Mistakes:

• Confusing keys and values in dictionary
• Expecting all vertices in output
• Assuming KeyError for existing key

4. The following code attempts to create an adjacency matrix for a graph with 3 vertices but has a bug:

matrix = [[0]*3]*3
matrix[0][1] = 1
print(matrix)

What is the output and what is the bug?

medium

A. IndexError; Wrong indexing

B. [[0, 1, 0], [0, 0, 0], [0, 0, 0]]; No bug

C. [[0, 0, 0], [0, 0, 0], [0, 0, 0]]; Assignment failed

D. [[0, 1, 0], [0, 1, 0], [0, 1, 0]]; Rows are shallow copies

Solution

1. Step 1: Understand matrix initialization

   Using [[0]*3]*3 creates 3 references to the same inner list.

2. Step 2: Modify one element affects all rows

   Setting matrix[0][1] = 1 changes the second element in all rows because they share the same list.

3. Final Answer:

   [[0, 1, 0], [0, 1, 0], [0, 1, 0]]; Rows are shallow copies -> Option D

4. Quick Check:

   Shallow copy rows cause all rows to change [OK]

Hint: Avoid [[0]*n]*n; use nested list comprehension [OK]

Common Mistakes:

• Assuming only first row changes
• Ignoring shallow copy behavior
• Confusing IndexError with shallow copy bug

5. You have a graph with 1000 vertices and about 10,000 edges. You need to frequently check if an edge exists between two vertices. Which representation is best and why?

hard

A. Edge List, because it is simplest to implement

B. Adjacency Matrix, because it allows O(1) edge existence checks

C. Adjacency List, because it uses less memory for sparse graphs

D. Incidence Matrix, because it stores edges explicitly

Solution

1. Step 1: Analyze graph density and operations

   Graph has 1000 vertices and 10,000 edges, which is moderately sparse but not very sparse.

2. Step 2: Consider operation speed for edge checks

   Adjacency matrix allows checking edge existence in constant time O(1), while adjacency list requires searching neighbors.

3. Step 3: Balance memory and speed

   Though adjacency matrix uses more memory, the speed benefit for frequent edge checks outweighs memory cost here.

4. Final Answer:

   Adjacency Matrix, because it allows O(1) edge existence checks -> Option B

5. Quick Check:

   Frequent edge check = Adjacency Matrix [OK]

Hint: For fast edge checks, adjacency matrix is best despite memory [OK]

Common Mistakes:

• Choosing adjacency list only for memory without considering speed
• Ignoring operation frequency in choice
• Confusing edge list with adjacency matrix for fast checks