Adjacency List vs Matrix When to Choose Which in DSA Go - 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 nearby friends for each person, adjacency matrix is like a big table showing if any two people know each other.

Adjacency List:
Node 1 -> 2 -> 4 -> null
Node 2 -> 1 -> 3 -> null
Node 3 -> 2 -> null
Node 4 -> 1 -> null

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

Dry Run Walkthrough

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

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

Step 1: Create adjacency list for each node with its neighbors

Node 1 -> 2 -> 4 -> null
Node 2 -> 1 -> 3 -> null
Node 3 -> 2 -> null
Node 4 -> 1 -> null

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

Step 2: Create adjacency matrix with 4x4 grid marking edges

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

Why: Matrix stores all possible connections, easy to check if edge exists

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

Adjacency List: Node 1 neighbors are 2 and 4, no 3
Adjacency Matrix: matrix[1][3] = 0 (no edge)

Why: List requires scanning neighbors, matrix direct lookup

Step 4: Add edge 3-4 in both structures

List: Node 3 -> 2 -> 4 -> null
Node 4 -> 1 -> 3 -> null
Matrix: matrix[3][4] = 1, matrix[4][3] = 1

Why: Both structures updated to reflect new connection

Result:

Adjacency List:
Node 1 -> 2 -> 4 -> null
Node 2 -> 1 -> 3 -> null
Node 3 -> 2 -> 4 -> null
Node 4 -> 1 -> 3 -> null

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

Annotated Code

DSA Go

package main

import "fmt"

// Graph using adjacency list
type GraphList struct {
	adj map[int][]int
}

func NewGraphList() *GraphList {
	return &GraphList{adj: make(map[int][]int)}
}

func (g *GraphList) AddEdge(u, v int) {
	// add v to u's list
	g.adj[u] = append(g.adj[u], v)
	// add u to v's list (undirected)
	g.adj[v] = append(g.adj[v], u)
}

func (g *GraphList) HasEdge(u, v int) bool {
	// scan neighbors of u
	for _, nbr := range g.adj[u] {
		if nbr == v {
			return true
		}
	}
	return false
}

func (g *GraphList) String() string {
	res := ""
	for node := 1; node <= 4; node++ {
		res += fmt.Sprintf("Node %d ->", node)
		for _, nbr := range g.adj[node] {
			res += fmt.Sprintf(" %d ->", nbr)
		}
		res += " null\n"
	}
	return res
}

// Graph using adjacency matrix
type GraphMatrix struct {
	matrix [][]int
	size   int
}

func NewGraphMatrix(size int) *GraphMatrix {
	m := make([][]int, size)
	for i := range m {
		m[i] = make([]int, size)
	}
	return &GraphMatrix{matrix: m, size: size}
}

func (g *GraphMatrix) AddEdge(u, v int) {
	// mark edge in matrix (undirected)
	g.matrix[u-1][v-1] = 1
	g.matrix[v-1][u-1] = 1
}

func (g *GraphMatrix) HasEdge(u, v int) bool {
	return g.matrix[u-1][v-1] == 1
}

func (g *GraphMatrix) String() string {
	res := "    1 2 3 4\n"
	for i := 0; i < g.size; i++ {
		res += fmt.Sprintf("%d [", i+1)
		for j := 0; j < g.size; j++ {
			res += fmt.Sprintf(" %d", g.matrix[i][j])
		}
		res += " ]\n"
	}
	return res
}

func main() {
	// Create graph with edges 1-2, 1-4, 2-3
	gl := NewGraphList()
	gl.AddEdge(1, 2)
	gl.AddEdge(1, 4)
	gl.AddEdge(2, 3)

	gm := NewGraphMatrix(4)
	gm.AddEdge(1, 2)
	gm.AddEdge(1, 4)
	gm.AddEdge(2, 3)

	// Check edge 1-3
	fmt.Printf("Edge 1-3 in list? %v\n", gl.HasEdge(1, 3))
	fmt.Printf("Edge 1-3 in matrix? %v\n", gm.HasEdge(1, 3))

	// Add edge 3-4
	gl.AddEdge(3, 4)
	gm.AddEdge(3, 4)

	// Print final graphs
	fmt.Println("Adjacency List:")
	fmt.Print(gl.String())
	fmt.Println("Adjacency Matrix:")
	fmt.Print(gm.String())
}

g.adj[u] = append(g.adj[u], v) // add neighbor v to node u's adjacency list

add neighbor v to node u's adjacency list

g.adj[v] = append(g.adj[v], u) // add u to v's list (undirected)

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

for _, nbr := range g.adj[u] { if nbr == v { return true } }

scan neighbors of u to check if v is connected

g.matrix[u-1][v-1] = 1 // mark edge in matrix (undirected)

set matrix cell to 1 to mark edge from u to v

g.matrix[v-1][u-1] = 1 // mark edge in matrix (undirected)

set matrix cell to 1 to mark edge from v to u

return g.matrix[u-1][v-1] == 1

directly check if edge exists in matrix

Output

Edge 1-3 in list? false

Edge 1-3 in matrix? false

Adjacency List:

Node 1 -> 2 -> 4 -> null

Node 2 -> 1 -> 3 -> null

Node 3 -> 2 -> 4 -> null

Node 4 -> 1 -> 3 -> null

Adjacency Matrix:

    1 2 3 4

1 [ 0 1 0 1 ]

