Why Adjacency List Representation in DSA C#?

The Big Idea

Discover how a simple list can save you from drowning in useless data!

The Scenario

Imagine you want to keep track of friends in a social group. You try writing down every possible pair of friends in a big table, even if many people have only a few friends.

The Problem

This big table wastes a lot of space and takes a long time to find who is friends with whom. It also becomes confusing and slow when the group grows.

The Solution

Using an adjacency list, you write down each person and just list their friends next to them. This way, you save space and quickly see connections without searching a huge table.

Before vs After

✗ Before

int[,] graph = new int[5,5]; // matrix with many zeros
// to find friends, check all pairs

✓ After

List<int>[] adjacencyList = new List<int>[5];
for (int i = 0; i < 5; i++) {
    adjacencyList[i] = new List<int>();
}
// each list holds friends of one person

What It Enables

This lets you efficiently store and explore connections in large networks without wasting space or time.

Real Life Example

Social media platforms use adjacency lists to quickly find your friends and friends of friends without scanning everyone.

Key Takeaways

Manual tables waste space and slow down searches.

Adjacency lists store only real connections, saving space.

They make exploring networks faster and easier.

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