An adjacency list of a graph $G(V,E)$ consists of $|V|$ linked lists, one per vertex. The linked list for vertex $u$ holds the
names of vertices to which $u$ has an outgoing edge—that is, vertices $v$ for which $(u, v) \in E$.
Therefore, each edge appears in exactly one of the linked lists if the graph is directed or two
of the lists if the graph is undirected. Either way, the total size of the data structure is $O(|E|)$.
Checking for a particular edge $(u, v)$ requires sifting
through $u$’s adjacency list. But it is easy to iterate through all neighbors of a vertex (by running
down the corresponding linked list), and this turns out to be a very
useful operation in graph algorithms. For undirected graphs, this representation has a
symmetry of sorts: $v$ is in $u$’s adjacency list if and only if $u$ is in $v$’s adjacency list.
