数据结构篇10、集合Set及其三种底层实现

我们经常使用java标准库中的TreeSet或者HashSet,他们的底层实现分别是红黑树和哈希表；我们本文定义自己的Set接口，使用我们前面自己实现的数据结构链表、二分搜索树、AVL树来实现此Set接口；

1、Set接口

Set接口如下所示，方法作用见注释；

public interface Set<E> {
    //往集合中添加元素
    void add(E e);
    //从集合中移除元素
    void remove(E e);
    //查找集合中是否包含元素
    boolean contains(E e);
    //获得集合中元素个数
    int getSize();
    //返回集合是否为空
    boolean isEmpty();
}
复制代码

2、链表实现的集合Set

链表实现的Set集合如下所示，其实就是对我们自己实现的链表Api的一层封装，我们自己实现的链表见数据结构篇02；

需要注意一点我们定义的Set集合不允许存放重复元素，所以add方法需要先检查是否存在；

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

    private LinkedList<E> list;

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

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

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

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

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

    @Override
    public void remove(E e){
        list.removeElement(e);
    }
}
复制代码

3、二分搜索树实现的集合Set

二分搜索树实现的集合Set如下所示，其实就是对我们实现的二分搜索树api的一层封装，我们实现的二分搜索树见数据结构篇05；

为什么链表的add方法需要检查是否存在，此时不需要检查了呢？因为我们实现的二分搜索树本来就不能存放重复元素；

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

    private BST<E> bst;

    public BSTSet(){
        bst = new BST<>();
    }

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

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

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

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

    @Override
    public void remove(E e){
        bst.remove(e);
    }
}
复制代码

4、AVL树实现的集合Set

AVL树实现的集合Set如下所示，其实就是对我们实现的AVL树api的一层封装，我们实现的AVL树见数据结构篇07；

我们实现的AVL树为了实现映射Map，定义的是两种泛型，但我们实现集合Set时其实只需要K一个泛型就够了，此时我们可以把V泛型定义为Object，然后在使用到的时候直接置为null即可；

同理add函数不需要检查是否存在，因为我们实现的AVL树也不支持存放重复元素；

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

    private AVLTree<E, Object> avl;

    public AVLSet(){
        avl = new AVLTree<>();
    }

    @Override
    public int getSize(){
        return avl.getSize();
    }

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

    @Override
    public void add(E e){
        avl.add(e, null);
    }

    @Override
    public boolean contains(E e){
        return avl.contains(e);
    }

    @Override
    public void remove(E e){
        avl.remove(e);
    }
}
复制代码