Graph Adjacency List How to implement O(1) lookup for nodes/vertexes. Array?

Question

I read in the specifications for graphs implemented with Adjacency List that adding edges is done in constant time. BUT that would require a node lookup with O(1). I would like best possible performance. The question here is which datatype would would give me that. Hashmap has been considered, worst case with hashmap is still O(n).

Could I use an Array for this? The node's can be of any datatype, generics. Could this be done with some hash function generating index values based on the node alone? That would give me O(1). Sure I can just capitalize and use LinkedList with indexOf. Constant time is best.

Answer 1

Anything with a hashing step you run the risk of collision, so worst case (however unlikely) is Omega(N).

The best possible guaranteed asymptotic performance for insert and retrieve simultaneously when working with lists is O(log N). You'll get that if you store your nodes in something like a heap or balanced tree. You can't do any better on both operations because it would let you violate the provable O(N log N) bound on sorting.