思维导图

什么是集合：

  在计算机科学中，集合是一组可变数量的数据项（也可能是0个）的组合，这些数据项可能共享某些特征，需要以某种操作方式一起进行操作。一般来讲，这些数据项的类型是相同的，或基类相同（若使用的语言支持继承）。列表（或数组）通常不被认为是集合，因为其大小固定，但事实上它常常在实现中作为某些形式的集合使用。

集合的分类

  集合的种类包括列表，集(数据不重复)，多重集(数据重复)，树和图。枚举类型可以是列表或集。
集合还可以分为有序集合和无序集合：
•有序集合:其中的数据具有顺序性(常常基于搜索树实现)
•无序集合:其中的数据没有顺序性(常常基于哈希表实现)

实现步骤图示：

代码实现：

链表实现集合：

public class LinkedListSet<E extends Comparable<E>> implements Set<E> {

    private LinkedList<E> list;

    public LinkedListSet() {
        this.list = new LinkedList<>();
    }

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

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public void contains(E e) {
        list.contains(e);
    }

    @Override
    public void add(E e) {
        if (!list.contains(e)) {
            list.addFirst(e);
        }
    }

    @Override
    public void remove(E e) {
        list.remove(e);
    }
}

二叉树实现集合：

public class BinarySearchTreeSet<E extends Comparable<E>> implements Set<E> {
    private BinarySearchTreeSet<E> bst ;

    public BinarySearchTreeSet(){
        this.bst = new BinarySearchTreeSet();
    }

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

    @Override
    public boolean isEmpty() {
        return bst.isEmpty();
    }

    @Override
    public void add(E e) {
        bst.add(e);
    }

    @Override
    public void remove(E e) {
        bst.remove(e);
    }

    @Override
    public void contains(E e) {
        bst.contains(e);
    }
}

时间复杂度：