Adjacency List Representation in DSA Java - Build from Scratch

Adjacency List Representation

📖 Scenario: You are working on a simple social network app. Each user can have friends. You want to store who is friends with whom using a graph.

🎯 Goal: Build an adjacency list representation of the friendship graph using Java's HashMap and ArrayList. Then print the adjacency list.

📋 What You'll Learn

Create a HashMap<String, ArrayList<String>> called friendGraph.

Add users as keys and their friends as list values.

Use exact user names and friends as specified.

Print the adjacency list in the format: User: friend1 -> friend2 -> ...

💡 Why This Matters

🌍 Real World

Social networks, recommendation systems, and network analysis often use adjacency lists to store connections efficiently.

💼 Career

Understanding adjacency lists is fundamental for software engineers working with graphs, networks, and data relationships.

1

Create the friendship graph

Create a HashMap<String, ArrayList<String>> called friendGraph and add these entries exactly: "Alice" with friends "Bob" and "Charlie", "Bob" with friend "Alice", and "Charlie" with friend "Alice".

DSA Java

// Your code here

Hint

Use HashMap<String, ArrayList<String>> and add friends using add() method on ArrayList.

2

Add a user with no friends

Create an empty ArrayList<String> called davidFriends and add it to friendGraph with the key "David" to represent a user with no friends.

DSA Java

import java.util.HashMap;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        HashMap> friendGraph = new HashMap();

        ArrayList aliceFriends = new ArrayList();
        aliceFriends.add("Bob");
        aliceFriends.add("Charlie");
        friendGraph.put("Alice", aliceFriends);

        ArrayList bobFriends = new ArrayList();
        bobFriends.add("Alice");
        friendGraph.put("Bob", bobFriends);

        ArrayList charlieFriends = new ArrayList();
        charlieFriends.add("Alice");
        friendGraph.put("Charlie", charlieFriends);

        // Your code here
    }
}

Hint

Create an empty ArrayList<String> and add it to friendGraph with key "David".

3

Print the adjacency list

Use a for loop with variables user and friends to iterate over friendGraph.entrySet(). Inside the loop, print the user followed by a colon and space, then print each friend separated by " -> " without a trailing arrow.

DSA Java

import java.util.HashMap;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        HashMap> friendGraph = new HashMap();

        ArrayList aliceFriends = new ArrayList();
        aliceFriends.add("Bob");
        aliceFriends.add("Charlie");
        friendGraph.put("Alice", aliceFriends);

        ArrayList bobFriends = new ArrayList();
        bobFriends.add("Alice");
        friendGraph.put("Bob", bobFriends);

        ArrayList charlieFriends = new ArrayList();
        charlieFriends.add("Alice");
        friendGraph.put("Charlie", charlieFriends);

        ArrayList davidFriends = new ArrayList();
        friendGraph.put("David", davidFriends);

        // Your code here
    }
}

Hint

Use a for loop over friendGraph.entrySet(). Print the user, then loop over their friends printing with arrows between.

4

Print the final adjacency list output

Write a System.out.println statement inside the loop to print the adjacency list in the format: User: friend1 -> friend2 -> .... For users with no friends, print only User: .

DSA Java

import java.util.HashMap;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        HashMap> friendGraph = new HashMap();

        ArrayList aliceFriends = new ArrayList();
        aliceFriends.add("Bob");
        aliceFriends.add("Charlie");
        friendGraph.put("Alice", aliceFriends);

        ArrayList bobFriends = new ArrayList();
        bobFriends.add("Alice");
        friendGraph.put("Bob", bobFriends);

        ArrayList charlieFriends = new ArrayList();
        charlieFriends.add("Alice");
        friendGraph.put("Charlie", charlieFriends);

        ArrayList davidFriends = new ArrayList();
        friendGraph.put("David", davidFriends);

        // Your code here
    }
}

Hint

Check the output matches exactly the format with arrows and no trailing arrow for last friend.

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