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

Mental Model

Graphs can be stored in two main ways: adjacency lists save neighbors only, adjacency matrices save all connections in a grid.

Analogy: Think of a city map: adjacency list is like a list of roads from each city to connected cities, adjacency matrix is like a big table showing if any two cities have a direct road.

Adjacency List:
City 1 -> [2, 3]
City 2 -> [1]
City 3 -> [1]

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

Dry Run Walkthrough

Input: Graph with 3 cities: 1 connected to 2 and 3, 2 connected to 1, 3 connected to 1

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

Step 1: Create adjacency list for each city

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

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

Step 2: Create adjacency matrix grid for all city pairs

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

Why: Matrix stores all possible connections, easy to check any pair

Step 3: Check if city 2 connects to city 3 using list and matrix

List: City 2 neighbors [1], no 3
Matrix: position (2,3) = 0 (no connection)

Why: Shows how adjacency list is faster for neighbors, matrix is direct for any pair

Result:

Adjacency List:
City 1 -> [2, 3]
City 2 -> [1]
City 3 -> [1]

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

Annotated Code

DSA Rust

use std::collections::HashMap;

// Graph using adjacency list
struct GraphList {
    adj_list: HashMap<usize, Vec<usize>>,
}

impl GraphList {
    fn new() -> Self {
        GraphList { adj_list: HashMap::new() }
    }

    fn add_edge(&mut self, u: usize, v: usize) {
        self.adj_list.entry(u).or_default().push(v);
        self.adj_list.entry(v).or_default().push(u);
    }

    fn neighbors(&self, u: usize) -> Vec<usize> {
        self.adj_list.get(&u).cloned().unwrap_or_default()
    }

    fn print(&self) {
        for (node, neighbors) in &self.adj_list {
            print!("City {} -> [", node);
            for (i, n) in neighbors.iter().enumerate() {
                if i > 0 { print!(", "); }
                print!("{}", n);
            }
            println!("]");
        }
    }
}

// Graph using adjacency matrix
struct GraphMatrix {
    matrix: Vec<Vec<u8>>,
    size: usize,
}

impl GraphMatrix {
    fn new(size: usize) -> Self {
        GraphMatrix {
            matrix: vec![vec![0; size]; size],
            size,
        }
    }

    fn add_edge(&mut self, u: usize, v: usize) {
        self.matrix[u - 1][v - 1] = 1;
        self.matrix[v - 1][u - 1] = 1;
    }

    fn connected(&self, u: usize, v: usize) -> bool {
        self.matrix[u - 1][v - 1] == 1
    }

    fn print(&self) {
        print!("    ");
        for i in 1..=self.size {
            print!("{} ", i);
        }
        println!();
        for i in 0..self.size {
            print!("{} [ ", i + 1);
            for j in 0..self.size {
                print!("{} ", self.matrix[i][j]);
            }
            println!("]");
        }
    }
}

fn main() {
    // Build graph with 3 cities
    let mut graph_list = GraphList::new();
    graph_list.add_edge(1, 2);
    graph_list.add_edge(1, 3);

    let mut graph_matrix = GraphMatrix::new(3);
    graph_matrix.add_edge(1, 2);
    graph_matrix.add_edge(1, 3);

    println!("Adjacency List:");
    graph_list.print();

    println!("\nAdjacency Matrix:");
    graph_matrix.print();

    // Check connection between city 2 and 3
    println!("\nCheck if city 2 connects to city 3:");
    println!("List: {:?}", graph_list.neighbors(2));
    println!("Matrix: {}", graph_matrix.connected(2, 3));
}

self.adj_list.entry(u).or_default().push(v);

Add neighbor v to u's adjacency list

self.adj_list.entry(v).or_default().push(u);

Add neighbor u to v's adjacency list for undirected graph

self.matrix[u - 1][v - 1] = 1;

Mark edge from u to v in matrix

self.matrix[v - 1][u - 1] = 1;

Mark edge from v to u in matrix for undirected graph

self.adj_list.get(&u).cloned().unwrap_or_default()

Retrieve neighbors of u or empty if none

self.matrix[u - 1][v - 1] == 1

Check if edge exists between u and v

Output

Adjacency List:

City 1 -> [2, 3]

City 2 -> [1]

City 3 -> [1]



Adjacency Matrix:

    1 2 3 

1 [ 0 1 1 ]

2 [ 1 0 0 ]

3 [ 1 0 0 ]



Check if city 2 connects to city 3:

List: [1]

Matrix: false

Complexity Analysis

Time: O(V + E) for adjacency list because we store only existing edges; O(V^2) for adjacency matrix because we store all pairs

Space: O(V + E) for adjacency list as it stores neighbors only; O(V^2) for adjacency matrix due to full grid storage

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

Edge Cases

Empty graph with no edges

Adjacency list is empty; adjacency matrix is all zeros

DSA Rust

self.adj_list.get(&u).cloned().unwrap_or_default()

Graph with single node and no edges

