Adjacency List Representation in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list after adding edges

What is the printed adjacency list after executing the following TypeScript code?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();

  addVertex(v: number) {
    if (!this.adjacencyList.has(v)) {
      this.adjacencyList.set(v, []);
    }
  }

  addEdge(v: number, w: number) {
    this.adjacencyList.get(v)?.push(w);
    this.adjacencyList.get(w)?.push(v);
  }

  printGraph() {
    this.adjacencyList.forEach((neighbors, vertex) => {
      console.log(`${vertex} -> ${neighbors.join(' -> ')} -> null`);
    });
  }
}

const g = new Graph();
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.printGraph();

A

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

B

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

C

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

D

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

💡 Hint

Remember edges are added in both directions for an undirected graph.

The graph has vertices 1, 2, and 3. Edges connect 1 with 2 and 3. So, vertex 1's neighbors are 2 and 3. Vertices 2 and 3 each have 1 as their neighbor.

❓ Predict Output

intermediate

Adjacency list after removing a vertex

What is the adjacency list printed after removing vertex 2 from the graph below?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();

  addVertex(v: number) {
    if (!this.adjacencyList.has(v)) {
      this.adjacencyList.set(v, []);
    }
  }

  addEdge(v: number, w: number) {
    this.adjacencyList.get(v)?.push(w);
    this.adjacencyList.get(w)?.push(v);
  }

  removeVertex(v: number) {
    this.adjacencyList.delete(v);
    this.adjacencyList.forEach((neighbors) => {
      const index = neighbors.indexOf(v);
      if (index !== -1) {
        neighbors.splice(index, 1);
      }
    });
  }

  printGraph() {
    this.adjacencyList.forEach((neighbors, vertex) => {
      console.log(`${vertex} -> ${neighbors.join(' -> ')} -> null`);
    });
  }
}

const g = new Graph();
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(1, 3);
g.removeVertex(2);
g.printGraph();

A

1 -> 3 -> null
3 -> 1 -> null

B

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

C

1 -> null
3 -> null

D

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

💡 Hint

Removing a vertex also removes it from neighbors' lists.

Vertex 2 is removed. So, it no longer appears as a vertex or neighbor. Vertices 1 and 3 remain connected.

🔧 Debug

advanced

Identify the error in adjacency list edge addition

What error will the following TypeScript code cause when adding an edge?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();

  addVertex(v: number) {
    if (!this.adjacencyList.has(v)) {
      this.adjacencyList.set(v, []);
    }
  }

  addEdge(v: number, w: number) {
    this.adjacencyList.get(v).push(w);
    this.adjacencyList.get(w).push(v);
  }
}

const g = new Graph();
g.addVertex(1);
g.addEdge(1, 2);

A SyntaxError: Unexpected token '.'

B No error, edge added successfully

C TypeError: Cannot read property 'push' of undefined

D ReferenceError: g is not defined

💡 Hint

Check if vertices exist before adding edges.

Vertex 2 was never added, so adjacencyList.get(2) returns undefined. Calling push on undefined causes a TypeError.

🧠 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 lists store only existing edges, while adjacency matrices allocate space for all possible edges.

B Adjacency matrices store edges as linked lists, which use more memory than arrays.

C Adjacency lists require a fixed-size 2D array, increasing memory usage.

D Adjacency matrices compress edges, making them less memory efficient.

💡 Hint

Think about how each structure stores edges.

Adjacency lists keep only neighbors for each vertex, so they use memory proportional to edges. Adjacency matrices allocate space for all vertex pairs, even if no edge exists.

🚀 Application

expert

Resulting adjacency list after multiple operations

After running the following TypeScript code, what is the printed adjacency list?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = new Map();

  addVertex(v: number) {
    if (!this.adjacencyList.has(v)) {
      this.adjacencyList.set(v, []);
    }
  }

  addEdge(v: number, w: number) {
    this.adjacencyList.get(v)?.push(w);
    this.adjacencyList.get(w)?.push(v);
  }

  removeEdge(v: number, w: number) {
    this.adjacencyList.set(v, this.adjacencyList.get(v)?.filter(x => x !== w) || []);
    this.adjacencyList.set(w, this.adjacencyList.get(w)?.filter(x => x !== v) || []);
  }

  printGraph() {
    this.adjacencyList.forEach((neighbors, vertex) => {
      console.log(`${vertex} -> ${neighbors.join(' -> ')} -> null`);
    });
  }
}

const g = new Graph();
g.addVertex(1);
g.addVertex(2);
g.addVertex(3);
g.addVertex(4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 4);
g.removeEdge(1, 3);
g.printGraph();

A

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

