The Set ADT

Here is the Set ADT:

public interface Set<T> {
  boolean add(T item);
  boolean remove(T item);
  boolean contains(T item);
  int size();
}

This is a small interface with only four methods. The add method puts an item into the set, the remove method takes one out, the contains method reports whether a given item is in the set, and size reports how many items the set holds.

The interface has no get and no indexOf. A set is not a positional data structure; you cannot ask for the item at an index. A set is about membership: you can ask whether an item is present and how many items there are.

Do not picture a set as a line of items. Picture it as a loose collection of distinct items in no particular order.

  ┌─────────────────────────────┐
  │    "alice"      "bob"       │
  │           "carol"           │
  │   "dave"          "erin"    │
  └─────────────────────────────┘
  each item appears once; no order