An undirected graph $G=(V,E)$ is represented by the sets $V(G)$ and $E(G)$. If these sets are maintained as simple lists where the buffer $v$ communicates with the vertex list and $e$ communicates with the edge list, Algorithm 1 creates an adjacency list $A$ for $G$.

Algorithm 1: Create Adjacency List of Undirected Graph
 $i=$first($V$) while $k\neq eol$ insert($A,v,header$) $k=$next($V,k$) $k=$first($E$) while $k\neq eol$ insert($A,e.v,e.w$) insert($A,e.w,e.v$) $k=$next($E,k$)

The first loop in Algorithm 1 creates a header for each vertex. This operation is not strictly necessary given the current data definition; however, it is often required in practical implementations.

You should observe that the algorithm inserts each edge in $E(G)$ into the adjacency list twice: once in the stated direction and once in the reverse direction. If $G$ is a directed graph, the reverse insertion is inappropriate (i.e. omit the final insert statement in Algorithm 1). It should be apparent that the algorithm has a time complexity of $O\left(|V|+|E|\right)$ if all operators have time complexity of $O(1)$.

It is often beneficial to create an adjacency list based on an alternate labeling of the vertices of $G$. This operation requires a mapping $\mu$ of the integers from 1 to $|V|$ onto the set $V(G)$. Algorithm 2 maps $V(G)$ to the order in which it is enumerated.

Algorithm 2: Map Vertices To Labeling Order
 $i=0$ $k=$first($V$) while $k\neq eol$ $i=i+1$ map($\mu,v,i$) $k=$next($V,k$)

Algorithm 3 combines these two procedures. It labels $V(G)$ according to its order of enumeration and creates an adjacency list based on this labeling.

Algorithm 3: Create Ordered Adjacency List
 $i=0$ $k=$first($V$) while $k\neq eol$ $i=i+1$ map($\mu,v,i$) insert($A,v,header$) $k=$next($V,k$) $k$ = first($E$) while $k\neq eol$ $i=$evaluate($\mu,e.v$) $j=$evaluate($\mu,e.w$) insert($A,i,j$) insert($A,j,i$) $k=$next($E,k$)

If map and evaluate have constant time complexity, the overall algorithm retains its linear complexity.

Note. In a practical implementation, map will insert the pair $(d,r)$ into a data structure that is optimized for searching and evaluate will look up $d$ in this data structure. Efficient operations of this sort have a time complexity of $O\left(\,\log _{2}n\,\right)$. Therefore, adjacency list creation will have complexity $O\left(\,|V|\log _{2}|V|+|E|\log _{2}|V|\,\right)$.