# Glossary

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.