Adjacency List Representation in DSA Java - Execution Trace

Concept Flow - Adjacency List Representation

Start

↓

Create empty adjacency list

↓

Add vertices

↓

For each edge

↓

Add edge to adjacency list

↓

Repeat for all edges

↓

Graph represented as adjacency list

↓

End

Build an adjacency list by creating a list for each vertex and adding connected vertices for each edge.

Execution Sample

DSA Java

int V = 3;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
adj.get(0).add(1);
adj.get(1).add(2);

Create adjacency list for 3 vertices and add edges 0->1 and 1->2.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Initialize adjacency list with 3 empty lists	0:[], 1:[], 2:[]	adj points to list of 3 empty lists	[0]->[], [1]->[], [2]->[]
2	Add edge 0->1	0:[1], 1:[], 2:[]	adj.get(0) adds 1	[0]->[1], [1]->[], [2]->[]
3	Add edge 1->2	0:[1], 1:[2], 2:[]	adj.get(1) adds 2	[0]->[1], [1]->[2], [2]->[]
4	No more edges	0:[1], 1:[2], 2:[]	No pointer changes	[0]->[1], [1]->[2], [2]->[]

💡 All edges processed, adjacency list complete

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
adj	null	[[], [], []]	[[1], [], []]	[[1], [2], []]	[[1], [2], []]
V	3	3	3	3	3

Key Moments - 3 Insights

Why do we add edges to adj.get(vertex) instead of adj directly?

Because adj is a list of lists, each adj.get(vertex) is the list of neighbors for that vertex. See execution_table step 2 and 3 where edges are added to specific vertex lists.

What does an empty list for a vertex mean?

It means that vertex has no outgoing edges. For example, vertex 2 has an empty list in execution_table step 4.

Why do we initialize adjacency list with empty lists for each vertex?

To have a place to store neighbors for each vertex. Without initialization, we cannot add edges. See execution_table step 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the adjacency list for vertex 0?

A [2]

B [1]

C []

D [0]

💡 Hint

Check the 'Nodes in List' column at step 2 for vertex 0.

At which step does vertex 1 get its first neighbor added?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at 'Operation' and 'Nodes in List' columns to see when adj.get(1) changes.

If we add an edge 2->0, how would the visual state change at step 4?

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

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

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

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

💡 Hint

Adding edge 2->0 means adding 0 to adj.get(2) list.

Concept Snapshot

Adjacency List Representation:
- Use a list of lists to store graph edges.
- Each index represents a vertex.
- Each list at index stores neighbors.
- Initialize with empty lists for all vertices.
- Add edges by appending neighbors to vertex lists.

Full Transcript

We start by creating an empty adjacency list with one empty list per vertex. Then for each edge, we add the connected vertex to the corresponding list. For example, adding edge 0 to 1 means adding 1 to the list at index 0. This builds a simple and efficient graph representation. Empty lists mean no outgoing edges for that vertex. This method is easy to update and traverse.

Practice

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

easy

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

B. A matrix showing connections between all pairs of vertices

C. A list of all edges without vertex connections

D. A list storing only isolated vertices

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each vertex with a list of 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 A

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 edges only without vertices
• Assuming it stores isolated vertices only

2. Which of the following is the correct Java syntax to declare an adjacency list for a graph with 5 vertices?

easy

A. ArrayList<Integer>[] graph = new ArrayList[5];

B. ArrayList<Integer> graph = new ArrayList(5);

C. List<Integer> graph = new List[5];

D. ArrayList[] graph = new ArrayList<Integer>(5);

Solution

1. Step 1: Understand adjacency list declaration

   We need an array of ArrayLists, one for each vertex, so ArrayList<Integer>[] is correct.

2. Step 2: Check syntax correctness

   ArrayList<Integer>[] graph = new ArrayList[5]; correctly declares an array of ArrayLists with size 5. Others misuse generics or types.

3. Final Answer:

   ArrayList<Integer>[] graph = new ArrayList[5]; -> Option A

4. Quick Check:

   Array of ArrayLists = ArrayList<Integer>[] graph = new ArrayList[5]; [OK]

Hint: Adjacency list = array of ArrayLists in Java [OK]

Common Mistakes:

• Using List instead of ArrayList for array declaration
• Trying to instantiate generic arrays directly
• Missing generic type in ArrayList declaration

3. Given the following Java code snippet for an undirected graph adjacency list, what will be the output after adding edges?

ArrayList<Integer>[] graph = new ArrayList[3];
for (int i = 0; i < 3; i++) graph[i] = new ArrayList<>();
graph[0].add(1);
graph[1].add(0);
graph[1].add(2);
graph[2].add(1);
System.out.println(graph[1]);

medium

A. [0, 1]

B. [1, 2]

C. [2]

D. [0, 2]

Solution

1. Step 1: Trace additions to graph[1]

   graph[1] adds 0 and 2, so its list contains [0, 2].

2. Step 2: Confirm output of System.out.println(graph[1])

   Printing graph[1] shows the list [0, 2].

3. Final Answer:

   [0, 2] -> Option D

4. Quick Check:

   graph[1] = [0, 2] [OK]

Hint: Check which vertices are added to graph[1] list [OK]

Common Mistakes:

• Confusing indices and values in adjacency list
• Forgetting undirected edges require adding both ways
• Misreading the printed list order

4. Identify the error in this Java code snippet that tries to create an adjacency list for a graph with 4 vertices:

ArrayList<Integer>[] graph = new ArrayList[4];
for (int i = 0; i <= 4; i++) {
    graph[i] = new ArrayList<>();
}

medium

A. Missing generic type in ArrayList declaration

B. ArrayList cannot be used for adjacency list

C. Loop condition should be i < 4, not i <= 4

D. Array size should be 5 instead of 4

Solution

1. Step 1: Analyze loop range and array size

   Array size is 4, valid indices are 0 to 3. Loop uses i <= 4, which accesses index 4 (out of bounds).

2. Step 2: Identify correct loop condition

   Loop should run while i < 4 to avoid ArrayIndexOutOfBoundsException.

3. Final Answer:

   Loop condition should be i < 4, not i <= 4 -> Option C

4. Quick Check:

   Array indices 0 to 3, loop must use i < 4 [OK]

Hint: Array indices go from 0 to size-1 [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Assuming array size 4 means indices 0 to 4
• Ignoring generic type warnings

5. You want to represent a weighted directed graph using adjacency lists in Java. Which data structure is best to store the edges for each vertex?

hard

A. ArrayList<Integer> storing only destination vertices

B. ArrayList> storing destination and weight

C. ArrayList storing all edges as lists

D. ArrayList<Boolean> storing if edge exists or not

Solution

1. Step 1: Understand weighted directed graph needs

   Each edge has a destination vertex and a weight value, so both must be stored.

2. Step 2: Choose data structure to store pairs

   Using ArrayList of Pair allows storing destination and weight together.

3. Step 3: Evaluate other options

   ArrayList<Integer> storing only destination vertices stores only destination, missing weight; ArrayList storing all edges as lists is nested lists without clear pair; ArrayList<Boolean> storing if edge exists or not stores booleans, not weights.

4. Final Answer:

   ArrayList> storing destination and weight -> Option B

5. Quick Check:

   Weighted edges need destination + weight pairs [OK]

Hint: Store edges as pairs (destination, weight) in adjacency list [OK]

Common Mistakes:

• Storing only destination without weight
• Using nested lists without clear structure
• Using booleans which can't hold weights