[prev] 43 [next]

Adjacency List Representation (cont)

Storage cost: V list ptrs + 2*E nodes ≅ O(V+E)

Cost of operations   (if VLists unsorted):

  • initialisation: O(V)   (initialise VLists)
  • 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)