Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

general
communitycreator

What is an adjacency list?

Tarun Telang

The need for an adjacency list

An adjacency matrix is a popular and simple way to represent a graph. However, it is most suitable when your model does not frequently manipulate vertices. Adjacency matrices are good for storing dense graphs, but in most of the other cases, an adjacency list is better than an adjacency matrix.

Adjacency list

In an adjacency list, we use an array of linked lists to represent a graph instead of a matrix.

For example, consider the graph below.

g 1 1 2 2 1--2 3 3 1--3 5 5 2--5 4 4 3--4 5--4
A Graph with 5 vertices and 5 edges

Below is the adjacency list representation for the above graph. There is a corresponding array element for each vertex of the graph. The edges, which represent connections between these vertices, are represented as nodes in the linked list.

/ represents a null or None value to denote the end of the linked list.

%0 node_1625454358344 5 node_1625454515932 2 node_1625454358344->node_1625454515932 node_1625454541073 4 node_1625454515932->node_1625454541073 node_1625493187518 / node_1625454541073->node_1625493187518 node_1625454382908 4 node_1625454493882 3 node_1625454382908->node_1625454493882 node_1625454449542 5 node_1625454493882->node_1625454449542 node_1625493172162 / node_1625454449542->node_1625493172162 node_2 3 node_1625454464714 1 node_2->node_1625454464714 node_1625454476232 4 node_1625454464714->node_1625454476232 node_1625493232274 / node_1625454476232->node_1625493232274 node_1 2 node_1_1 5 node_1->node_1_1 node_1625493199415 / node_1_1->node_1625493199415 node_0 1 node_0_1 2 node_0->node_0_1 node_1625454465692 3 node_0_1->node_1625454465692 node_1625493244773 / node_1625454465692->node_1625493244773
Adjacency list representing the above graph

Space complexity

In general, the space complexity of an adjacency list is O(V+E)O(V + E), and in the worst case, it is O(V2)O(V^{2}) when every node is connected to all the other nodes. Here, VV represents the number of vertices and EE represents the number of edges in the graph.

The space complexity of the adjacency matrix is O(V2)O(V^{2}).

Space complexity comparison

Space complexity

Adjacency matrix

Adjacency list

Average case

O(V2)

O(V+E)

Worst case

O(V2)

O(V2)

An adjacency list is more efficient, in terms of storage requirements, for representing a graph.

Time complexity

Below is a list of various graph operations and their corresponding time complexities.

Time complexity comparison

Use cases / Implementation

Adjacency matrix

Adjacency list

Adding a vertex

O(V2)

O(1)

Removing a vertex

O(V2)

O(V+E)

Adding an edge

O(1)

O(1)

Removing an edge

O(1)

O(E)

Querying for an edge

O(1)

O(V)

Finding neighbors

O(V)

O(V)

Conclusion

Before choosing between the adjacency list and adjacency matrix, you must first compare the time and space complexities for the various graph operations you would need to perform.

RELATED TAGS

general
communitycreator
RELATED COURSES

View all Courses

Keep Exploring