Adjacency list has one key with empty neighbors; matrix has one row and column with zero

DSA Rust

self.adj_list.get(&u).cloned().unwrap_or_default()

Check connection between nodes with no edge

Adjacency list returns empty or no neighbor; matrix returns 0 (false)

DSA Rust

self.matrix[u - 1][v - 1] == 1

When to Use This Pattern

When a problem involves graph representation and you need to choose storage, consider adjacency list for memory efficiency with few edges, and adjacency matrix for fast edge checks in dense graphs.

Common Mistakes

Mistake: Using adjacency matrix for very large sparse graphs causing high memory use
Fix: Switch to adjacency list to store only existing edges and save space

Mistake: Assuming adjacency list can quickly check if any two nodes are connected directly
Fix: Remember adjacency list requires searching neighbors, which can be slower than matrix lookup

Summary

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

Use adjacency list for sparse graphs and adjacency matrix for dense graphs or fast edge queries.

Adjacency list saves space by storing only existing edges; adjacency matrix allows instant edge lookup.

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 sparse.

2. Step 2: Choose data structure for sparse graphs

   Adjacency List stores only existing edges, saving space for sparse graphs.

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 Rust syntax to declare an adjacency matrix using a 2D vector for a graph with 3 vertices initialized to zero?

easy

A. let matrix = vec![vec![0; 2]; 3];

B. let matrix = [[0; 3]; 3];

C. let matrix = vec![0; 3];

D. let matrix = vec![vec![0; 3]; 3];

Solution

1. Step 1: Understand adjacency matrix structure

   It is a 2D structure with size n x n, here 3 x 3.

2. Step 2: Check Rust syntax for 2D vector initialization

   vec![vec![0; 3]; 3] creates a 3x3 matrix filled with zeros.

3. Final Answer:

   let matrix = vec![vec![0; 3]; 3]; -> Option D

4. Quick Check:

   3x3 zero matrix = vec![vec![0; 3]; 3] [OK]

Hint: Use vec![vec![value; cols]; rows] for 2D vectors [OK]

Common Mistakes:

• Using single vector for 2D matrix
• Wrong inner vector size
• Using fixed-size array without mutability

3. Given the following Rust code for an adjacency list, what will be printed?

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

medium

A. [1, 2]

B. [0, 1]

C. [0]

D. [2, 1]

Solution

1. Step 1: Understand adjacency list structure

   graph[0] contains neighbors of vertex 0, which are 1 and 2.

2. Step 2: Check printed output

   Printing graph[0] shows the vector [1, 2].

3. Final Answer:

   [1, 2] -> Option A

4. Quick Check:

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

Hint: Access adjacency list by index to get neighbors [OK]

Common Mistakes:

• Confusing indices and values
• Expecting sorted output
• Mixing adjacency matrix with list

4. Identify the error in this Rust code snippet for creating an adjacency matrix and fix it:

let mut matrix = vec![vec![0; 3]; 3];
matrix[0][1] = 1;
matrix[1][3] = 1;

medium

A. Use a 4x4 matrix instead of 3x3;

B. Index 3 is out of bounds; change to matrix[1][2] = 1;

C. Change vec![0; 3] to vec![0; 4];

D. No error; code runs fine

Solution

1. Step 1: Check matrix size and indices

   Matrix is 3x3, valid indices are 0,1,2 for both rows and columns.

2. Step 2: Identify invalid index usage

   matrix[1][3] accesses column 3 which is out of bounds.

3. Step 3: Fix the index

   Change matrix[1][3] to matrix[1][2] to stay within bounds.

4. Final Answer:

   Index 3 is out of bounds; change to matrix[1][2] = 1; -> Option B

5. Quick Check:

   3x3 matrix max index = 2 [OK]

Hint: Indices start at 0; max index = size-1 [OK]

Common Mistakes:

• Using index equal to size (out of bounds)
• Assuming 1-based indexing
• Ignoring Rust's strict bounds checking

5. You need to represent a dense graph with 1000 vertices where you frequently check if an edge exists between any two vertices. Which representation is best and why?

hard

A. Edge List, because it is fastest for dense graphs

B. Adjacency List, because it uses less memory for dense graphs

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

D. Adjacency Matrix, because it uses less memory for sparse graphs

Solution

1. Step 1: Analyze graph density and operations

   Dense graph means many edges, close to maximum possible.

2. Step 2: Choose data structure for fast edge checks

   Adjacency matrix allows O(1) time to check if edge exists by direct index access.

3. Step 3: Consider memory tradeoff

   Though adjacency matrix uses more memory, for dense graphs this is acceptable and efficient.

4. Final Answer:

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

5. Quick Check:

   Dense graph + fast edge check = Adjacency Matrix [OK]

Hint: Dense graphs + frequent edge checks = adjacency matrix [OK]

Common Mistakes:

• Choosing adjacency list for dense graphs wastes time
• Confusing edge list speed with adjacency matrix
• Incorrectly thinking adjacency matrix saves memory for sparse graphs