Adjacency List vs Matrix When to Choose Which in DSA Typescript - Expert Trade-off Analysis

Overview - Adjacency List vs Matrix When to Choose Which

What is it?

Graphs are ways to show connections between things. Two common ways to store these connections are adjacency lists and adjacency matrices. An adjacency list keeps a list of neighbors for each point, while an adjacency matrix uses a grid to mark if two points connect. Both help us understand and work with networks, but they do it differently.

Why it matters

Choosing the right way to store connections can make programs faster and use less memory. If we pick the wrong one, our program might slow down or use too much space, especially with big networks. Knowing when to use each helps build better apps, like social networks or maps, that run smoothly and save resources.

Where it fits

Before this, you should know what graphs are and basic data structures like arrays and lists. After this, you can learn about graph algorithms like searching or shortest paths, which use these storage methods to work efficiently.

Mental Model

Core Idea

Adjacency lists store neighbors as lists for each node, saving space for sparse graphs, while adjacency matrices use a fixed grid to quickly check connections, better for dense graphs.

Think of it like...

Imagine a city map: adjacency lists are like having a list of direct bus routes from each stop, while adjacency matrices are like a big table showing if any two stops have a direct route between them.

Graph with 4 nodes:

Adjacency List:
1: 2 -> 4
2: 1 -> 3
3: 2
4: 1

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

Build-Up - 7 Steps

1

Foundation

Understanding Graph Connections

Concept: Graphs show how things connect using points (nodes) and lines (edges).

A graph has nodes representing items and edges showing connections. For example, in a friendship network, nodes are people and edges are friendships. We need ways to store these connections so computers can use them.

Result

You know what a graph is and why storing connections matters.

Understanding what a graph represents is the base for choosing how to store its connections.

2

Foundation

Basics of Adjacency List and Matrix

Concept: Two main ways to store graph connections: lists and matrices.

Adjacency list stores for each node a list of neighbors. Adjacency matrix uses a 2D grid where rows and columns are nodes, and cells show if nodes connect (1) or not (0).

Result

You can describe both storage methods and their basic structure.

Knowing these two forms helps you see their strengths and weaknesses.

3

Intermediate

Memory Use in Sparse vs Dense Graphs

🤔Before reading on: Do you think adjacency lists or matrices use less memory for graphs with few connections? Commit to your answer.

Concept: Memory use depends on how many edges exist compared to nodes.

Sparse graphs have few edges compared to nodes. Adjacency lists only store existing edges, saving space. Matrices always store all possible pairs, using more memory. Dense graphs have many edges, so matrices can be efficient.

Result

You understand when adjacency lists save memory and when matrices might not.

Knowing memory use helps pick the right storage for your graph size and connection density.

4

Intermediate

Speed of Checking Connections

🤔Before reading on: Which is faster to check if two nodes connect, adjacency list or matrix? Commit to your answer.

Concept: Checking if two nodes connect differs in speed between lists and matrices.

In adjacency matrices, checking connection is quick: just look at one cell. In adjacency lists, you must search the list of neighbors, which can take longer if the list is big.

Result

You see adjacency matrices offer faster connection checks.

Understanding speed trade-offs helps optimize algorithms needing many connection checks.

5

Intermediate

Adding and Removing Edges

🤔Before reading on: Is it easier to add or remove edges in adjacency lists or matrices? Commit to your answer.

Concept: Operations like adding or removing edges have different costs in each structure.

In adjacency matrices, adding or removing edges is simple: update one cell. In adjacency lists, you add or remove from a list, which can be slower if the list is long or unordered.

Result

You understand operational differences affecting performance.

Knowing operation costs guides data structure choice for dynamic graphs.

6

Advanced

Choosing Based on Graph Type and Algorithm

🤔Before reading on: Would you choose adjacency list or matrix for a social network with millions of users but few connections each? Commit to your answer.

Concept: Graph type and algorithm needs influence storage choice.

Sparse graphs like social networks benefit from adjacency lists to save memory. Dense graphs or algorithms needing fast connection checks, like Floyd-Warshall, prefer adjacency matrices. Some algorithms work better with one structure.

Result

You can match graph and algorithm types to storage methods.

Understanding this match improves algorithm efficiency and resource use.

7

Expert

Hybrid and Space-Optimized Approaches

🤔Before reading on: Do you think combining adjacency lists and matrices can improve performance? Commit to your answer.

Concept: Advanced systems sometimes combine both or optimize storage for special cases.

Hybrid structures use adjacency lists for most nodes but matrices for dense parts. Compressed sparse row (CSR) formats store large sparse graphs efficiently. These methods balance speed and memory for real-world large graphs.

Result

You learn about practical optimizations beyond basic structures.

Knowing advanced storage techniques prepares you for handling big, complex graphs in production.

Under the Hood

Adjacency lists store pointers or references to neighbor nodes in dynamic arrays or linked lists, allowing flexible size per node. Adjacency matrices allocate a fixed-size 2D array where each cell represents a possible edge, enabling constant-time access but fixed memory use regardless of actual edges.

