Adjacency list representations of graphs take a more vertexcentric
approach. There are many possible implementations of adjacency lists.
In this section, we present a simple one. At the end of the section,
we discuss different possibilities. In an adjacency list representation,
the graph is represented as an array,
, of lists. The list
contains a list of all the vertices adjacent to vertex
.
That is, it contains every index
such that
.
(An example is shown in Figure 12.3.) In this particular
implementation, we represent each list in
as ArrayStack, because we would like constant time access
by position. Other options are also possible. Specifically, we could
have implemented
as a DLList.

The
operation just appends the value
to the list
:
This takes constant time.
The
operation searches through the list
until it finds
and then removes it:
This takes
time, where
(the degree
of
) counts the number of edges in that have
as their source.
The
operation is similar; it searches through the list
until it finds
(and returns true), or reaches the end of
the list (and returns false):
This also takes
time.
The
operation is very simple;
it returns the list
:
The
operation is much more work. It scans over every
vertex checking if the edge
exists and, if so, adding
to the output list:
This operation is very slow. It scans the adjacency list of every vertex,
so it takes
time.
The following theorem summarizes the performance of the above data structure:
As alluded to earlier, there are many different choices to be made when implementing a graph as an adjacency list. Some questions that come up include:
opendatastructures.org