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 .
int n; List *adj;(An example is shown in Figure 12.3.) In this particular implementation, we represent each list in as a subclass of , because we would like constant time access by position. Other options are also possible. Specifically, we could have implemented as a .

The operation just appends the value to the list :
void addEdge(int i, int j) { adj[i].add(j); }This takes constant time.
The operation searches through the list until it finds and then removes it:
void removeEdge(int i, int j) { for (int k = 0; k < adj[i].size(); k++) { if (adj[i].get(k) == j) { adj[i].remove(k); return; } } }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):
bool hasEdge(int i, int j) { return adj[i].contains(j); }This also takes time.
The operation is very simple; it copies the values in into the output list:
void outEdges(int i, LisT &edges) { for (int k = 0; k < adj[i].size(); k++) edges.add(adj[i].get(k)); }This clearly takes time.
The operation is much more work. It scans over every vertex checking if the edge exists and, if so, adding to the output list:
void inEdges(int i, LisT &edges) { for (int j = 0; j < n; j++) if (adj[j].contains(i)) edges.add(j); }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