In an adjacency list representation, linked lists are used to represent the adjacent vertices of a vertex. That is, a separate linked list is made for the adjacent vertices of each vertex, and, in the end, all the vertices of the graph are connected. Because linked lists are used, this way of representing a graph uses memory in a more optimized manner.
Consider the following directed graph:
Its adjacency list representation is as follows:
You can see in the preceding diagram that the adjacent vertices of vertex 1 are connected in the form of a linked list. Because there are no adjacent vertices for vertex 2, its pointer is pointing to NULL. Similarly, the adjacent vertices of vertex 3, that is, vertices 4 and 5, are connected to vertex 3 in the form of a linked list. Once a linked...