Question

Illustrate the trade off between adjacency matrix and adjacency list

Answer 1

Answer:

It depends on the problem.

Explanation:

Adjacency Matrix

Uses O(n^2) memory

It is fast to lookup and check for presence or absence of a specific edge

between any two nodes O(1)

It is slow to iterate over all edges

It is slow to add/delete a node; a complex operation O(n^2)

It is fast to add a new edge O(1)

Adjacency List

Memory usage depends on the number of edges (not number of nodes),

which might save a lot of memory if the adjacency matrix is sparse

Finding the presence or absence of specific edge between any two nodes

is slightly slower than with the matrix O(k); where k is the number of neighbors nodes

It is fast to iterate over all edges because you can access any node neighbors directly

It is fast to add/delete a node; easier than the matrix representation

It fast to add a new edge O(1)