Suppose that instead of a linked list, each array entry $adj[u]$ is a hash table containing the vertices $v$ for which $(u,v) \in E$. If all edge lookups are equally likely, what is the expected time to determine whether an edge is in the graph? What disadvantages does this scheme have ? Suggest an alternate data structure for each edge list that solves these problems. Does your alternative have disadvantages compared to the hash table ?
