Adjacency List Representation in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is an adjacency list in graph representation?

An adjacency list is a way to represent a graph where each node stores a list of its neighbors. It shows which nodes are directly connected to each node.

intermediate

How does an adjacency list differ from an adjacency matrix?

An adjacency list stores neighbors only, saving space for sparse graphs. An adjacency matrix uses a 2D array showing connections between all pairs, using more space.

beginner

TypeScript code snippet: How to declare an adjacency list for a graph with 3 nodes?

const graph: Map<number, number[]> = new Map();
graph.set(0, [1, 2]);
graph.set(1, [0]);
graph.set(2, [0]);

intermediate

Why is adjacency list preferred for sparse graphs?

Because it only stores existing edges, saving memory and making traversal faster compared to adjacency matrix which stores all possible edges.

intermediate

What is the time complexity to find all neighbors of a node in adjacency list?

It is O(k), where k is the number of neighbors of that node, because the list directly stores neighbors.

What data structure is commonly used to implement an adjacency list?

A Queue

B 2D array

C Stack

D Array of lists or Map of lists

An adjacency list is usually implemented as an array or map where each element stores a list of neighbors.

Which graph representation uses less space for a graph with few edges?

A Adjacency matrix

B Adjacency list

C Edge list

D Incidence matrix

Adjacency list stores only existing edges, so it uses less space for sparse graphs.

In an adjacency list, how do you find neighbors of a node?

A Look up the node's list of neighbors

B Scan the entire matrix row

C Check all nodes in the graph

D Use a stack to traverse

Neighbors are stored directly in the node's list in adjacency list representation.

What is the main disadvantage of adjacency matrix compared to adjacency list?

A Uses more memory for sparse graphs

B Slower to find neighbors

C Cannot represent directed graphs

D Hard to implement

Adjacency matrix uses memory for all possible edges, even if many don't exist.

Which of these is a valid TypeScript type for an adjacency list?

A string[]

B number[][]

C Map<number, number[]>

D Set<number>

Map maps each node to a list of neighbor nodes.

Explain how an adjacency list represents a graph and why it is efficient for sparse graphs.

Think about how you store only connected nodes, not all possible pairs.

Describe how you would implement an adjacency list in TypeScript for an undirected graph.

Remember undirected means two-way connections.