Adjacency List Representation in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list after adding edges

What is the printed adjacency list after adding the edges in the given Java code?

DSA Java

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjList.computeIfAbsent(v, k -> new ArrayList<>());
    }

    public void printGraph() {
        for (int key : adjList.keySet()) {
            System.out.print(key + " -> ");
            for (int val : adjList.get(key)) {
                System.out.print(val + " -> ");
            }
            System.out.println("null");
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);
        g.printGraph();
    }
}

A

1 -> 2 -> 3 -> null
2 -> 1 -> 4 -> null
3 -> 1 -> null
4 -> 2 -> null

B

1 -> 2 -> 3 -> null
2 -> 4 -> null
3 -> null
4 -> null

C

1 -> 2 -> 3 -> null
2 -> 4 -> 1 -> null
3 -> null
4 -> null

D

1 -> 2 -> 3 -> null
2 -> 4 -> null
3 -> 1 -> null
4 -> 2 -> null

💡 Hint

Look carefully at how edges are added and which nodes get neighbors.

The addEdge method adds v to u's list and ensures v exists in the map with an empty list. It does not add u to v's list, so edges are one-way.

❓ Predict Output

intermediate

Output after adding undirected edges

What is the output of the adjacency list after adding edges with the undirected addEdge method?

DSA Java

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }

    public void printGraph() {
        for (int key : adjList.keySet()) {
            System.out.print(key + " -> ");
            for (int val : adjList.get(key)) {
                System.out.print(val + " -> ");
            }
            System.out.println("null");
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);
        g.printGraph();
    }
}

A

1 -> 2 -> 3 -> null
2 -> 4 -> 1 -> null
3 -> null
4 -> null

B

1 -> 2 -> 3 -> null
2 -> 4 -> null
3 -> null
4 -> null

C

1 -> 2 -> 3 -> null
2 -> 1 -> null
3 -> 1 -> null
4 -> 2 -> null

D

1 -> 2 -> 3 -> null
2 -> 1 -> 4 -> null
3 -> 1 -> null
4 -> 2 -> null

💡 Hint

Edges are added both ways for undirected graphs.

Since addEdge adds v to u's list and u to v's list, neighbors appear in both nodes' lists.

🔧 Debug

advanced

Identify the error in adjacency list initialization

What error will this Java code produce when trying to add edges to the adjacency list?

DSA Java

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int u, int v) {
        adjList.get(u).add(v);
        adjList.get(v).add(u);
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(1, 2);
    }
}

A NullPointerException

B IndexOutOfBoundsException

C ClassCastException

D No error, runs fine

💡 Hint

Check if the adjacency list has entries before calling get(u).add(v).

The map is empty initially, so adjList.get(u) returns null, causing NullPointerException when calling add.

🧠 Conceptual

advanced

Memory efficiency of adjacency list vs adjacency matrix

Which statement correctly explains why adjacency lists are more memory efficient than adjacency matrices for sparse graphs?

A Adjacency matrices store edges as objects, which use more memory than primitive types in adjacency lists.

B Adjacency lists require a fixed size array for all nodes, increasing memory usage compared to adjacency matrices.

C Adjacency lists store only existing edges, while adjacency matrices store all possible edges including non-existent ones.

D Adjacency matrices use linked lists internally, which consume more memory than arrays used in adjacency lists.

💡 Hint

Think about how each structure stores edges for nodes that have few connections.

Adjacency lists only keep neighbors for nodes that have edges, saving space when many edges are missing.

❓ Predict Output

expert

Output after removing an edge from adjacency list

What is the output of the adjacency list after removing edge (1, 3) from the undirected graph?

DSA Java

import java.util.*;

public class Graph {
    private Map<Integer, List<Integer>> adjList = new HashMap<>();

    public void addEdge(int u, int v) {
        adjList.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
        adjList.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
    }

    public void removeEdge(int u, int v) {
        adjList.getOrDefault(u, new ArrayList<>()).remove(Integer.valueOf(v));
        adjList.getOrDefault(v, new ArrayList<>()).remove(Integer.valueOf(u));
    }

    public void printGraph() {
        for (int key : adjList.keySet()) {
            System.out.print(key + " -> ");
            for (int val : adjList.get(key)) {
                System.out.print(val + " -> ");
            }
            System.out.println("null");
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(1, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 4);
        g.removeEdge(1, 3);
        g.printGraph();
    }
}

A

1 -> 2 -> null
2 -> 1 -> 4 -> null
3 -> null
4 -> 2 -> null

B

1 -> 2 -> 3 -> null
2 -> 1 -> 4 -> null
3 -> 1 -> null
4 -> 2 -> null

C

1 -> 2 -> null
2 -> 4 -> null
3 -> null
4 -> 2 -> null

D

1 -> 2 -> null
2 -> 1 -> null
3 -> null
4 -> 2 -> null

💡 Hint

Removing edge (1,3) removes 3 from 1's list and 1 from 3's list.

After removal, 1's neighbors are only 2, and 3 has no neighbors. Other edges remain unchanged.

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