Why designed this way?

Adjacency lists were designed to save memory when graphs have few edges, avoiding storing empty connections. Matrices were designed for quick edge lookup and simple implementation, especially useful when graphs are dense or small.

Adjacency List Structure:
Node 1 -> [Node 2] -> [Node 4] -> null
Node 2 -> [Node 1] -> [Node 3] -> null
Node 3 -> [Node 2] -> null
Node 4 -> [Node 1] -> null

Adjacency Matrix Structure:
      1  2  3  4
   1 [0, 1, 0, 1]
   2 [1, 0, 1, 0]
   3 [0, 1, 0, 0]
   4 [1, 0, 0, 0]

Myth Busters - 4 Common Misconceptions

Quick: Do you think adjacency matrices always use less memory than adjacency lists? Commit yes or no.

Common Belief: Adjacency matrices always use less memory because they are simple grids.

Reality: Adjacency matrices use more memory for sparse graphs because they store all possible edges, even if many don't exist.

Why it matters: Using matrices for sparse graphs wastes memory and can slow down programs.

Quick: Is checking if two nodes connect always faster with adjacency lists? Commit yes or no.

Common Belief: Adjacency lists are always faster to check connections because they store neighbors directly.

Reality: Adjacency matrices provide constant-time checks by direct indexing, which is faster than searching lists.

Why it matters: Choosing lists for speed-critical connection checks can cause slower performance.

Quick: Can adjacency lists handle dense graphs efficiently? Commit yes or no.

Common Belief: Adjacency lists are always better, no matter how dense the graph is.

Reality: For dense graphs, adjacency lists can become large and slow, making matrices more efficient.

Why it matters: Using lists for dense graphs can cause slow operations and complex code.

Quick: Do adjacency matrices only work for unweighted graphs? Commit yes or no.

Common Belief: Adjacency matrices cannot store weights, only presence or absence of edges.

Reality: Adjacency matrices can store weights by placing numbers instead of 0/1 in cells.

Why it matters: Misunderstanding this limits the use of matrices in weighted graph problems.

Expert Zone

1

Adjacency lists can be implemented with hash maps for faster neighbor lookups, blending list and matrix benefits.

2

Sparse matrix representations like Compressed Sparse Row (CSR) optimize memory and speed for very large graphs.

3

In parallel computing, adjacency matrices allow simpler partitioning of data for concurrent processing.

When NOT to use

Avoid adjacency matrices for very large sparse graphs due to high memory use; prefer adjacency lists or compressed sparse formats. Avoid adjacency lists for dense graphs or when constant-time edge checks are critical; prefer matrices.

Production Patterns

Social networks use adjacency lists for memory efficiency. Routing algorithms in maps use adjacency matrices for fast edge checks. Hybrid systems combine both for large-scale graph processing in search engines and recommendation systems.

Connections

Sparse Matrix Storage

Builds-on adjacency list concepts by compressing storage for large sparse graphs.

Understanding adjacency lists helps grasp sparse matrix formats used in scientific computing and big data.

Database Indexing

Shares the idea of efficient lookup structures to speed queries.

Knowing adjacency matrices' constant-time access parallels how database indexes speed data retrieval.

Neural Networks

Uses weighted adjacency matrices to represent connections between neurons.

Recognizing adjacency matrices in graphs helps understand how neural networks store and process connections.

Common Pitfalls

#1 Using adjacency matrix for a huge sparse graph causing memory overflow.

Wrong approach:

const matrix = new Array(1000000).fill(0).map(() => new Array(1000000).fill(0));

Correct approach:

const adjacencyList: Map = new Map(); // Store only existing edges

Root cause:

Not realizing adjacency matrices allocate memory for all possible edges regardless of actual connections.

#2 Checking connection by scanning entire adjacency list instead of direct access.

Wrong approach:

function hasEdge(list: number[], target: number) { for (let node of list) { if (node === target) return true; } return false; }

Correct approach:

function hasEdge(matrix: number[][], from: number, to: number) { return matrix[from][to] === 1; }

Root cause:

Ignoring adjacency matrix's advantage of constant-time edge lookup.

#3 Adding duplicate edges in adjacency list causing incorrect graph representation.

Wrong approach:

adjacencyList.get(node).push(neighbor); // without checking if neighbor exists

Correct approach:

if (!adjacencyList.get(node).includes(neighbor)) { adjacencyList.get(node).push(neighbor); }

Root cause:

Not handling duplicates leads to wrong graph structure and bugs.

Key Takeaways

Adjacency lists save memory for graphs with few connections by storing only existing edges.

Adjacency matrices use fixed memory but allow fast checks if two nodes connect.

Choose adjacency lists for large, sparse graphs and adjacency matrices for small or dense graphs.

Understanding operation costs like adding or checking edges helps pick the right structure.

Advanced systems combine or optimize these structures for big, real-world graphs.

Practice

1. Which data structure is generally more space-efficient for representing a graph with very few edges compared to the number of vertices?

easy

A. Adjacency List

B. Adjacency Matrix

