Adjacency List Representation (cont)
Storage cost: V list ptrs + 2*E nodes ≅ O(V+E)
Cost of operations (if VList s unsorted):
- initialisation: O(V) (initialise
VList s)
- insert edge: O(V) (insert vertex into list, if not there)
- delete edge: O(V) (need to find vertex in list)
- isConnected: O(V) (need to find vertex in list)
|