Representing Graphs: Adjacency List

We went through Adjacency matrix in the last post and understood how they work and why they are not really a viable solution in many places. However in this post we will discuss the better alternative: Adjacency lists

Adjacency List

Adjacency list use a HashMap, and if you don't know what that is let me give you a quick run down. A HashMap is an array where each element stores two things a key and a value. The position of the value in the array is determined by the key, as it is fed to a hashing algorithm to get a index number, which is where the key and the value is stored.

Now that we know what a HashMap is we can continue with adjacency lists. When we store a node in an adjacency list we have to input three things, the source node, the destination node, and the weight(if the graph is weighted). The source node is what you use as your key value. Now is where it gets interesting, instead of a value we store a list in that position. In this list we store pairs of destination nodes and weights. Thus we can represent which node connects to which and what weight this edge holds.

A simple example is (credit to GeeksForGeeks for the image):

Advantages and disadvantages

Advantages of this method include saving space on graphs with not too many connections, it also makes adding new nodes and connections much easier and can be used to represent undirected and directed graphs.

Disadvantages include the fact that for large graphs with many connections it is going to take more memory than an adjacency matrix, and also it takes longer in an adjacency matrix to access and edge.

Conclusion

While most of the time an adjacency list is preferred because of how easy it to expand and shrink it, and how it also saves you space. There are also some cases where a matrix would make more sense because of the disadvantages listed above.

Thank you for reading, I do hope you found the article informative and useful.