Adjacency List vs Matrix When to Choose Which in DSA Typescript - Visual Comparison

Concept Flow - Adjacency List vs Matrix When to Choose Which

Start: Need to represent graph

↓

Check graph size and edges

↓

Use List

↓

Less space

↓

Slower edge check

↓

Good for large graphs

↓

End

Decide graph representation by checking if graph is sparse or dense, then choose adjacency list or matrix accordingly.

Execution Sample

DSA Typescript

const graphList = new Map<number, number[]>();
graphList.set(1, [2,3]);
graphList.set(2, [1]);
graphList.set(3, [1]);

const graphMatrix = [
  [0,1,1],
  [1,0,0],
  [1,0,0]
];

Shows a simple graph with 3 nodes represented as adjacency list and adjacency matrix.

Execution Table

Step	Operation	Graph Type	Data Structure State	Memory Use	Edge Check Speed	Visual State
1	Initialize graph with 3 nodes and 2 edges	Adjacency List	{1: [2,3], 2: [1], 3: [1]}	Low (O(V+E))	Slower (need to search lists)	1 -> 2,3; 2 -> 1; 3 -> 1
2	Initialize graph with 3 nodes and 2 edges	Adjacency Matrix	[[0,1,1],[1,0,0],[1,0,0]]	Higher (O(V^2))	Faster (direct index)	1 2 3 1 0 1 1 2 1 0 0 3 1 0 0
3	Check if edge exists between 1 and 3	Adjacency List	Same	Same	Search list of node 1	Check if 3 in [2,3] → Yes
4	Check if edge exists between 1 and 3	Adjacency Matrix	Same	Same	Direct access matrix[0][2]	Value is 1 → Yes
5	Add edge between 2 and 3	Adjacency List	{1: [2,3], 2: [1,3], 3: [1,2]}	Low	Slower	1 -> 2,3; 2 -> 1,3; 3 -> 1,2
6	Add edge between 2 and 3	Adjacency Matrix	[[0,1,1],[1,0,1],[1,1,0]]	Higher	Faster	1 2 3 1 0 1 1 2 1 0 1 3 1 1 0
7	Decide representation for large sparse graph	Decision	Prefer adjacency list	Efficient	Acceptable	Use list for less memory
8	Decide representation for small dense graph	Decision	Prefer adjacency matrix	Memory not a problem	Fast edge checks	Use matrix for speed
9	End	N/A	N/A	N/A	N/A	Representation chosen based on graph type

💡 Stop after deciding best representation based on graph size and density

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 5	After Step 6	Final
graphList	empty Map	{1:[2,3],2:[1],3:[1]}	{1:[2,3],2:[1],3:[1]}	{1:[2,3],2:[1,3],3:[1,2]}	{1:[2,3],2:[1,3],3:[1,2]}	{1:[2,3],2:[1,3],3:[1,2]}
graphMatrix	empty array	N/A	[[0,1,1],[1,0,0],[1,0,0]]	[[0,1,1],[1,0,0],[1,0,0]]	[[0,1,1],[1,0,1],[1,1,0]]	[[0,1,1],[1,0,1],[1,1,0]]

Key Moments - 3 Insights

Why does adjacency list use less memory for sparse graphs?

Because adjacency list stores only existing edges, as shown in step 1 and 5 in execution_table, it uses memory proportional to vertices plus edges (O(V+E)), unlike matrix which uses O(V^2) regardless.

Why is edge check faster in adjacency matrix?

In step 4 and 6, adjacency matrix allows direct access to check if edge exists using indices, making it O(1), while adjacency list requires searching the list which is slower.

When should we prefer adjacency matrix despite higher memory?

As in step 8, for small dense graphs where memory is not a big concern, adjacency matrix is preferred for its fast edge lookup and simpler implementation.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the method used to check edge between nodes 1 and 3 in adjacency list?

A Direct index access in matrix

B Search node 1's adjacency list for 3

C Check all nodes for edge

D Use a boolean matrix

💡 Hint

Refer to execution_table row 3 under 'Edge Check Speed' and 'Visual State'

At which step does adjacency matrix add an edge between nodes 2 and 3?

A Step 6

B Step 5

C Step 4

D Step 7

💡 Hint

Check execution_table rows 5 and 6 for adjacency matrix updates

If the graph is very large but has few edges, which representation is better according to variable_tracker?

A Both are equally good

B Adjacency matrix for fast edge checks

C Adjacency list for memory efficiency

D Neither can represent large graphs

💡 Hint

Look at variable_tracker rows for graphList and graphMatrix memory usage

Concept Snapshot

Adjacency List vs Matrix:
- List stores edges as lists per node, uses less memory for sparse graphs
- Matrix uses 2D array, uses more memory but allows O(1) edge checks
- Choose list for large, sparse graphs
- Choose matrix for small, dense graphs
- Edge addition and checks differ in speed and memory use

Full Transcript

This concept compares adjacency list and adjacency matrix for graph representation. Adjacency list stores neighbors in lists, saving memory for sparse graphs but making edge checks slower. Adjacency matrix uses a 2D array, consuming more memory but allowing fast edge checks. The choice depends on graph size and density: use list for large sparse graphs and matrix for small dense graphs. The execution table shows step-by-step how edges are added and checked in both structures, and the variable tracker shows memory and state changes. Key moments clarify why memory and speed differ and when to prefer each structure.