数据结构与算法笔记目录： 《恋上数据结构》 笔记目录

想加深 Java 基础推荐看这个： Java 强化笔记目录

我的《恋上数据结构》源码（第1季 + 第2季）：https://github.com/szluyu99/Data_Structure_Note

集合的特点：

• 不存放重复的元素
• 常用于去重
  存放新增 IP，统计新增 IP
  存放词汇，统计词汇量
  ...

思考：集合的内部实现能否直接利用以前学过的数据结构?

• 动态数组
• 链表
• 二叉搜索树（AVL树、红黑树）

集合的接口定义

集合的接口文件(interface)，所有实现的集合都需要实现该接口。

public interface Set<E> {
    int size();    //元素数量
    boolean isEmpty(); // 是否为空
    void claer(); // 清空集合
    boolean contains(E element); // 是否包含element元素
    void add(E element); // 添加element元素
    void remove(E element); // 删除element元素
    void traversal(Visitor<E> visitor); // 通过访问器遍历
    
    public static abstract class Visitor<E>{ // 访问器
        boolean stop;
        public abstract boolean visit(E element);
    }
}

双向链表 LinkedList 实现 ListSet

通过 双向链表 实现 ListSet。

/**
 * LinkedList实现的ListSet
 */
public class ListSet<E> implements Set<E>{
    private LinkedList<E> list = new LinkedList<>();

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

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

    public void claer() {
        list.clear();
    }

    public boolean contains(E element) {
        return list.contains(element);
    }

    public void add(E element) {
        // if(list.contains(element)) return;
        
        int index = list.indexOf(element);
        if(index == List.ELEMENT_NOT_FOUND){ // 没有该元素
            list.add(element); // 没有就添加
        }else{
            list.set(index, element); // 已经有就替换
        }
    }

    public void remove(E element) {
        int index = list.indexOf(element);
        if(index != List.ELEMENT_NOT_FOUND){
            list.remove(index);
        }
    }

    public void traversal(Visitor<E> visitor) {
        int size = list.size();
        for(int i = 0; i < size; i++){
            visitor.visit(list.get(i));
        }
    }

}

红黑树 RBTree 实现 TreeSet

通过 红黑树 实现的 TreeSet。

/**
 * 红黑树实现集合
 */
public class TreeSet<E> implements Set<E>{
    private RBTree<E> tree = new RBTree<>();
    
    public int size() {
        return tree.size();
    }

    public boolean isEmpty() {
        return tree.isEmpty();
    }

    public void claer() {
        tree.clear();
    }

    public boolean contains(E element) {
        return tree.contains(element);
    }

    public void add(E element) {
        tree.add(element); // 红黑树自带去重
    }

    public void remove(E element) {
        tree.remove(element);
    }

    public void traversal(Visitor<E> visitor) {
        tree.inorder(new BinaryTree.Visitor<E>() {
            @Override
            public boolean visit(E element) {
                return visitor.visit(element);
            }
        });
    }

}

TreeMap 实现 TreeSet

通过 TreeMap 实现 TreeSet。

/**
 * 利用TreeMap实现TreeSet
 */
public class TreeSet<E> implements Set<E> {

    private Map<E, Object> map = new TreeMap<>();
    
    public int size() {
        return map.size();
    }

    public boolean isEmpty() {
        return map.isEmpty();
    }

    public void claer() {
        map.clear();
    }

    public boolean contains(E element) {
        return map.containsKey(element);
    }

    public void add(E element) {
        map.put(element, null);
    }

    public void remove(E element) {
        map.remove(element);
    }

    public void traversal(Visitor<E> visitor) {
        map.traversal(new Map.Visitor<E, Object>() {
            public boolean visit(E key, Object value) {
                return visitor.visit(key);
            }
        });
    }
}

HashMap 实现 HashSet

通过 HashMap 实现 TreeSet。

/**
 * 利用HashMap实现HashSet
 */
public class HashSet<E> implements Set<E> {
    private HashMap<E, Object> map = new HashMap<>();

    public int size() {
        return map.size();
    }

    public boolean isEmpty() {
        return map.isEmpty();
    }
    
    public void clear() {
        map.clear();
    }

    public boolean contains(E element) {
        return map.containsKey(element);
    }

    public void add(E element) {
        map.put(element, null);
    }

    public void remove(E element) {
        map.remove(element);
    }

    public void traversal(Visitor<E> visitor) {
        map.traversal(new Map.Visitor<E, Object>() {
            public boolean visit(E key, Object value) {
                return visitor.visit(key);
            }
        });
    }

}