Adjacency List Representation in DSA Go - Time & Space Complexity

Time Complexity: Adjacency List Representation

O(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 grow as the graph gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

type Graph struct {
    adjList map[int][]int
}

func (g *Graph) AddEdge(u, v int) {
    g.adjList[u] = append(g.adjList[u], v)
    g.adjList[v] = append(g.adjList[v], u) // for undirected graph
}

This code adds an edge between two nodes in an undirected graph using an adjacency list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Appending neighbors to adjacency lists.
• How many times: Once per edge addition.

How Execution Grows With Input

Each edge causes two append operations, so the work grows with the number of edges.

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

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

Final Time Complexity

Time Complexity: O(E)

This means the time to build the adjacency list grows directly with the number of edges.

Common Mistake

[X] Wrong: "Adding an edge takes time proportional to the number of nodes."

[OK] Correct: Adding an edge only appends to lists, which is quick and does not depend on total nodes.

Interview Connect

Knowing adjacency list time complexity helps you explain graph storage choices clearly and confidently.

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 matrix showing distances between nodes

B. A list where each node stores its connected neighbors

C. A list of all nodes without connections

D. A stack of nodes visited during traversal

Solution

1. Step 1: Understand adjacency list concept and compare options

   An adjacency list stores each node with a list of its neighbors, showing direct connections. Only the description "A list where each node stores its connected neighbors" correctly describes this structure; others describe different concepts.

2. Final Answer:

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

3. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list always stores neighbors per node [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking adjacency list stores distances
• Mixing adjacency list with traversal order

2. Which Go syntax correctly declares an adjacency list for a graph with integer nodes?

easy

A. var graph map[int][]int = make(map[int][]int)

B. var graph []int = make([]int, 0)

C. var graph map[int]int = make(map[int]int)

D. var graph [][]int = make([][]int, 0)

Solution

1. Step 1: Identify adjacency list type in Go and check options for correct syntax

   An adjacency list maps each node (int) to a slice of connected nodes ([]int), so map[int][]int is correct. var graph map[int][]int = make(map[int][]int) uses map[int][]int with make, which is correct. Others use wrong types or slices without mapping.

2. Final Answer:

   var graph map[int][]int = make(map[int][]int) -> Option A

3. Quick Check:

   Adjacency list = map node to slice [OK]

Hint: Adjacency list in Go = map[node][]neighbors [OK]

Common Mistakes:

• Using slice of ints instead of map for adjacency list
• Declaring map[int]int which stores single int, not neighbors
• Confusing slice of slices with map

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

graph := make(map[int][]int)
graph[1] = []int{2, 3}
graph[2] = []int{1}
graph[3] = []int{1, 4}
graph[4] = []int{3}

for node, neighbors := range graph {
    fmt.Printf("%d -> %v\n", node, neighbors)
}

medium

A. 1 -> [2 3]
2 -> [1]
3 -> [1 4]
4 -> [3]

B. 1 -> [1 4]
2 -> [2 3]
3 -> [3]
4 -> [4]

C. 1 -> [2]
2 -> [3]
3 -> [4]
4 -> [1]

D. 1 -> []
2 -> []
3 -> []
4 -> []

Solution

1. Step 1: Analyze graph assignments and match printed output

   Node 1 connects to 2 and 3, node 2 connects to 1, node 3 connects to 1 and 4, node 4 connects to 3. Output prints each node with its neighbors slice exactly as assigned, matching 1 -> [2 3]\n2 -> [1]\n3 -> [1 4]\n4 -> [3].

2. Final Answer:

   1 -> [2 3] 2 -> [1] 3 -> [1 4] 4 -> [3] -> Option A

3. Quick Check:

   Print adjacency list as assigned [OK]

Hint: Print adjacency list shows node and its neighbors slice [OK]

Common Mistakes:

• Mixing neighbors between nodes
• Confusing slice contents order
• Assuming empty neighbors incorrectly

4. Identify the error in this Go code snippet for adding an edge to an undirected graph adjacency list:

func addEdge(graph map[int][]int, u int, v int) {
    graph[u] = append(graph[u], v)
    graph[v] = append(graph[u], v)
}

medium

A. append cannot be used with slices

B. Function does not return the updated graph

C. map[int][]int cannot be modified inside function

D. Second append uses graph[u] instead of graph[v]

Solution

1. Step 1: Review append calls for edges and identify correct usage

   First append adds v to graph[u], correct. Second append should add u to graph[v], but uses graph[u] mistakenly. Second append must be graph[v] = append(graph[v], u) to add reverse edge for undirected graph.

2. Final Answer:

   Second append uses graph[u] instead of graph[v] -> Option D

3. Quick Check:

   Append neighbors to correct node slice [OK]

Hint: Append neighbors to correct node slice for undirected edges [OK]

Common Mistakes:

• Appending to wrong slice causing incorrect graph
• Thinking map cannot be modified inside function
• Misunderstanding append usage in Go

5. You have a graph represented by an adjacency list in Go as map[int][]int. How would you efficiently check if an edge exists between nodes u and v?

hard

A. Iterate over graph[u] slice to find v; return true if found, else false

B. Check if graph[u][v] exists directly using indexing

C. Use a map[int]bool inside graph[u] for constant time lookup

D. Sort graph[u] slice and use binary search to find v

Solution

1. Step 1: Understand adjacency list lookup and optimize lookup with map

   graph[u] is a slice, so direct indexing by v is invalid (Check if graph[u][v] exists directly using indexing wrong). Iteration (Iterate over graph[u] slice to find v; return true if found, else false) is linear time. Using map[int]bool inside graph[u] allows constant time check if v is neighbor (Use a map[int]bool inside graph[u] for constant time lookup). Sorting and binary search (Sort graph[u] slice and use binary search to find v) adds overhead.

2. Final Answer:

   Use a map[int]bool inside graph[u] for constant time lookup -> Option C

3. Quick Check:

   Map lookup faster than slice iteration [OK]

Hint: Use map for neighbors to check edges fast [OK]

Common Mistakes:

• Trying to index slice by node value directly
• Ignoring performance of linear search
• Overcomplicating with sorting when map is simpler