Adjacency List Representation in DSA C++ - 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.

// Build adjacency list for a graph with n vertices and edges
vector<vector<int>> adjList(n);
for (auto &edge : edges) {
    int u = edge[0];
    int v = edge[1];
    adjList[u].push_back(v);
    adjList[v].push_back(u); // if undirected
}
    

This code creates a list of neighbors for each vertex from the given edges.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping over all edges to add neighbors.
• How many times: Once for each edge, so as many times as edges count.

How Execution Grows With Input

As the number of edges grows, the time to build the list grows roughly the same.

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

Pattern observation: The work grows directly with the number of edges.

Final Time Complexity

Time Complexity: O(E)

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

Common Mistake

[X] Wrong: "Building adjacency list takes O(V^2) time because we have to check all pairs of vertices."

[OK] Correct: We only add neighbors for edges that exist, so the time depends on edges, not all vertex pairs.

Interview Connect

Knowing adjacency list time complexity helps you explain graph storage choices clearly and efficiently in interviews.

Self-Check

"What if the graph is directed and we only add one direction for each edge? How does the time complexity change?"

Practice

1. What does an adjacency list represent in graph data structures?

easy

A. A list storing only isolated vertices

B. A matrix showing connections between all pairs of vertices

C. A list of all edges without vertex information

D. A list where each vertex stores a list of its adjacent vertices

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each vertex and the vertices it connects to directly.

2. Step 2: Compare with other graph representations

   Unlike adjacency matrix, adjacency list focuses on neighbors per vertex, not all pairs.

3. Final Answer:

   A list where each vertex stores a list of its adjacent vertices -> Option D

4. Quick Check:

   Adjacency list = vertex with neighbors [OK]

Hint: Adjacency list = vertex + its neighbors list [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking it stores all edges as pairs only
• Assuming it stores isolated vertices only

2. Which of the following is the correct C++ syntax to declare an adjacency list for a graph with n vertices using vectors?

easy

A. vector<int> adj[n];

B. vector adj(n);

C. vector adj[n];

D. vector<int> adj(n);

Solution

1. Step 1: Understand vector of vectors declaration

   To represent adjacency list, we use vector adj(n); to create n empty lists.

2. Step 2: Check other options for correctness

   vector<int> adj[n]; declares a non-standard variable-length array (VLA) of vectors. vector adj[n]; is invalid syntax. vector<int> adj(n); declares a single vector of ints, not a list of lists.

3. Final Answer:

   vector adj(n); -> Option B

4. Quick Check:

   Use vector of vectors for adjacency list [OK]

Hint: Use vector for adjacency list [OK]

Common Mistakes:

• Using vector<int> adj(n) which is 1D vector
• Incorrect syntax like vector adj[n];
• Confusing array of vectors with vector of vectors

3. What will be the output adjacency list after executing the following C++ code?

int V = 3;
vector adj(V);
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(2);
for(int i = 0; i < V; i++) {
  cout << i << ": ";
  for(auto v : adj[i]) cout << v << " ";
  cout << endl;
}

medium

A. 0: 1 2
1: 2
2:

B. 0: 2 1
1: 2
2:

C. 0: 1
1: 2
2: 0 1

D. 0:
1: 0 2
2: 1

Solution

1. Step 1: Trace adjacency list insertions

   adj[0] gets 1 and 2 pushed, adj[1] gets 2 pushed, adj[2] remains empty.

2. Step 2: Print adjacency list content

   For i=0: prints "0: 1 2 ", for i=1: "1: 2 ", for i=2: "2: " (empty).

3. Final Answer:

   0: 1 2 1: 2 2: -> Option A

4. Quick Check:

   Push_back order preserved in adjacency list [OK]

Hint: Push_back order shows neighbors in insertion order [OK]

Common Mistakes:

• Assuming adjacency list is sorted automatically
• Mixing up indices and values
• Printing empty lists incorrectly

4. Identify the error in the following code snippet that tries to add an edge to an adjacency list for an undirected graph:

int V = 4;
vector adj(V);
int u = 1, v = 3;
adj[u].push_back(v);
// Missing line here

medium

A. The code should also add adj[v].push_back(u) for undirected edge

B. The vector declaration is incorrect

C. The indices u and v are out of range

D. push_back should be replaced with insert

Solution

1. Step 1: Understand undirected graph edge addition

   For undirected graphs, edges must be added both ways: u to v and v to u.

2. Step 2: Check code for missing reverse edge

   Code adds edge from u to v but misses adj[v].push_back(u), so graph is incomplete.

3. Final Answer:

   The code should also add adj[v].push_back(u) for undirected edge -> Option A

4. Quick Check:

   Undirected edge = add both directions [OK]

Hint: Add edges both ways for undirected graphs [OK]

Common Mistakes:

• Adding edge only one way in undirected graph
• Using wrong vector syntax
• Confusing push_back with insert

5. Given a directed graph with 4 vertices and edges: (0->1), (0->2), (1->2), (2->0), (2->3), (3->3), which adjacency list representation correctly shows the graph?

hard

A. 0: 2 1
1: 2
2: 3 0
3: 3

B. 0: 1 2
1: 0 2
2: 0 3
3: 3

C. 0: 1 2
1: 2
2: 0 3
3: 3

D. 0: 1 2
1: 2
2: 3
3: 0 3

Solution

1. Step 1: List edges for each vertex

   Vertex 0 connects to 1 and 2, vertex 1 connects to 2, vertex 2 connects to 0 and 3, vertex 3 connects to itself (3).

2. Step 2: Match edges to adjacency list options

   0: 1 2 1: 2 2: 0 3 3: 3 matches exactly the edges given. Others have wrong order or extra edges.

3. Final Answer:

   0: 1 2 1: 2 2: 0 3 3: 3 -> Option C

4. Quick Check:

   Match edges to adjacency list exactly [OK]

Hint: Write edges per vertex to verify adjacency list [OK]

Common Mistakes:

• Mixing order of neighbors
• Adding edges not in original graph
• Missing self-loop at vertex 3