Adjacency List Representation in DSA Rust - Time & Space Complexity

Time Complexity: Adjacency List Representation

O(V + E)

Understanding Time Complexity

We want to understand how fast we can build and use an adjacency list for a graph.

How does the time needed change when the graph grows bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn add_edge(adj_list: &mut Vec<Vec<usize>>, u: usize, v: usize) {
    adj_list[u].push(v);
    adj_list[v].push(u); // for undirected graph
}

fn build_graph(edges: &[(usize, usize)], n: usize) -> Vec<Vec<usize>> {
    let mut adj_list = vec![Vec::new(); n];
    for &(u, v) in edges {
        add_edge(&mut adj_list, u, v);
    }
    adj_list
}
    

This code builds an adjacency list for an undirected graph with n nodes and a list of edges.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through all edges to add connections.
• How many times: Once for each edge in the graph.

How Execution Grows With Input

Each edge causes two insertions in the adjacency list. So the work grows with the number of edges.

Input Size (n edges)	Approx. Operations
10	20 insertions
100	200 insertions
1000	2000 insertions

Pattern observation: Operations grow linearly with the number of edges.

Final Time Complexity

Time Complexity: O(V + E)

This means the time grows with the number of nodes plus the number of edges in the graph.

Common Mistake

[X] Wrong: "Adding edges takes O(V²) time because we have to check all nodes."

[OK] Correct: We directly add edges to the list for each node without scanning all nodes, so it depends on edges, not nodes squared.

Interview Connect

Knowing adjacency list complexity helps you explain graph storage choices clearly and shows you understand efficient graph algorithms.

Self-Check

What if the graph was directed and we only added one direction per edge? How would the time complexity change?

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 where each node stores its connected neighbors

D. A queue of nodes to visit next

Solution

1. Step 1: Understand graph representation

   An adjacency list stores each node with a list of its neighbors, showing direct connections.

2. Step 2: Compare options

   Only A list where each node stores its connected neighbors describes this correctly; others describe different structures or concepts.

3. Final Answer:

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

4. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list = node with its neighbors [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking adjacency list stores distances
• Mixing up with traversal queues

2. Which Rust data structure is best suited to represent an adjacency list for a graph with nodes labeled 0 to n-1?

easy

A. Vec

B. HashMap

C. Vec<usize>

D. HashSet<usize>

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list for nodes 0 to n-1 is a vector where each index holds a vector of neighbors.

2. Step 2: Match Rust types

   Vec matches this: outer Vec for nodes, inner Vec for neighbors. Others don't store neighbors per node properly.

3. Final Answer:

   Vec -> Option A

4. Quick Check:

   Vec of Vecs = adjacency list [OK]

Hint: Use Vec for adjacency list in Rust [OK]

Common Mistakes:

• Using HashMap with single usize value instead of list
• Using Vec<usize> which holds only one neighbor list
• Using HashSet which doesn't map nodes to neighbors

3. Given the following Rust code, what is the printed adjacency list?

let mut graph: Vec = vec![vec![], vec![], vec![]];
graph[0].push(1);
graph[1].push(2);
graph[2].push(0);
println!("{:?}", graph);

medium

A. [[0], [1], [2]]

B. [[1], [2], [0]]

C. [[], [], []]

D. [[2], [0], [1]]

Solution

1. Step 1: Trace graph initialization

   graph starts as three empty vectors: [[], [], []]

2. Step 2: Apply push operations

   graph[0].push(1) -> [[1], [], []] graph[1].push(2) -> [[1], [2], []] graph[2].push(0) -> [[1], [2], [0]]

3. Final Answer:

   [[1], [2], [0]] -> Option B

4. Quick Check:

   Push neighbors correctly = [[1], [2], [0]] [OK]

Hint: Follow push calls step-by-step [OK]

Common Mistakes:

• Mixing indices when pushing neighbors
• Assuming graph is empty after pushes
• Confusing order of neighbors

4. Identify the error in this Rust code snippet for creating an adjacency list:

let mut graph: Vec = Vec::new();
graph[0].push(1);

medium

A. Vec::new() cannot be mutable

B. usize type is incorrect for adjacency list

C. push method does not exist for Vec

D. graph is empty, so graph[0] access causes panic

Solution

1. Step 1: Analyze graph initialization

   graph is empty Vec with no elements, so graph[0] does not exist.

2. Step 2: Understand indexing error

   Accessing graph[0] causes runtime panic because index 0 is out of bounds.

3. Final Answer:

   graph is empty, so graph[0] access causes panic -> Option D

4. Quick Check:

   Empty Vec indexing = panic [OK]

Hint: Initialize Vec with size before indexing [OK]

Common Mistakes:

• Assuming Vec::new() has elements
• Confusing mutability with initialization
• Thinking push is invalid method

5. You want to represent a directed graph with 4 nodes using an adjacency list in Rust. Which code correctly initializes the graph and adds edges from node 0 to 1 and 2, and from node 2 to 3?

hard

A. let mut graph = vec![vec![], vec![], vec![], vec![]];
graph[0].push(1);
graph[0].push(2);
graph[2].push(3);

B. let mut graph = Vec::new();
graph[0].push(1);
graph[0].push(2);
graph[2].push(3);

C. let mut graph = vec![0; 4];
graph[0] = 1;
graph[0] = 2;
graph[2] = 3;

D. let mut graph = vec![vec![0]; 4];
graph[0].push(1);
graph[0].push(2);
graph[2].push(3);

Solution

1. Step 1: Check graph initialization

   let mut graph = vec![vec![], vec![], vec![], vec![]]; graph[0].push(1); graph[0].push(2); graph[2].push(3); initializes a Vec of Vecs with 4 empty vectors, ready to hold neighbors.

2. Step 2: Verify edge additions

   graph[0].push(1) and graph[0].push(2) add edges from node 0 to 1 and 2; graph[2].push(3) adds edge from 2 to 3.

3. Step 3: Identify errors in other options

   let mut graph = Vec::new(); graph[0].push(1); graph[0].push(2); graph[2].push(3);: graph is empty Vec, indexing causes panic. let mut graph = vec![0; 4]; graph[0] = 1; graph[0] = 2; graph[2] = 3;: graph is Vec<usize>, not Vec; push invalid. let mut graph = vec![vec![0]; 4]; graph[0].push(1); graph[0].push(2); graph[2].push(3);: graph initialized with vec![vec![0]; 4] means each node starts with neighbor 0, incorrect.

4. Final Answer:

   let mut graph = vec![vec![], vec![], vec![], vec![]]; graph[0].push(1); graph[0].push(2); graph[2].push(3); -> Option A

5. Quick Check:

   Vec of empty Vecs + push edges = correct [OK]

Hint: Initialize Vec with empty Vecs before pushing [OK]

Common Mistakes:

• Using empty Vec without size causes panic
• Initializing with repeated vec![0] adds wrong neighbors
• Using Vec<usize> instead of Vec