Adjacency List Representation in DSA C - 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 neighboring nodes. It saves space by only storing edges that exist.

beginner

How does an adjacency list differ from an adjacency matrix?

An adjacency list stores neighbors for each node in lists, using less space for sparse graphs. An adjacency matrix uses a 2D array to store edge presence, using more space.

intermediate

In C, what data structure is commonly used to implement an adjacency list?

A common approach is to use an array of pointers, where each pointer points to a linked list of neighbors for that vertex.

beginner

Why is adjacency list preferred for sparse graphs?

Because it only stores existing edges, it uses less memory and is faster to iterate over neighbors compared to adjacency matrix which stores all possible edges.

intermediate

What is the time complexity to find all neighbors of a vertex using adjacency list?

It is O(k), where k is the number of neighbors of that vertex, since we directly access the list of neighbors.

What does each element in an adjacency list represent?

A A graph color

B A matrix row

C A vertex and its neighbors

D An edge weight

Each element in an adjacency list stores a vertex and a list of its neighboring vertices.

Which data structure is commonly used to store neighbors in C adjacency lists?

A Array of arrays

B Stack

C Queue

D Linked lists

Linked lists are used to store neighbors dynamically for each vertex.

What is the main advantage of adjacency lists over adjacency matrices?

A Faster edge lookup

B Less memory for sparse graphs

C Simpler to implement

D Supports weighted graphs only

Adjacency lists use less memory when the graph has fewer edges.

How do you add an edge from vertex u to vertex v in an adjacency list?

A Add v to u's neighbor list

B Set matrix[u][v] = 1

C Add u to v's neighbor list

D Increment edge count

In adjacency lists, adding an edge means adding the destination vertex to the source vertex's neighbor list.

What is the space complexity of adjacency list for a graph with V vertices and E edges?

A O(V + E)

B O(V^2)

C O(E^2)

D O(V)

Adjacency list stores vertices and edges separately, so space is proportional to vertices plus edges.

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

Think about how you would list friends for each person instead of a big table.

Describe how you would implement an adjacency list in C using arrays and linked lists.

Imagine each vertex has a pointer to a chain of neighbors.