C. Edge List

D. Incidence Matrix

Solution

1. Step 1: Understand graph density

   Sparse graphs have few edges compared to vertices, so storing all possible edges wastes space.

2. Step 2: Compare space usage of adjacency list and matrix

   Adjacency list stores only existing edges, using less space for sparse graphs. Adjacency matrix always uses space for all possible edges.

3. Final Answer:

   Adjacency List -> Option A

4. Quick Check:

   Sparse graph = Adjacency List [OK]

Hint: Sparse graph? Use adjacency list for less space [OK]

Common Mistakes:

• Choosing adjacency matrix for sparse graphs
• Confusing edge count with vertex count
• Ignoring space complexity differences

2. Which of the following is the correct TypeScript syntax to declare an adjacency matrix for a graph with 3 vertices initialized with zeros?

easy

A. const matrix: number[][] = new Array(3).fill(new Array(3).fill(0));

B. const matrix: number[] = [0,0,0];

C. const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]];

D. const matrix: number[][] = Array(3).map(() => Array(3).fill(0));

Solution

1. Step 1: Understand adjacency matrix type

   An adjacency matrix is a 2D array (array of arrays) of numbers representing edges.

2. Step 2: Check initialization correctness

   const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]]; explicitly creates a 3x3 matrix with zeros. const matrix: number[][] = new Array(3).fill(new Array(3).fill(0)); uses fill with the same inner array reference, causing bugs. const matrix: number[][] = Array(3).map(() => Array(3).fill(0)); uses map on empty array, which won't work as expected. const matrix: number[] = [0,0,0]; is 1D array, not matrix.

3. Final Answer:

   const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]]; -> Option C

4. Quick Check:

   Explicit 2D array with zeros = const matrix: number[][] = [[0,0,0],[0,0,0],[0,0,0]]; [OK]

Hint: Use explicit 2D array for adjacency matrix initialization [OK]

Common Mistakes:

• Using fill with nested arrays causing shared references
• Declaring 1D array instead of 2D
• Using map on empty array without initialization

3. Given the following adjacency list representation of a graph in TypeScript:

const graph = {
  0: [1, 2],
  1: [2],
  2: [0, 3],
  3: []
};
console.log(graph[2]);

What will be the output?

medium

A. [2]

B. [1, 2]

C. undefined

D. [0, 3]

Solution

1. Step 1: Identify the adjacency list for vertex 2

   In the graph object, key '2' maps to the array [0, 3].

2. Step 2: Understand console.log output

   Logging graph[2] prints the array [0, 3] representing edges from vertex 2.

3. Final Answer:

   [0, 3] -> Option D

4. Quick Check:

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

Hint: Access adjacency list by vertex key to get connected nodes [OK]

Common Mistakes:

• Confusing keys and values in adjacency list
• Expecting adjacency matrix output
• Assuming undefined for existing keys

4. Consider this TypeScript code snippet for creating an adjacency matrix for a graph with 3 vertices:

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

What is the problem with this code?

medium

A. All rows refer to the same inner array, so all rows change when one element changes

B. The matrix is not initialized with zeros

C. The matrix is not a 2D array

D. The size variable is not used correctly

Solution

1. Step 1: Analyze the fill method usage

   Using fill with new Array(size).fill(0) creates one inner array and fills outer array with references to the same inner array.

2. Step 2: Understand effect of modifying one element

   Changing matrix[0][1] changes that element in all rows because they share the same inner array reference.

3. Final Answer:

   All rows refer to the same inner array, so all rows change when one element changes -> Option A

4. Quick Check:

   Shared inner array reference causes unexpected changes [OK]

Hint: Avoid fill with nested arrays; use map to create separate arrays [OK]

Common Mistakes:

• Thinking fill creates separate inner arrays
• Ignoring shared reference problem
• Assuming matrix is 1D array

5. You need to represent a dense graph with 1000 vertices where you frequently check if an edge exists between any two vertices. Which representation is best and why?

hard

A. Adjacency List, because it uses less space for dense graphs

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

C. Edge List, because it is fastest for dense graphs

D. Incidence Matrix, because it uses less space than adjacency matrix

Solution

1. Step 1: Understand graph density and operation needs

   Dense graph means many edges; checking edge existence frequently requires fast lookup.

2. Step 2: Compare adjacency list and matrix for edge checks

   Adjacency matrix allows direct O(1) access to check if edge exists between two vertices. Adjacency list requires searching neighbors, which can be slower in dense graphs.

3. Step 3: Consider space tradeoff

   Though adjacency matrix uses more space, for dense graphs this is acceptable and beneficial for speed.

4. Final Answer:

   Adjacency Matrix, because it allows O(1) edge existence checks -> Option B

5. Quick Check:

   Dense graph + frequent edge check = Adjacency Matrix [OK]

Hint: Dense graph + frequent edge check? Use adjacency matrix [OK]

Common Mistakes:

• Choosing adjacency list for dense graphs needing fast edge checks
• Ignoring time complexity of edge existence queries
• Confusing edge list with adjacency matrix benefits