Adjacency List Representation in DSA C# - Time & Space Complexity

Time Complexity: Adjacency List Representation

O(n + m)

Understanding Time Complexity

We want to understand how the time to build and use an adjacency list changes as the graph grows.

How does the number of nodes and edges affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Create adjacency list for a graph
var adjacencyList = new Dictionary<int, List<int>>();

void AddEdge(int u, int v) {
    if (!adjacencyList.ContainsKey(u)) {
        adjacencyList[u] = new List<int>();
    }
    adjacencyList[u].Add(v);
}
    

This code adds a directed edge from node u to node v in the adjacency list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding edges to the adjacency list.
• How many times: Once per edge added.

How Execution Grows With Input

Each edge causes one addition to a list. The number of nodes affects dictionary checks.

Input Size (n = nodes, m = edges)	Approx. Operations
10 nodes, 15 edges	About 15 insertions and up to 10 dictionary checks
100 nodes, 200 edges	About 200 insertions and up to 100 dictionary checks
1000 nodes, 5000 edges	About 5000 insertions and up to 1000 dictionary checks

Pattern observation: Operations grow roughly with the number of edges and nodes.

Final Time Complexity

Time Complexity: O(n + m)

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

Common Mistake

[X] Wrong: "Adding edges takes O(m²) time because each insertion searches the whole list."

[OK] Correct: Each edge is added directly to a list without searching, so insertion is fast and does not depend on the number of edges already added.

Interview Connect

Understanding adjacency list time complexity helps you explain graph storage and traversal efficiency clearly in interviews.

Self-Check

"What if we used an adjacency matrix instead of a list? How would the time complexity for adding edges change?"

Practice

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

easy

A. A list of all nodes without connections

B. A list where each node stores its connected neighbors

C. A matrix showing distances between nodes

D. A queue used for graph traversal

Solution

1. Step 1: Understand adjacency list concept

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

2. Step 2: Compare with other options

   Other options describe different structures: matrix, isolated nodes, or traversal tools, not adjacency lists.

3. Final Answer:

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

4. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list always links nodes to their neighbors [OK]

Common Mistakes:

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

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

easy

A. Dictionary adjacencyList = new Dictionary();

B. List<int> adjacencyList = new List<int>();

C. Dictionary adjacencyList = new Dictionary();

D. int[][] adjacencyList = new int[5][];

Solution

1. Step 1: Identify adjacency list structure

   An adjacency list maps each node (int) to a list of connected nodes (List<int>), so Dictionary fits.

2. Step 2: Check other options

   List<int> adjacencyList = new List<int>(); is a simple list, not mapping nodes to neighbors. int[][] adjacencyList = new int[5][]; is an array of arrays, possible but less flexible. Dictionary adjacencyList = new Dictionary(); maps int to int, not to a list.

3. Final Answer:

   Dictionary<int, List<int>> adjacencyList = new Dictionary<int, List<int>>(); -> Option C

4. Quick Check:

   Use Dictionary with List for adjacency list [OK]

Hint: Use Dictionary for adjacency lists in C# [OK]

Common Mistakes:

• Using List<int> alone without mapping nodes
• Using Dictionary instead of list of neighbors
• Confusing jagged arrays with adjacency lists

3. Given the following C# code, what is the output?

var graph = new Dictionary();
graph[1] = new List<int> {2, 3};
graph[2] = new List<int> {1};
graph[3] = new List<int> {1};

foreach(var node in graph)
{
    Console.Write(node.Key + ": ");
    foreach(var neighbor in node.Value)
    {
        Console.Write(neighbor + " ");
    }
    Console.WriteLine();
}

medium

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

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

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

D. 1:
2:
3:

Solution

1. Step 1: Analyze graph initialization

   Node 1 connects to 2 and 3; node 2 connects to 1; node 3 connects to 1.

2. Step 2: Trace output loop

   For each node, print key and neighbors separated by spaces. So output lines are: "1: 2 3 " "2: 1 " "3: 1 "

3. Final Answer:

   1: 2 3 2: 1 3: 1 -> Option A

4. Quick Check:

   Print node keys with their neighbors [OK]

Hint: Print keys with their neighbor lists exactly as stored [OK]

Common Mistakes:

• Printing node itself as neighbor
• Missing spaces between neighbors
• Printing empty neighbor lists

4. Identify the error in this adjacency list code snippet and select the fix:

var graph = new Dictionary();
graph[1].Add(2);
graph[1].Add(3);

medium

A. Initialize graph[1] with a new List<int> before adding neighbors

B. Change Dictionary to Dictionary

C. Use graph.Add(1, 2) instead of graph[1].Add(2)

D. Remove the Add calls; just declare graph

Solution

1. Step 1: Understand dictionary initialization

   graph[1] is not initialized with a list, so calling Add on null causes error.

2. Step 2: Fix by initializing list

   Assign graph[1] = new List<int>() before adding neighbors fixes the null reference error.

3. Final Answer:

   Initialize graph[1] with a new List<int> before adding neighbors -> Option A

4. Quick Check:

   Initialize list before adding elements [OK]

Hint: Always create list before adding neighbors [OK]

Common Mistakes:

• Trying to add to null list
• Changing dictionary type incorrectly
• Using Add method wrongly on dictionary

5. You have a graph represented by an adjacency list: Dictionary. How would you add an undirected edge between nodes 4 and 5?

hard

A. Add a new dictionary entry with key 4 and value 5

B. Add 5 to node 4's list only

C. Add 4 to node 5's list only

D. Add 5 to node 4's list and 4 to node 5's list

Solution

1. Step 1: Understand undirected edge meaning

   Undirected edge means both nodes connect to each other, so both lists must include the other node.

2. Step 2: Add neighbors to both nodes

   Add 5 to node 4's neighbor list and 4 to node 5's neighbor list to represent the edge correctly.

3. Final Answer:

   Add 5 to node 4's list and 4 to node 5's list -> Option D

4. Quick Check:

   Undirected edge = mutual neighbor entries [OK]

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

Common Mistakes:

• Adding edge only one way
• Adding wrong node to list
• Using dictionary entry incorrectly