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.

OperationHow?Runtime
has
insert
remove
size
Solution

Except for size, all operations require a helper find method to check if an element exists. We cannot keep the underlying data sorted to perform Binary Search (why?). We will, however, explore this option for implementing an array-based OrderedSet ADT. Let's keep the underlying data unsorted and perform Linear Search in find.

OperationHow?Runtime
hasreturn find(t) != -1;$O(n)$
insertif (fint(t) == -1) data[numElement++] = t;$O(n)$
removeFind the element, swap with last, numElements--$O(n)$
sizereturn numElements;$O(1)$
findLinear search$O(n)$

Notice the remove strategy, which allows us to spend constant time after the element is found.