Implementing ArraySet

Here is the Set interface:

public interface Set<T> {
  boolean add(T item);       // adds item if it is absent; returns true if the set changed
  boolean remove(T item);    // removes item if it is present; returns true if the set changed
  boolean contains(T item);  // returns true if item is in the set
  int size();                // returns the number of items in the set
}

add, remove, and contains throw an IllegalArgumentException if the item is null.

ArraySet<T> implements the Set<T> interface with a backing array. The items are at indices 0 through size - 1, in no particular order:

public class ArraySet<T> implements Set<T> {

  private T[] arr;   // the backing array
  private int size;  // how many items the set holds

  @SuppressWarnings("unchecked")
  public ArraySet() {
    arr = (T[]) new Object[10];
    size = 0;
  }

  @Override
  public int size() {
    return size;
  }

  // Doubles the capacity of arr and keeps the items where they are.
  private void grow() { /* already implemented */ }

  // the other operations go here
}

Solution

private int indexOf(T item) {
  for (int i = 0; i < size; i++) {
    if (arr[i].equals(item)) {
      return i;
    }
  }
  return -1;
}

Solution

@Override
public boolean contains(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  return indexOf(item) != -1;
}

@Override
public boolean add(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  if (indexOf(item) != -1) {
    return false;
  }
  if (size == arr.length) {
    grow();
  }
  arr[size] = item;
  size++;
  return true;
}

Solution

A list promises to keep the remaining items in order, so it has to shift. A set promises no order, so it can copy the last item into the gap and shrink the size. A client cannot tell that the last item moved.

Solution

@Override
public boolean remove(T item) {
  if (item == null) {
    throw new IllegalArgumentException();
  }
  int i = indexOf(item);
  if (i == -1) {
    return false;
  }
  arr[i] = arr[size - 1];
  arr[size - 1] = null;
  size--;
  return true;
}

Solution

size is $O (1)$ : it returns a field. contains is $O (n)$ : it is a linear search. add is $O (n)$ : the duplicate check is a linear search, and the append after it is $O (1)$ amortized. remove is $O (n)$ : closing the gap is $O (1)$ , but finding the item is a linear search.

Solution

Both use $O (n)$ space. The array has more slots than items unless it is full. The linked list allocates exactly one node per item, but each node also stores a next reference.