[prev] 44 [next]
Storage cost: O(V+E)   (V list pointers, total of 2·E list elements)
  • the larger of V,E determines the complexity

Cost of operations:

  • initialisation: O(V)   (initialise V lists)
  • insert edge: O(1)   (insert one vertex into list)
    • if you don't check for duplicates
  • find/delete edge: O(V)   (need to find vertex in list)
If vertex lists are sorted
  • insert requires search of list ⇒ O(V)
  • delete always requires a search, regardless of list order