Why Adjacency List Representation in DSA Java?

The Big Idea

Discover how to handle huge networks without drowning in wasted space!

The Scenario

Imagine you want to keep track of friendships in a large school. You try to write down every possible pair of friends in a big table, marking if they are friends or not.

The Problem

This table becomes huge and mostly empty because not everyone is friends with everyone else. It takes a lot of time to find who is friends with whom, and you waste space storing many empty spots.

The Solution

Using an adjacency list, you only write down the friends each person has. This way, you save space and quickly find friends by looking at a small list for each person.

Before vs After

✗ Before

int[][] friendshipMatrix = new int[numberOfStudents][numberOfStudents];
// Fill matrix with 0 or 1 to show friendship
// Check friendship by accessing friendshipMatrix[i][j]

✓ After

List<List<Integer>> adjacencyList = new ArrayList<>();
// Each list at index i holds friends of student i
// Check friends by iterating adjacencyList.get(i)

What It Enables

It enables efficient storage and quick lookup of connections in large networks without wasting space.

Real Life Example

Social media platforms use adjacency lists to store who follows whom, making it easy to find friends or followers without huge memory use.

Key Takeaways

Adjacency lists store only existing connections, saving space.

They allow fast access to neighbors of a node.

Ideal for sparse graphs where many pairs are not connected.

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