The adjacency list representation of a graph consists of an array of |V| lists, one for each vertex in V. For each vertex u in V, there's a list containing all vertices v so that there is an edge connecting u and v in E. Figure 6.3 shows the adjacency list representation of the directed graph in Figure 6.1:

For undirected graphs, we follow a similar strategy and build the adjacency list as if it were a directed graph with two edges between each pair of vertices u and v, which are (u, v) and (v, u).

Figure 6.4 shows the adjacency list representation of the undirected graph in Figure 6.2:

If G is a directed graph, the sum of the lengths of all the adjacency lists is |E|, as each edge constitutes a single node in one of the adjacency lists.

If G is an undirected graph, the sum of the lengths of all the adjacency lists is 2*|E|, since each edge (u, v) appears twice, that is, once in u's and once in v's adjacency list.

For both types of graphs, the adjacency list representation has the property of requiring an amount of memory equal to O(V + E).

The following code snippet shows how to create a graph using the adjacency list representation in Java:

public class AdjacencyListGraph {
  ArrayList<Integer>[] adj;
  public AdjacencyListGraph(int nodes) {
    this.adj = new ArrayList[nodes];
    for (int i = 0; i < nodes; i++)
    this.adj[i] = new ArrayList<>();
  }
  public void addEdge(int u, int v) {
    adj[u].add(v);
  }
}  

It is common for one to have weighted graphs, that is, graphs in which each edge has an associated weight. The adjacency list representation is robust enough to support different graph variants, since we can store different edge representations in the adjacency lists.