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
Except for size, all operations require a helper find method to check if an element exists. Then, we can perform Binary Search, so find and has will cost $O(\lg n)$. The insert and remove operations will remain linear 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.