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

The Big Idea

Discover how picking the right graph storage can save you from slow, clunky programs!

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 mark if they are friends or not.

This list grows huge and hard to manage as the school size increases.

The Problem

Writing down every possible pair wastes a lot of space because most students have only a few friends.

It becomes slow to find who is friends with whom because you check many empty spots.

Updating friendships means changing many entries, which is error-prone.

The Solution

Using an adjacency list, you only write down actual friendships, saving space and time.

It is easier to add or remove friends because you only update the list for that student.

For dense friendships, adjacency matrix is faster to check if two students are friends.

Before vs After

✗ Before

int matrix[1000][1000] = {0}; // store all pairs
// check friendship
if(matrix[studentA][studentB] == 1) { /* friends */ }

✓ After

struct Node { int friend_id; struct Node* next; };
struct Node* adjacencyList[1000] = {NULL};
// check friendship by traversing list of studentA

What It Enables

Choosing the right way to store connections lets you handle big networks efficiently and quickly.

Real Life Example

Social media platforms use adjacency lists to store user connections because most users have few friends compared to total users.

Key Takeaways

Adjacency matrix uses more space but is quick for dense graphs.

Adjacency list saves space and is better for sparse graphs.

Choosing the right structure improves speed and memory use.