集合01--[集合的基本概念&&链表与红黑树实现集合区别]

1.集合

1.1基本概念

1.2相关知识

1.2.1集合与链表数组等数据结构区别

之前学习的链表和动态数组是不需要遍历这个接口的

因为他们有索引这一概念所以不需要 而集合这一数据结构 需要使用遍历这一接口的

1.2.2两种实现方式

集合有两种实现方式 第一种通过链表 另外一种通过红黑树实现

1.2.3两种方式性能对比

红黑树实现的集合性能优于链表实现的集合

相关实例 遍历JAVA源码并添加单词到集合中

 1.2.4红黑树实现的集合缺陷

用红黑树实现集合 要求 元素必须具备可比较性

用链表和数组实现的集合 对元素不要求任何限制

1.3 相关练习题

https://leetcode-cn.com/problems/intersection-of-two-arrays/

2.代码实现

set 接口

public interface Set<E> {
    int size();
    boolean isEmpty();
    void clear();
    boolean contains(E element);
    void add(E element);
    void remove(E element);
    void traversal(Visitor<E> visitor);
    
    public static abstract class Visitor<E> {
        boolean stop;
        public abstract boolean visit(E element);
    }
}

ListSet

public class ListSet<E> implements Set<E> {
    private List<E> list = new LinkedList<>();
    
    @Override
    public int size() {
        return list.size();
    }

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

    @Override
    public void clear() {
        list.clear();
    }

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

    @Override
    public void add(E element) {
        int index = list.indexOf(element);
        if (index != List.ELEMENT_NOT_FOUND) { // 存在就覆盖
            list.set(index, element);
        } else { // 不存在就添加
            list.add(element);
        }
    }

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

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

}

TreeSet

public class TreeSet<E> implements Set<E> {
    private RBTree<E> tree;
    
    public TreeSet() {
        this(null);
    }
    
    public TreeSet(Comparator<E> comparator) {
        tree = new RBTree<>(comparator);
    }
    
    @Override
    public int size() {
        return tree.size();
    }

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

    @Override
    public void clear() {
        tree.clear();
    }

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

    @Override
    public void add(E element) {
        tree.add(element);
    }

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

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

}

Main函数

public class Main {
    
    static void test1() {

        Set<Integer> listSet = new ListSet<>();
        listSet.add(10);
        listSet.add(11);
        listSet.add(11);
        listSet.add(12);
        listSet.add(10);
        
        Set<Integer> treeSet = new TreeSet<>();
        treeSet.add(12);
        treeSet.add(10);
        treeSet.add(7);
        treeSet.add(11);
        treeSet.add(10);
        treeSet.add(11);
        treeSet.add(9);
        
        treeSet.traversal(new Visitor<Integer>() {
            @Override
            public boolean visit(Integer element) {
                System.out.println(element);
                return false;
            }
        });
    }
    
    
    static void testSet(Set<String> set, String[] words) {
        for (int i = 0; i < words.length; i++) {
            set.add(words[i]);
        }
        for (int i = 0; i < words.length; i++) {
            set.contains(words[i]);
        }
        for (int i = 0; i < words.length; i++) {
            set.remove(words[i]);
        }
    }
    
    static void test2() {
        FileInfo fileInfo = Files.read("C:\Users\MJ Lee\Desktop\src\java\util", 
                new String[]{"java"});
        
        System.out.println("文件数量：" + fileInfo.getFiles());
        System.out.println("代码行数：" + fileInfo.getLines());
        String[] words = fileInfo.words();
        System.out.println("单词数量：" + words.length);
        
//        Times.test("ListSet", new Task() {
//            public void execute() {
//                testSet(new ListSet<>(), words);
//            }
//        });
        
        Times.test("TreeSet", new Task() {
            public void execute() {
                testSet(new TreeSet<>(), words);
            }
        });
    }

    public static void main(String[] args) {
        test2();
    }

}