Array Implementation of OrderedSet
We want to efficiently implement the OrderedSet 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 perform Binary Search so find and has will cost $O(\lg n)$. The insert and remove operation will remain linear time since we must shift the elements around to keep the values in order.
| Operation | How? | Runtime |
|---|---|---|
has | return find(t) != -1; | $O(\lg n)$ |
insert | Find where to insert, then shift elements to make room. | $O(n)$ |
remove | Find the element, shift all element after it to left. | $O(n)$ |
size | return numElements; | $O(1)$ |
find | Binary search | $O(\lg n)$ |
We leave this as an (unsolved) exercise to you: implement the operations of an array-based OrderedSet.