 Adjacency list edge conventions

For a directed graph, store $v$ in $\mathrm{Adj}[u]$ for the edge $u\to v$. The reverse edge $v\to u$ is separate and is stored only if it exists. Consequently, list length is outdegree, not indegree, and each directed edge contributes one entry in total. An incoming-list index is additional storage.^[ref]

Orient the seven edges of our example from earlier to later labels. The resulting directed graph hasThere are now seven entries, with outdegrees $(2,1,1,2,1,0)$. In particular, $F$ needs an empty list even though it is reached from $D,E$: incoming edges do not make $F$'s outgoing list nonempty. Replacing each directed edge by an undirected graph connection would lose this distinction.

Our running simple graph excludes self-loops and repeated edges. If those restrictions are relaxed, specify how the adjacency list encodes them. Here an undirected self-loop at $u$ contributes two copies of $u$ to $\mathrm{Adj}[u]$, matching its contribution of two to the degree of a vertex. A directed self-loop contributes one copy, and one each to outdegree and indegree. Distinct parallel edges retain distinct entries; a multigraph's list length can therefore exceed its number of distinct neighbours.^[ref][ref]

For example, add one undirected self-loop at $A$ to the seven-edge example. Its list becomes $(B,C,A,A)$, the vertex degree of $A$ becomes four, and the total entry count becomes sixteen for eight edges. If an application instead stores a self-loop once, it must account for its doubled undirected vertex degree separately. In a weighted graph, an entry can be an ordered pair $(v,w)$ meaning destination $v$ and weight $w$; the weight belongs to the edge, not to the destination vertex.