玩转数据结构（十四）如何实现set

待我称王封你为后i 2022-05-21 12:29 148阅读 0赞

### 1、set简介 ###

set是一种不支持重复元素的集合。本节将介绍两种实现set的方式，一种是基于BST实现，另一种基于链表实现。

关于BST如何实现：[构建BST][BST]

关于LinkedList如何实现：[实现LinkedList][LinkedList]

### 2、set接口 ###

public interface Set<E> {
        void add(E e);
        boolean contains(E e);
        void remove(E e);
        int getSize();
        boolean isEmpty();
    }

### 3、基于BST实现Set ###

特性：**元素不重复、有序**

/**
     * 插入、删除、查找时间复杂度均为O(logn)
     * @param <E>
     */
    public class BSTSet<E extends Comparable<E>> implements Set<E> {
        private BST<E> bst;
    
        public BSTSet() {
            bst = new BST<E>();
        }
    
        @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);
        }
    
        @Override
        public int getSize() {
            return bst.size();
        }
    
        @Override
        public boolean isEmpty() {
            return bst.isEmpty();
        }
    }

### 4、基于链表实现Set ###

import java.util.ArrayList;
    
    /**
     * 添加时间复杂度：O（n） 因为其中包含contains检验:O（n）
     * 删除时间复杂度：O（n）
     * 查询时间复杂度：O（n）
     * @param <E>
     */
    public class LinkedListSet<E> implements Set<E> {
        private LinkedList<E> list;
    
        public LinkedListSet() {
            list = new LinkedList<>();
        }
    
        @Override
        public void add(E e) {
            if(!list.contains(e)) {//元素去重复
                list.addFirst(e);
            }
        }
    
        @Override
        public boolean contains(E e) {
            return list.contains(e);
        }
    
        @Override
        public void remove(E e) {
            list.removeElement(e);
        }
    
        @Override
        public int getSize() {
            return list.getSize();
        }
    
        @Override
        public boolean isEmpty() {
            return list.isEmpty();
        }
    }

### 5、两种方式实现的Set性能比较 ###

BSTSet基于BST实现，其中的增加、删除、查询操作的时间复杂度均为O（logn）;

LinkedListSet基于链表实现，其中的增加、删除和查询均涉及链表的遍历，因此时间复杂度为O（n）;

由此可见O（logn）时间复杂度的效率是极高的，因此BSTSet要比LinkedListSet效率要高的多。

[BST]: https://blog.csdn.net/zhoujian_Liu/article/details/80948356
[LinkedList]: https://blog.csdn.net/zhoujian_Liu/article/details/80901879