Mark As Completed Discussion
Implementation of an Adjacency List

In this illustration, each vertex is given an index in its list. The list has all of its neighboring vertices stored as a linked list (can also be an array) adjacent to it.

For example, the last element in the list is the vertex 3, which has a pointer to a linked list of its neighbors. The list that is adjacent to vertex 3 contains references to two other vertices (1 and 2), which are the two nodes that are connected to the node 3.

Thus, just by looking up the node 3, we can quickly determine who its neighbors are and, by proxy, realize that it has two edges connected to it.

This all results from the structure of an adjacency list making it easy to determine all the neighbors of one particular vertex. In fact, retrieving one node's neighbors takes constant or O(1) time, since all we need to do is find the index of the node we're looking for and pull out its list of adjacent vertices.

Please see the implementation of adjacency list attached.

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment