Adjacency List Representation in DSA Java

Mental Model

We store each node's neighbors in a list so we can quickly see who it connects 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 edges: 0-1, 0-2, 1-3

Goal: Build adjacency lists showing neighbors for each node

Step 1: Add edge 0-1: add 1 to 0's list and 0 to 1's list

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

Why: We record that 0 and 1 are connected both ways

Step 2: Add edge 0-2: add 2 to 0's list and 0 to 2's list

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

Why: We record that 0 and 2 are connected both ways

Step 3: Add edge 1-3: add 3 to 1's list and 1 to 3's list

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

Why: We record that 1 and 3 are connected both ways

Result:

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

Annotated Code

DSA Java

import java.util.*;

class Graph {
    private final int vertices;
    private final List<List<Integer>> adjList;

    public Graph(int vertices) {
        this.vertices = vertices;
        adjList = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest); // add dest to src's list
        adjList.get(dest).add(src); // add src to dest's list (undirected)
    }

    public void printGraph() {
        for (int i = 0; i < vertices; i++) {
            System.out.print(i + " -> ");
            System.out.println(adjList.get(i));
        }
    }
}

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

adjList.get(src).add(dest); // add dest to src's list

Add destination node to source node's adjacency list

adjList.get(dest).add(src); // add src to dest's list (undirected)

Add source node to destination node's adjacency list for undirected graph

for (int i = 0; i < vertices; i++) { System.out.print(i + " -> "); System.out.println(adjList.get(i)); }

Print each node and its list of neighbors

Output

0 -> [1, 2]

1 -> [0, 3]

2 -> [0]

3 -> [1]

Complexity Analysis

Time: O(V + E) because we create a list for each vertex and add each edge twice

Space: O(V + E) because adjacency lists store all vertices and edges explicitly

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

All adjacency lists remain empty

DSA Java

for (int i = 0; i < vertices; i++) {
    adjList.add(new ArrayList<>());
}

Graph with single vertex

One empty adjacency list is created

DSA Java

for (int i = 0; i < vertices; i++) {
    adjList.add(new ArrayList<>());
}

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: Always add dest to src's list and src to dest's list to keep connections symmetric

Mistake: Initializing adjacency list with fixed size but not creating inner lists
Fix: Create a new empty list for each vertex during initialization

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 to keep a list for each node showing exactly who it connects to.

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