B

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

C

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

D

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

💡 Hint

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

Edges added: (1,2), (1,3), (2,4), (3,4). Then edge (1,3) is removed. So 1's neighbors are only 2, 3's neighbors no longer include 1.

Practice

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

easy

A. A list of all nodes without connections

B. A matrix showing distances between nodes

C. A queue of nodes to visit next

D. A list where each node stores its connected neighbors

Solution

1. Step 1: Understand adjacency list concept

   An adjacency list stores each node with a list of its neighbors, showing direct connections.

2. Step 2: Compare options with definition

   Only A list where each node stores its connected neighbors correctly describes this structure; others describe different concepts.

3. Final Answer:

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

4. Quick Check:

   Adjacency list = neighbors list [OK]

Hint: Adjacency list always stores neighbors per node [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix
• Thinking it stores distances instead of neighbors
• Assuming it is a queue or unrelated structure

2. Which of the following is the correct TypeScript syntax to declare an adjacency list for a graph with nodes as numbers?

easy

A. const graph: number[][] = [];

B. const graph: Map = new Map();

C. const graph: Record = {};

D. const graph: Array<number> = [];

Solution

1. Step 1: Identify adjacency list type

   An adjacency list maps each node (number) to an array of connected nodes (number[]).

2. Step 2: Match TypeScript syntax

   Map correctly represents this; others are incorrect types or structures.

3. Final Answer:

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

4. Quick Check:

   Map = adjacency list [OK]

Hint: Use Map with number keys and array values for adjacency list [OK]

Common Mistakes:

• Using Record which maps to single number, not array
• Using number[][] without keys for nodes
• Using Array<number> which is just a list, not adjacency

3. Given the following TypeScript code, what is the output after adding edges?

const graph: Map = new Map();
graph.set(1, [2, 3]);
graph.set(2, [1]);
graph.set(3, [1, 4]);
graph.set(4, [3]);
console.log(graph.get(3));

medium

A. [2, 3]

B. [3, 4]

C. [1, 4]

D. undefined

Solution

1. Step 1: Trace graph.set calls

   Node 3 is set with neighbors [1, 4].

2. Step 2: Check graph.get(3)

   Returns the array [1, 4] assigned to node 3.

3. Final Answer:

   [1, 4] -> Option C

4. Quick Check:

   graph.get(3) = [1, 4] [OK]

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

Common Mistakes:

• Confusing neighbors of node 3 with node 1 or 2
• Expecting undefined if not careful with set calls
• Mixing up array contents order

4. Identify the error in this TypeScript adjacency list code snippet:

const graph: Map = new Map();
graph.set(1, [2]);
graph.set(2, [1]);
graph.get(3).push(1);

medium

A. graph.get(3) returns undefined, so push causes error

B. Map keys must be strings, not numbers

C. graph.set should use arrays of strings, not numbers

D. Missing initialization of graph variable

Solution

1. Step 1: Check graph.get(3) call

   Node 3 was never set, so graph.get(3) returns undefined.

2. Step 2: Understand push on undefined

   Calling push on undefined causes runtime error.

3. Final Answer:

   graph.get(3) returns undefined, so push causes error -> Option A

4. Quick Check:

   Accessing unset key returns undefined [OK]

Hint: Check if key exists before pushing to adjacency list [OK]

Common Mistakes:

• Assuming graph.get(3) returns empty array automatically
• Thinking Map keys must be strings (numbers are allowed)
• Ignoring runtime error from push on undefined

5. You want to represent a directed graph with nodes 1 to 4 using an adjacency list in TypeScript. Which code correctly adds an edge from node 2 to node 4 without affecting other edges?

const graph: Map = new Map();
graph.set(1, [2]);
graph.set(2, [3]);
graph.set(3, []);
graph.set(4, []);
// Add edge from 2 to 4 here

hard

A. graph.get(2)?.push(4);

B. graph.set(2, [4]);

C. graph.set(4, [2]);

D. graph.get(4)?.push(2);

Solution

1. Step 1: Understand existing edges

   Node 2 currently has neighbors [3]. We want to add 4 without removing 3.

2. Step 2: Choose correct method to add edge

   Using graph.get(2)?.push(4) adds 4 to existing array, preserving [3]. graph.set(2, [4]) replaces neighbors, removing 3.

3. Final Answer:

   graph.get(2)?.push(4); -> Option A

4. Quick Check:

   Use push to add edge without overwriting [OK]

Hint: Use push on existing neighbors to add edges safely [OK]

Common Mistakes:

• Overwriting neighbors array with set instead of pushing
• Adding edge to wrong node
• Confusing direction of edge in directed graph