Adjacency List vs Matrix When to Choose Which in DSA Typescript - Why the Distinction Matters

The Big Idea

Discover how a simple choice in storing connections can make your programs lightning fast or painfully slow!

The Scenario

Imagine you want to keep track of friendships in a large school. You try to write down every possible pair of students and whether they are friends or not on a big sheet of paper.

This sheet quickly becomes huge and hard to manage, especially when most students only have a few friends.

The Problem

Writing down every possible connection wastes a lot of space and time. It becomes slow to find who is friends with whom because you have to look through many empty spots.

Also, updating the list when friendships change is tiring and error-prone.

The Solution

Using an adjacency list, you only write down the friends each student actually has. This saves space and makes it faster to find and update friendships.

For smaller groups or when you need to quickly check if two students are friends, an adjacency matrix works well because it gives instant answers.

Before vs After

✗ Before

const matrix = Array(numStudents).fill(0).map(() => Array(numStudents).fill(false));
matrix[0][1] = true; // Mark friendship
// Checking friendship requires direct access

✓ After

const adjacencyList: Map<number, number[]> = new Map();
adjacencyList.set(0, [1]); // Student 0 is friends with 1
// Checking friendship by looking up list of friends

What It Enables

Choosing the right way to store connections lets you handle big or small networks efficiently and keeps your program fast and simple.

Real Life Example

Social media platforms use adjacency lists to store user connections because most users have a limited number of friends, saving huge amounts of memory.

But for small games or puzzles where quick checks of connections are needed, adjacency matrices are preferred.

Key Takeaways

Adjacency lists save space when connections are few.

Adjacency matrices give quick answers for dense connections.

Choosing the right one depends on the size and type of your network.