Adjacency List vs Matrix When to Choose Which in DSA Javascript - Trade-offs & Analysis

Mental Model

Graphs can be stored in two main ways: adjacency lists store neighbors for each node, adjacency matrices use a grid to mark connections.

Analogy: Think of a social group: adjacency list is like each person having a list of their friends, adjacency matrix is like a big table where you mark if two people are friends or not.

Adjacency List:
0: 1 -> 2 -> null
1: 0 -> 3 -> null
2: 0 -> null
3: 1 -> null

Adjacency Matrix:
   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 0]
3 [0 1 0 0]

Dry Run Walkthrough

Input: Graph with 4 nodes: edges 0-1, 0-2, 1-3

Goal: Show how adjacency list and matrix represent the same graph and when each is better

Step 1: Create adjacency list for node 0 with neighbors 1 and 2

0: 1 -> 2 -> null
1: null
2: null
3: null

Why: We list neighbors directly for node 0 to save space

Step 2: Add neighbors for node 1: 0 and 3

0: 1 -> 2 -> null
1: 0 -> 3 -> null
2: null
3: null

Why: Each node keeps only its connected nodes

Step 3: Add neighbor for node 2: 0

0: 1 -> 2 -> null
1: 0 -> 3 -> null
2: 0 -> null
3: null

Why: Node 2 connects back to 0

Step 4: Add neighbor for node 3: 1

0: 1 -> 2 -> null
1: 0 -> 3 -> null
2: 0 -> null
3: 1 -> null

Why: Node 3 connects back to 1

Step 5: Create adjacency matrix with 4x4 grid initialized to 0

   0 1 2 3
0 [0 0 0 0]
1 [0 0 0 0]
2 [0 0 0 0]
3 [0 0 0 0]

Why: Matrix starts empty, no edges marked

Step 6: Mark edges in matrix: 0-1 and 1-0 to 1

   0 1 2 3
0 [0 1 0 0]
1 [1 0 0 0]
2 [0 0 0 0]
3 [0 0 0 0]

Why: Matrix marks connections symmetrically for undirected graph

Step 7: Mark edges 0-2 and 2-0 to 1

   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 0]
2 [1 0 0 0]
3 [0 0 0 0]

Why: Add more edges to matrix

Step 8: Mark edges 1-3 and 3-1 to 1

   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 0]
3 [0 1 0 0]

Why: Complete matrix representation

Result:

Adjacency List:
0: 1 -> 2 -> null
1: 0 -> 3 -> null
2: 0 -> null
3: 1 -> null

Adjacency Matrix:
   0 1 2 3
0 [0 1 1 0]
1 [1 0 0 1]
2 [1 0 0 0]
3 [0 1 0 0]

Annotated Code

DSA Javascript

class Graph {
  constructor(size) {
    this.size = size;
    this.adjList = new Array(size).fill(null).map(() => []);
    this.adjMatrix = Array.from({ length: size }, () => new Array(size).fill(0));
  }

  addEdgeList(u, v) {
    this.adjList[u].push(v);
    this.adjList[v].push(u); // undirected
  }

  addEdgeMatrix(u, v) {
    this.adjMatrix[u][v] = 1;
    this.adjMatrix[v][u] = 1; // undirected
  }

  printAdjList() {
    for (let i = 0; i < this.size; i++) {
      let neighbors = this.adjList[i].join(' -> ');
      console.log(`${i}: ${neighbors} -> null`);
    }
  }

  printAdjMatrix() {
    console.log('   ' + [...Array(this.size).keys()].join(' '));
    for (let i = 0; i < this.size; i++) {
      console.log(i + ' [' + this.adjMatrix[i].join(' ') + ']');
    }
  }
}

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

console.log('Adjacency List:');
g.printAdjList();

// Add same edges to matrix
const g2 = new Graph(4);
g2.addEdgeMatrix(0, 1);
g2.addEdgeMatrix(0, 2);
g2.addEdgeMatrix(1, 3);

console.log('\nAdjacency Matrix:');
g2.printAdjMatrix();

this.adjList[u].push(v); this.adjList[v].push(u); // undirected

Add neighbors to adjacency list for both nodes to represent undirected edge

this.adjMatrix[u][v] = 1; this.adjMatrix[v][u] = 1; // undirected

Mark edges in adjacency matrix symmetrically for undirected graph

for (let i = 0; i < this.size; i++) { let neighbors = this.adjList[i].join(' -> '); console.log(`${i}: ${neighbors} -> null`); }

Print adjacency list showing neighbors for each node

for (let i = 0; i < this.size; i++) { console.log(i + ' [' + this.adjMatrix[i].join(' ') + ']'); }

Print adjacency matrix row by row

Output

Adjacency List:

0: 1 -> 2 -> null

1: 0 -> 3 -> null

2: 0 -> null

3: 1 -> null



Adjacency Matrix:

   0 1 2 3

0 [0 1 1 0]

1 [1 0 0 1]

2 [1 0 0 0]

3 [0 1 0 0]

Complexity Analysis

Time: O(V + E) for adjacency list because we store only edges; O(V^2) for adjacency matrix because we store all possible edges

Space: O(V + E) for adjacency list as it stores neighbors only; O(V^2) for adjacency matrix as it stores a full grid

vs Alternative: Adjacency list is better for sparse graphs with fewer edges; adjacency matrix is better for dense graphs or when quick edge lookup is needed

Edge Cases

Empty graph with no edges

Adjacency list has empty arrays; adjacency matrix is all zeros

