Adjacency List Representation in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare an adjacency list for a graph with 5 vertices.

DSA Java

List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < [1]; i++) {
    adjList.add(new ArrayList<>());
}

Drag options to blanks, or click blank then click option'

A6

B4

C5

D3

Attempts:

3 left

💡 Hint

Common Mistakes

Using a wrong number of vertices in the loop.

Not initializing the inner lists.

The graph has 5 vertices, so we create 5 empty lists inside the adjacency list.

2fill in blank

medium

Complete the code to add an edge from vertex 2 to vertex 4 in the adjacency list.

DSA Java

adjList.get([1]).add(4);

Drag options to blanks, or click blank then click option'

A3

B2

C4

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong index for the vertex.

Adding the edge to the wrong list.

To add an edge from vertex 2, we get the list at index 2 and add 4 to it.

3fill in blank

hard

Fix the error in the code to correctly add an undirected edge between vertices 1 and 3.

DSA Java

adjList.get(1).add([1]);
adjList.get(3).add(1);

Drag options to blanks, or click blank then click option'

A3

B1

C2

D4

Attempts:

3 left

💡 Hint

Common Mistakes

Adding the wrong vertex to the adjacency list.

Only adding one direction of the edge.

To add an undirected edge between 1 and 3, add 3 to 1's list and 1 to 3's list.

4fill in blank

hard

Fill both blanks to print all neighbors of vertex 0 using a for-each loop.

DSA Java

for (Integer [1] : adjList.get(0)) {
    System.out.println([2]);
}

Drag options to blanks, or click blank then click option'

Aneighbor

BadjList

Dvertex

Attempts:

3 left

💡 Hint

Common Mistakes

Using the wrong variable name in the print statement.

Confusing the adjacency list with the neighbor variable.

Use 'neighbor' as the loop variable and print it to show all neighbors of vertex 0.

5fill in blank

hard

Fill all three blanks to create an adjacency list from edges and print neighbors of vertex 1.

DSA Java

int[][] edges = [1];
List<List<Integer>> adjList = new ArrayList<>();
for (int i = 0; i < 3; i++) {
    adjList.add(new ArrayList<>());
}
for (int[] edge : edges) {
    adjList.get(edge[0]).add(edge[1]);
    adjList.get(edge[1]).add(edge[0]);
}
for (Integer [2] : adjList.get([3])) {
    System.out.print([2] + " ");
}

Drag options to blanks, or click blank then click option'

A{{1, 2}, {0, 1}, {1, 0}}

Bneighbor

C1

D{{0, 1}, {1, 2}, {2, 0}}

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect edge arrays.

Using wrong loop variable names.

Printing neighbors of the wrong vertex.

Use edges {{0,1}, {1,2}, {2,0}}; loop variable 'neighbor'; print neighbors of vertex 1.

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