Using an Array to Implement a Set

Our second implementation is ArraySet. It stores the items in a backing array with a size counter, which is the same representation we used for ArrayList. The array grows by doubling when it fills, the same way it did there.

Operations and Complexity

size(): Return the stored size. $O (1)$ .

contains(item): Perform a linear search through the filled part of the array. $O (n)$ .

add(item): Check for a duplicate first, which is the same linear search as contains. If the item is new, append it at the end of the array, $O (1)$ amortized. The search makes the whole operation $O (n)$ .

remove(item): Find the item, $O (n)$ . A set does not keep its items in any order, so instead of shifting we can use the swap-with-last removal from the dynamic-array chapter: copy the last item into the gap and shrink the size. That part is $O (1)$ , though the search still makes the whole operation $O (n)$ .

Amortized add?

ArraySet’s add is not marked amortized, the way ArrayList’s was. Its duplicate search costs $O (n)$ on every call, so the occasional grow does not change the bound. We saw the same thing with SortedArray in Chapter 4: its add shifts up to $n$ elements on every call, so grow did not change its bound either.

These are the same costs as LinkedSet. The two implementations differ in memory, and the trade-off is the same one we saw with the stack and the queue. The array carries spare capacity, and the linked list carries a next reference on every node.

Keeping the Array Sorted

You might be thinking that we could do better by keeping the array sorted, so that we could use binary search to find items in $O (lo g n)$ time. We will look at this idea shortly. For now, we implement the simple unsorted array design.