2 [ 1 0 1 0 ]

3 [ 0 1 0 1 ]

4 [ 1 0 1 0 ]

Complexity Analysis

Time: O(V + E) for adjacency list to check neighbors because it scans neighbors; O(1) for adjacency matrix lookup because it directly indexes the grid

Space: O(V + E) for adjacency list because it stores only existing edges; O(V^2) for adjacency matrix because it stores all possible edges even if missing

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

Edge Cases

Empty graph with no edges

Adjacency list stores empty neighbor lists; adjacency matrix is all zeros

DSA Go

for _, nbr := range g.adj[u] { if nbr == v { return true } }

Graph with single node and no edges

Adjacency list has one empty list; matrix is 1x1 with zero

DSA Go

for _, nbr := range g.adj[u] { if nbr == v { return true } }

Graph with duplicate edges added

Adjacency list may have repeated neighbors; matrix remains 1 for edge presence

DSA Go

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

When to Use This Pattern

When you need to represent a graph and decide between saving space or fast edge checks, choose adjacency list for sparse graphs and adjacency matrix for dense graphs or quick lookups.

Common Mistakes

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

Mistake: Checking edge existence in adjacency list without scanning neighbors
Fix: Always scan the neighbor list to confirm if edge exists

Summary

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

Use adjacency list for graphs with few edges and adjacency matrix for dense graphs or fast edge queries.

Adjacency list saves space by storing only real edges; adjacency matrix allows instant edge checks by indexing.

Practice

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

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 nodes is called a sparse graph.

2. Step 2: Choose data structure for sparse graphs

   Adjacency lists store 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 graph? Use adjacency list 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 declare an adjacency matrix for a graph with 4 nodes in Go?

easy

A. var graph [4][4]int

B. graph := make([][]int, 4)

C. var graph []int

D. graph := map[int][]int{}

Solution

1. Step 1: Understand adjacency matrix declaration

   An adjacency matrix is a 2D fixed-size array representing edges between nodes.

2. Step 2: Check Go syntax for fixed 2D array

   "var graph [4][4]int" declares a 4x4 integer matrix correctly.

3. Final Answer:

   var graph [4][4]int -> Option A

4. Quick Check:

   Fixed 2D array = var graph [4][4]int [OK]

Hint: Adjacency matrix = fixed 2D array declaration [OK]

Common Mistakes:

• Using slice of slices without initialization for matrix
• Declaring 1D slice instead of 2D array
• Using map which is adjacency list style

3. Given the following Go code using an adjacency list, what will be printed?

graph := map[int][]int{
  0: {1, 2},
  1: {2},
  2: {0},
  3: {},
}
fmt.Println(graph[1])

medium

A. [0 2]

B. [2]

C. [1 2]

D. []

Solution

1. Step 1: Identify adjacency list entries for node 1

   Node 1 has edges to node 2 only, so graph[1] = {2}.

2. Step 2: Understand fmt.Println output

   Printing graph[1] outputs the slice [2].

3. Final Answer:

   [2] -> Option B

4. Quick Check:

   graph[1] = [2] [OK]

Hint: Print adjacency list for node key directly [OK]

Common Mistakes:

• Confusing keys and values in map
• Assuming node 1 connects to node 0
• Expecting adjacency matrix output

4. The following Go code attempts to create an adjacency matrix but has a bug. What is the bug?

graph := make([][]int, 3)
for i := range graph {
  graph[i] = make([]int, 3)
}
graph[0][1] = 1
graph[1][2] = 1
fmt.Println(graph[0][2])

medium

A. The matrix is not initialized properly

B. graph[0][2] should be 1 but prints 0

C. Index out of range error

D. No bug, code runs correctly

Solution

1. Step 1: Check matrix initialization

   Each row is initialized with make([]int, 3), so matrix is properly created.

2. Step 2: Check assigned values and print

   graph[0][1] and graph[1][2] are set to 1; graph[0][2] was never set, so prints 0.

3. Step 3: Verify no runtime errors

   All indices are within range; no errors occur.

4. Final Answer:

   No bug, code runs correctly -> Option D

5. Quick Check:

   Proper initialization and indexing = No bug [OK]

Hint: Check initialization and index ranges carefully [OK]

Common Mistakes:

• Assuming unassigned entries print 1
• Thinking initialization is missing
• Expecting index errors without out-of-range access

5. You need to represent a dense graph with 1000 nodes where you frequently check if an edge exists between any two nodes. Which data structure is best and why? A) Adjacency Matrix for constant-time edge checks B) Adjacency List for memory efficiency C) Edge List for simple iteration D) Map of maps for flexible keys

hard

A. Edge List for simple iteration

B. Adjacency List for memory efficiency

C. Adjacency Matrix for constant-time edge checks

D. Map of maps for flexible keys

Solution

1. Step 1: Understand graph density and operations

   A dense graph has many edges, close to the maximum possible.

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

   Adjacency matrix allows O(1) time to check if edge exists between any two nodes.

3. Step 3: Consider memory tradeoff

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

4. Final Answer:

   Adjacency Matrix for constant-time edge checks -> Option C

5. Quick Check:

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

Hint: Dense graph + frequent edge checks? Use adjacency matrix [OK]

Common Mistakes:

• Choosing adjacency list for dense graphs slows edge checks
• Ignoring memory vs speed tradeoff
• Confusing edge list with adjacency matrix