Adjacency List Representation in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an adjacency list in graph representation?

An adjacency list is a way to represent a graph where each node stores a list of its neighboring nodes. It shows which nodes are directly connected to each node.

intermediate

How does an adjacency list differ from an adjacency matrix?

An adjacency list stores neighbors only, using less space for sparse graphs. An adjacency matrix uses a 2D array to store connections, using more space but allowing faster edge checks.

beginner

Show the adjacency list for a graph with edges: (1-2), (1-3), (2-4).

1: [2, 3]
2: [1, 4]
3: [1]
4: [2]

intermediate

Why is adjacency list preferred for sparse graphs?

Because it only stores existing edges, saving memory and making it faster to iterate neighbors compared to adjacency matrix which stores all possible edges.

beginner

What data structure is commonly used to implement adjacency lists in Python?

A dictionary where keys are nodes and values are lists of neighbors is commonly used for adjacency lists in Python.

Which data structure best represents an adjacency list?

A 2D array with 0s and 1s

B Dictionary with lists of neighbors

C Single list of all edges

D Stack of nodes

An adjacency list uses a dictionary (or map) where each node points to a list of its neighbors.

What is the main advantage of adjacency list over adjacency matrix?

A Uses less memory for sparse graphs

B Faster to check if edge exists

C Simpler to implement

D Always uses fixed size

Adjacency lists save memory by storing only existing edges, which is efficient for sparse graphs.

In an undirected graph, if node 1 is connected to node 2, how is this represented in adjacency list?

A Neither list contains the other

B Only 1's list contains 2

C 1's list contains 2 and 2's list contains 1

D Only 2's list contains 1

In undirected graphs, edges are stored in both nodes' adjacency lists.

What is the time complexity to find all neighbors of a node in adjacency list?

A O(number of edges squared)

B O(number of nodes)

C O(1)

D O(number of neighbors)

Neighbors are stored in a list, so accessing all neighbors takes time proportional to their count.

Which graph type benefits most from adjacency list representation?

A Sparse graphs

B Complete graphs

C Graphs with no edges

D Graphs with equal edges and nodes

Sparse graphs have fewer edges, so adjacency lists save space by storing only existing edges.

Explain how to represent a graph using an adjacency list and why it is useful.

Think about how you store friends for each person in a group.

Describe the difference between adjacency list and adjacency matrix with examples.

Compare a contact list vs a full table of connections.

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