Adjacency List Representation in DSA C#

Mental Model

We store each node's neighbors in a list so we can quickly see who it's connected to.

Analogy: Imagine a group of friends where each person keeps a list of their close friends. To find who someone knows, you just look at their list.

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

Dry Run Walkthrough

Input: Graph with 4 nodes: edges (0-1), (0-2), (1-3)

Goal: Build adjacency lists showing neighbors for each node

Step 1: Add edge from 0 to 1

0 -> [1]
1 -> []
2 -> []
3 -> []

Why: We record that node 0 connects to node 1

Step 2: Add edge from 1 to 0

0 -> [1]
1 -> [0]
2 -> []
3 -> []

Why: Since the graph is undirected, node 1 also connects back to node 0

Step 3: Add edge from 0 to 2

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

Why: Node 0 connects to node 2

Step 4: Add edge from 2 to 0

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

Why: Node 2 connects back to node 0

Step 5: Add edge from 1 to 3

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

Why: Node 1 connects to node 3

Step 6: Add edge from 3 to 1

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

Why: Node 3 connects back to node 1

Result:

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

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph
{
    private List<int>[] adjacencyList;

    public Graph(int nodes)
    {
        adjacencyList = new List<int>[nodes];
        for (int i = 0; i < nodes; i++)
        {
            adjacencyList[i] = new List<int>();
        }
    }

    public void AddEdge(int u, int v)
    {
        adjacencyList[u].Add(v); // add v to u's list
        adjacencyList[v].Add(u); // add u to v's list (undirected)
    }

    public void PrintGraph()
    {
        for (int i = 0; i < adjacencyList.Length; i++)
        {
            Console.Write(i + " -> [");
            for (int j = 0; j < adjacencyList[i].Count; j++)
            {
                Console.Write(adjacencyList[i][j]);
                if (j < adjacencyList[i].Count - 1)
                    Console.Write(", ");
            }
            Console.WriteLine("]");
        }
    }
}

class Program
{
    static void Main()
    {
        Graph graph = new Graph(4);
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.PrintGraph();
    }
}

adjacencyList[u].Add(v); // add v to u's list

Add neighbor v to node u's adjacency list

adjacencyList[v].Add(u); // add u to v's list (undirected)

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

for (int i = 0; i < adjacencyList.Length; i++)

Iterate over each node to print its neighbors

for (int j = 0; j < adjacencyList[i].Count; j++)

Iterate over neighbors of node i to print them

Output

0 -> [1, 2]

1 -> [0, 3]

2 -> [0]

3 -> [1]

Complexity Analysis

Time: O(V + E) because we create a list for each of the V nodes and add each of the E edges twice

Space: O(V + E) because we store a list of neighbors for each node and each edge appears twice

vs Alternative: Compared to adjacency matrix which uses O(V^2) space, adjacency list is more efficient for sparse graphs

Edge Cases

Graph with no edges

Each node's adjacency list remains empty

DSA C#

for (int i = 0; i < nodes; i++)
        {
            adjacencyList[i] = new List<int>();
        }

Graph with single node

Adjacency list has one empty list

DSA C#

adjacencyList = new List<int>[nodes];

Adding duplicate edges

Duplicates appear in adjacency lists since no check is done

DSA C#

adjacencyList[u].Add(v);

When to Use This Pattern

When you need to represent a graph efficiently and quickly find neighbors, use adjacency list representation because it stores only existing edges.

Common Mistakes

Mistake: Forgetting to add the edge in both directions for undirected graphs
Fix: Add both adjacencyList[u].Add(v) and adjacencyList[v].Add(u) to represent undirected edges

Mistake: Initializing adjacency lists incorrectly causing null reference errors
Fix: Initialize each list in the array before adding neighbors

Summary

Stores each node's neighbors in a list for efficient graph representation.

Use when you want to save space and quickly access neighbors in sparse graphs.

The key is that each node keeps a list of only its connected nodes, not all nodes.

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