[prev] 34 [next]

Sets as Linked Lists (cont)

Costs for set operations on linked list:
  • insert: duplicate check, insert at head;   O(n)
  • delete: find, unlink;   O(n)
  • member: linear search; O(n)
  • card: lookup; O(1)
  • union: copy s1, insert each item from s2; O(nm)
  • intersect: scan for each item in s1;   O(nm)
Assume n = size of s1, m = size of s2

If we don't have nelems, card becomes O(n)