DSA Javascript

this.adjList[u].push(v);

Graph with one node and no edges

Adjacency list has one empty array; adjacency matrix is 1x1 zero

DSA Javascript

this.adjList[u].push(v);

Graph with self-loop edge (node connected to itself)

Adjacency list includes node itself in neighbors; adjacency matrix marks diagonal as 1

DSA Javascript

this.adjList[u].push(v);

When to Use This Pattern

When a problem involves graph representation and you need to choose storage, think about graph size and edge density to pick adjacency list or matrix for efficiency.

Common Mistakes

Mistake: Using adjacency matrix for very large sparse graphs causing high memory use
Fix: Use adjacency list to store only existing edges and save space

Mistake: Forgetting to mark both directions in undirected graph edges
Fix: Add edges symmetrically in both adjacency list and matrix

Summary

Shows two ways to store graphs: adjacency list stores neighbors, adjacency matrix uses a grid.

Use adjacency list for sparse graphs and adjacency matrix for dense graphs or fast edge checks.

Adjacency list saves space by storing only existing edges; adjacency matrix uses fixed space but allows quick edge lookup.

Practice

1. Which data structure is generally better for representing a graph with many nodes but few edges?

easy

A. Adjacency Matrix

B. Adjacency List

C. Array

D. Stack

Solution

1. Step 1: Understand graph density

   A graph with many nodes but few edges is called a sparse graph.

2. Step 2: Choose efficient representation for sparse graphs

   Adjacency lists store only existing edges, saving space for sparse graphs.

3. Final Answer:

   Adjacency List -> Option B

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graphs use adjacency lists for space efficiency [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes space
• Confusing adjacency list with adjacency matrix
• Thinking arrays or stacks represent graphs directly

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

easy

A. const graph = [[], [], []];

B. const graph = [[0,0,0],[0,0,0],[0,0,0]];

C. const graph = new Array(3).fill([]);

D. const graph = {};

Solution

1. Step 1: Understand adjacency list structure

   An adjacency list is an array where each element is an array of neighbors.

2. Step 2: Check each option

   const graph = [[], [], []]; creates separate empty arrays for each node. const graph = new Array(3).fill([]); fills with the same array reference, causing bugs.

3. Final Answer:

   const graph = [[], [], []]; -> Option A

4. Quick Check:

   Separate empty arrays = const graph = [[], [], []]; [OK]

Hint: Use separate empty arrays, not fill with one array [OK]

Common Mistakes:

• Using fill([]) which shares the same array reference
• Using adjacency matrix syntax for adjacency list
• Using an object instead of array for adjacency list

3. What will be the output of the following JavaScript code snippet?

const graph = [
  [1, 2],
  [0],
  [0]
];
console.log(graph[0]);

medium

A. [0, 1, 2]

B. [0]

C. [1, 2]

D. undefined

Solution

1. Step 1: Understand the adjacency list structure

   graph[0] contains the neighbors of node 0, which are nodes 1 and 2.

2. Step 2: Check the console.log output

   Logging graph[0] prints the array [1, 2].

3. Final Answer:

   [1, 2] -> Option C

4. Quick Check:

   graph[0] = [1, 2] [OK]

Hint: Access adjacency list by index to get neighbors [OK]

Common Mistakes:

• Confusing adjacency list with adjacency matrix output
• Expecting all nodes instead of neighbors
• Mistaking graph[0] as undefined

4. Identify the error in this adjacency matrix initialization code for a graph with 3 nodes:

const graph = new Array(3).fill(new Array(3).fill(0));
graph[0][1] = 1;
console.log(graph);

medium

A. The inner arrays are shared references causing all rows to change

B. The graph array is not initialized with zeros

C. The syntax for new Array is incorrect

D. The assignment graph[0][1] = 1 is invalid

Solution

1. Step 1: Analyze array initialization

   Using fill with new Array(3).fill(0) creates one inner array shared by all rows.

2. Step 2: Effect of modifying graph[0][1]

   Changing graph[0][1] changes the same element in all rows because they reference the same array.

3. Final Answer:

   The inner arrays are shared references causing all rows to change -> Option A

4. Quick Check:

   Shared inner arrays cause unexpected changes [OK]

Hint: Use loop or map to create separate inner arrays [OK]

Common Mistakes:

• Assuming fill creates independent arrays
• Ignoring shared reference problem
• Thinking syntax is wrong instead of logic

5. You have a graph with 1000 nodes and about 10,000 edges. Which representation is more efficient in terms of memory and why? Choose the best option.

hard

A. Adjacency Matrix, because it allows O(1) edge checks

B. Adjacency List, because it stores all possible edges

C. Adjacency Matrix, because it is simpler to implement

D. Adjacency List, because it uses memory proportional to edges

Solution

1. Step 1: Calculate graph density

   Maximum edges for 1000 nodes is 1,000,000 (1000*1000). 10,000 edges is sparse.

2. Step 2: Compare memory usage

   Adjacency matrix uses memory for all possible edges (1,000,000). Adjacency list uses memory proportional to actual edges (10,000).

3. Step 3: Choose efficient representation

   Adjacency list is more memory efficient for sparse graphs.

4. Final Answer:

   Adjacency List, because it uses memory proportional to edges -> Option D

5. Quick Check:

   Sparse graph = Adjacency List memory efficient [OK]

Hint: Sparse large graph? Use adjacency list for memory [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs wastes memory
• Confusing simplicity with efficiency
• Thinking adjacency list stores all possible edges