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)
|