Array Implementation of Set
We want to efficiently implement the Set ADT with an array as the underlying data structure.
Exercise Complete the following table.
| Operation | How? | Runtime |
|---|---|---|
has | ||
insert | ||
remove | ||
size |
Solution
All operations, except for size, require a helper find method to check if an element exists. We can keep the underlying data in order to perform Binary Search. We will however explore this option for implementing an array based OrderedSet ADT. Let's keep the underlaying data unordered and perform Linear Search in find.
| Operation | How? | Runtime |
|---|---|---|
has | return find(t) != -1; | $O(n)$ |
insert | if (fint(t) == -1) data[numElement++] = t; | $O(n)$ |
remove | Find the element, swap with last, numElements-- | $O(n)$ |
size | return numElements; | $O(1)$ |
find | Linear search | $O(n)$ |
Notice the strategy for remove which allows us to spend constant time after the element is found.