Suppose we have a directed graph $G = (V,E$) represented with adjacency lists.  Is it possible to convert $G$ into its undirected equivalent* $G'$, also represented with adjacency lists, in $O(|V|+|E|)$ time?The obvious algorithm walks the adjacency list of each vertex $v$, and for each adjacent vertex $u$, inserts edges $(v,u)$ and $(u,v)$ into $G'$.  The issue is duplicates.  If $(u,v)$ happens to be in $G$ already, $(u,v)$ will be inserted into $G'$ twice: once when processing $v$'s adjacency list, and once when processing $u$'s.  Assuming that a well-formed graph doesn't contain any duplicate edges, we would need to check $u$'s adjacency list to see whether it contains $v$ before performing the second insertion.  But this check takes linear time in $|V|$, and we would need to perform this check for $O(|E|)$ edges, resulting in $O(|V|*|E|)$ time complexity.*Terminology:  by undirected equivalent of a digraph $G=(V,E)$, I mean the directed graph $G'=(V,E')$ such thatif $(v,u) \in E$ then $(v,u) \in E$ and $(u,v) \in E'$ andif $(v,u) \in E'$ then either $(v,u) \in E$ or $(u,v) \in E$.   
Convert a digraph to the corresponding undirected graph in linear time using adjacency lists
graphs
If you perform the check at the end rather than throughout, it will be much faster.Start by going over all edges, and for each edge $(i,j)$ add the edge $(j,i)$ to the adjacency list of $j$.Now given the adjacency list of $i$, we want to remove duplicates. For that we use an array indexed by $V$, which is initialized to zero (we only need to initialize it once). Go over the list and count how many times you see each edge. Now go over the list a second time and only add the first occurrence of every edge. Finally, go over the list a third time to reset the array back to zero. In all, we do $O(1)$ work per edge.One drawback of this algorithm is that the resulting adjacency lists aren't sorted, even if you started out with sorted ones. Here is a different algorithm which works in $O(|V|+|E|)$ time and maintains this invariant (assuming it holds originally). For each vertex $i$, compute the sorted lists $\{ j : (i,j) \in G \}$ and $\{ j : (j,i) \in G \}$. Then merge them and remove duplicates.