Adjacency List Representation in DSA Javascript

Mental Model

We store each node's neighbors in a list so we can quickly see who it's connected to.

Analogy: Imagine a group of friends where each person keeps a list of their friends' names. 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 by adding 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 by adding 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 by adding 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 Javascript

class Graph {
  constructor(vertices) {
    this.vertices = vertices;
    this.adjList = new Map();
    for (let i = 0; i < vertices; i++) {
      this.adjList.set(i, []);
    }
  }

  addEdge(v, w) {
    this.adjList.get(v).push(w); // add w to v's list
    this.adjList.get(w).push(v); // add v to w's list (undirected)
  }

  printGraph() {
    for (let [vertex, neighbors] of this.adjList) {
      console.log(`${vertex} -> [${neighbors.join(", ")}]`);
    }
  }
}

// Driver code
const g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.printGraph();

this.adjList.get(v).push(w); // add w to v's list

Add neighbor w to vertex v's adjacency list

this.adjList.get(w).push(v); // add v to w's list (undirected)

Add neighbor v to vertex w's adjacency list for undirected edge

Output

0 -> [1, 2]

1 -> [0, 3]

2 -> [0]

3 -> [1]

Complexity Analysis

Time: O(1) for each edge insertion because we directly add neighbors to lists

Space: O(V + E) because we store a list for each vertex and each edge twice

vs Alternative: Compared to adjacency matrix which uses O(V^2) space, adjacency list is more space efficient for sparse graphs

Edge Cases

Graph with no edges

All adjacency lists remain empty arrays

DSA Javascript

for (let i = 0; i < vertices; i++) { this.adjList.set(i, []); }

Graph with one vertex and no edges

Single vertex has an empty adjacency list

DSA Javascript

for (let i = 0; i < vertices; i++) { this.adjList.set(i, []); }

When to Use This Pattern

When you need to represent graph connections efficiently and want to 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 each edge to both vertices' adjacency lists to keep connections symmetric

Summary

Stores each node's neighbors in a list for quick access.

Use when representing graphs, especially sparse ones, to save space.

The key is each vertex keeps a list of its connected nodes.

Practice

1. What does an adjacency list represent in a graph data structure?

easy

A. A list where each node stores its neighbors

B. A matrix showing connections between nodes

C. A list of all nodes without connections

D. A list of edges sorted by weight

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each node with a list of its neighbors or connected nodes.

2. Step 2: Compare with other graph representations

   An adjacency matrix is a 2D array, not a list of neighbors. Other options describe different structures.

3. Final Answer:

   A list where each node stores its neighbors -> Option A

4. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list always stores neighbors for each node [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking it stores edges sorted by weight
• Assuming it lists nodes without connections only

2. Which of the following is the correct JavaScript syntax to initialize an empty adjacency list for a graph?

easy

A. const graph = [];

B. const graph = new Map();

C. const graph = {};

D. const graph = new Set();

Solution

1. Step 1: Identify suitable data structure for adjacency list

   An adjacency list can be implemented using a Map to store nodes and their neighbors efficiently.

2. Step 2: Check syntax correctness

   new Map() creates an empty map. Arrays or objects can be used but Map is preferred for graph keys. Set is for unique values, not key-value pairs.

3. Final Answer:

   const graph = new Map(); -> Option B

4. Quick Check:

   Use Map() for adjacency list initialization [OK]

Hint: Use Map() to store nodes and neighbors in adjacency list [OK]

Common Mistakes:

• Using Set which does not store key-value pairs
• Using empty array which is less clear for key-value
• Using empty object but Map is better for keys

3. Given the following adjacency list representation in JavaScript, what will be the output of console.log(graph.get('A'));?

const graph = new Map();
graph.set('A', ['B', 'C']);
graph.set('B', ['A', 'D']);
graph.set('C', ['A']);
graph.set('D', ['B']);

medium

A. ['B', 'D']

B. ['A', 'D']

C. ['C', 'D']

D. ['B', 'C']

Solution

1. Step 1: Locate the key 'A' in the adjacency list

   The graph Map has key 'A' with value ['B', 'C'] representing neighbors.

2. Step 2: Understand what graph.get('A') returns

   It returns the array of neighbors for 'A', which is ['B', 'C'].

3. Final Answer:

   ['B', 'C'] -> Option D

4. Quick Check:

   graph.get('A') = ['B', 'C'] [OK]

Hint: graph.get(node) returns neighbors array for that node [OK]

Common Mistakes:

• Confusing neighbors of 'A' with neighbors of 'B'
• Expecting a string instead of array
• Mixing up keys and values in Map

4. The following code attempts to add an edge from node 'A' to node 'D' in an adjacency list but has a bug. What is the error?

const graph = new Map();
graph.set('A', ['B', 'C']);
// Add edge from A to D
graph.get('A').push('D');
console.log(graph.get('A'));

medium

A. graph.get('A') returns undefined causing error

B. Cannot push to array returned by graph.get('A')

C. The code works correctly and adds 'D' to neighbors

D. graph.set should be used instead of push

Solution

1. Step 1: Check if graph.get('A') returns an array

   graph.get('A') returns ['B', 'C'], an array, so push is valid.

2. Step 2: Verify if push adds 'D' correctly

   push('D') adds 'D' to the array, so neighbors become ['B', 'C', 'D'].

3. Final Answer:

   The code works correctly and adds 'D' to neighbors -> Option C

4. Quick Check:

   push on neighbors array works [OK]

Hint: graph.get(node) returns array; push adds neighbor [OK]

Common Mistakes:

• Assuming graph.get returns undefined if key exists
• Thinking push cannot modify array in Map
• Confusing push with set method

5. You want to represent a directed graph with nodes 'X', 'Y', 'Z' where edges are X->Y, Y->Z, and Z->X. Which adjacency list correctly represents this graph in JavaScript?

hard

A. const graph = new Map([['X', ['Y']], ['Y', ['Z']], ['Z', ['X']]]);

B. const graph = new Map([['X', ['Y', 'Z']], ['Y', ['X']], ['Z', ['Y']]]);

C. const graph = new Map([['X', ['Z']], ['Y', ['X']], ['Z', ['Y']]]);

D. const graph = new Map([['X', ['Y']], ['Y', ['X', 'Z']], ['Z', []]]);

Solution

1. Step 1: Understand directed edges

   Edges are X->Y, Y->Z, Z->X, so each node points only to its direct neighbors.

2. Step 2: Match edges to adjacency list entries

   'X' neighbors: ['Y'], 'Y' neighbors: ['Z'], 'Z' neighbors: ['X'] matches const graph = new Map([['X', ['Y']], ['Y', ['Z']], ['Z', ['X']]]); exactly.

3. Final Answer:

   const graph = new Map([['X', ['Y']], ['Y', ['Z']], ['Z', ['X']]]); -> Option A

4. Quick Check:

   Directed edges match adjacency list neighbors [OK]

Hint: Each node's list shows only nodes it points to [OK]

Common Mistakes:

• Including neighbors that don't have edges from the node
• Mixing up direction of edges
• Adding extra neighbors not in edges