容器的并集操作

List<String> a = new ArrayList<>();
        a.add("I");
        a.add("lv");
        a.add("U");

        List<String> b = new ArrayList<>();
        b.add("U");
        b.add("give");
        b.add("veni");

        //a并b，若b为空返回false
        boolean flag8 = a.addAll(b);
        System.out.println(flag8);
        for (String str:a){
            System.out.println(str);
        }

容器的交集操作

List<String> a1 = new ArrayList<>();
       a1.add("I");
       a1.add("lv");
       a1.add("U");

       List<String> b1 = new ArrayList<>();
       b1.add("U");
       b1.add("give");
       b1.add("veni");
       boolean flag9 = a1.retainAll(b1);
       System.out.println(flag9);
       for(String str:a1){
           System.out.println(str);
       }

容器的差集操作

/*
        删除a2中a2、b2共有的元素
         */
        List<String> a2 = new ArrayList<>();
        a2.add("I");
        a2.add("lv");
        a2.add("U");

        List<String> b2 = new ArrayList<>();
        b2.add("U");
        b2.add("give");
        b2.add("veni");

        boolean flag10 = a2.removeAll(b2);
        System.out.println(flag10);
        for (String str:a2){
            System.out.println(str);//I lv
        }
        //此时a2包含I lv;b2包含U give veni
        boolean flag11 = b2.removeAll(a2);
        System.out.println(flag11);
        for (String str:b2){
            System.out.println(str);//U give veni
        }

ArrayList底层源码分析/P191

• 延迟初始化
• 从0个元素到1个元素，扩容至10；到11个元素，再扩容至15
• 第一次扩容10，第二次开始每次扩容至上一次容量的1.5倍，int类型 非整数去掉小数部分

留出提前量，不至于每次都扩容

size ，minCapacity = size+1

第10个元素加入时minCapacity = 11，开始判断然后扩容，不会等第11个元素加入再扩容

【初始化】【扩容】

elementData[size++] = e 与 element.size()

size初始为0，放入一个元素，[0] = e1，size() = 1；放入第二个元素，[1] = e2，size() = 2；

这样定义达到了数组下标总是等于元素个数-1

Vector容器类

Vector底层是用数组实现的，相关的方法都加了同步检查，因此“线程安全，效率低”

比如，indexOf方法就增加了synchronized同步标记

多线程 交替处理

List<String> v = new Vector<>();

        v.add("a");
        v.add("b");
        v.add("a");

        for (int i = 0; i < v.size(); i++) {
            System.out.println(v.get(i));
        }

        System.out.println("----------------------");

		//foreach循环
        for (String str:v){
            System.out.println(str);
        }

Vector容器源码分析/P193

• 立即初始化，数组一创建即给定容量10
• 扩容至2倍
• 扩容后多余的容量里：没有元素or其余元素都为0/null？

Stack容器

【Stack栈容器】是Vector的一个子类

• 先进后出，后进先出（出井机制）
• 它通过5个操作方法对vector进行扩展，允许将向量视为堆栈

stack的使用

//实例化Stack栈容器
        Stack<String> stack = new Stack<>();

        System.out.println("--------将元素添加到栈容器中--------");
        stack.push("a");
        stack.push("b");
        stack.push("c");
        System.out.println("--------获取栈中元素----------");
        //把栈顶元素从栈中取出，每次栈中元素数量-1
        String pop = stack.pop();
        System.out.println(pop);
        String pop1 = stack.pop();
        System.out.println(pop1);
        String pop2 = stack.pop();
        System.out.println(pop2);
        System.out.println("--------判断栈是否为空---------");
        boolean flag = stack.empty();
        System.out.println(flag);
//        System.out.println(stack.empty());
        System.out.println("--------返回栈顶元素，但不将其从栈中移除--------");
        stack.push("b");
        stack.push("c");
        String peek1 = stack.peek();
        System.out.println(peek1);
        stack.push("U");
        String peek2 = stack.peek();
        System.out.println(peek2);
        System.out.println("---------返回元素在栈容器中的位置-------");
        //栈中元素的位置，从上而下，从1开始，不同于数组下标从0开始
        int u = stack.search("U");
        int b = stack.search("b");
        int c = stack.search("c");
        System.out.println(u);//1
        System.out.println(b);//3
        System.out.println(c);//2

stack使用案例/P196——假设修正法

//匹配符号的对称性
    public void symmetry(){
        String str = "...{.....[....(....]...]....}..(....)..[...]...";
        //实例化Stack
        Stack<String> stack = new Stack<>();
        //假设修正法
        //假设匹配
        boolean flag = true;
        //拆分字符串，获取字符
        for (int i = 0; i < str.length(); i++) {
            char c= str.charAt(i);

            //按字符对比，以字符串添加
            if (c == '{'){
                stack.push("}");
            }
            if (c == '['){
                stack.push("]");
            }
            if (c == '('){
                stack.push(")");
            }

            //判断符号是否匹配（利用先进后出）
            if (c == '}' || c == ']' || c ==')'){
                if (stack.empty()){
                    //修正处理
                    flag = false;
                    break;
                }
                String x = stack.pop();
                if (x.charAt(0) != c){
                    //修正处理
                    flag = false;
                    break;
                }
            }
        }
        if (!stack.empty()){
            //修正处理
            flag = false;
        }
        System.out.println(flag);
    }

LinkedList容器类

• LinkedList底层用【双向链表】实现的存储
• 【特点】查询效率低，增删效率高，线程不安全
• 双向链表也叫双链表，是链表的一种，它的每个数据节点中都有两个指针，分别指向前一个节点和后一个节点。所以，从双向链表中的任意一个节点开始，都可以很方便地找到所有节点
• LinkedList实现了List 接口，所以LinkedList是具备List的存储特征的（有序，元素有重复）

数据结构学习

LinkedList的使用（List标准）

public class LinkedListTest {
    public static void main(String[] args) {
        List<String> list = new LinkedList<>();

        //添加元素
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("a");
        //获取元素
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        System.out.println("------------------");

        for (String str:list){
            System.out.println(str);
        }
    }
}

LinkedList的使用（非List标准）

public class LinkedListTest {
    public static void main(String[] args) {

        /**
         * 基于List标准
         */
        List<String> list = new LinkedList<>();

        //添加元素
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("a");
        //获取元素
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        System.out.println("------------------");

        for (String str:list){
            System.out.println(str);
        }
        
        System.out.println("--------addFirst----------");

        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.addFirst("a");
        linkedList.addFirst("b");
        linkedList.addFirst("c");

        for (String str:linkedList){
            System.out.println(str);//c b a
        }

        System.out.println("----------addLast---------");
        linkedList.addLast("a");
        linkedList.addLast("b");
        linkedList.addLast("c");

        for (String str:linkedList){
            System.out.println(str);//c b a a b c
        }

        System.out.println("---------getFirst---getLast-------");
        String l1 = linkedList.getFirst();
        System.out.println(l1);
        String l2 = linkedList.getLast();
        System.out.println(l2);

        System.out.println("--------removeFirst-----------");
        String l3 = linkedList.removeFirst();
        System.out.println(l3);
        String l4 = linkedList.removeFirst();
        System.out.println(l4);

        System.out.println("--------removeFirst-----------");
        String l5 = linkedList.removeLast();
        System.out.println(l3);
        String l6 = linkedList.removeLast();
        System.out.println(l4);

        System.out.println("---------pop--------");
        String l7 = linkedList.pop();
        System.out.println(l7);
        for (String str:linkedList){
            System.out.println(str);
        }

        System.out.println("------push-------");
        linkedList.push("love");
        for (String str:linkedList){
            System.out.println(str);
        }

        System.out.println("-------isEmpty--------");
        boolean flag = linkedList.isEmpty();
        System.out.println(flag);
        
         System.out.println("---------指定位置add-----------");
        linkedList.add(2,"ad");//给定索引不能大于元素个数，从0开始，有序性，不能隔着挂载
        for (String str:linkedList){
            System.out.println(str);
        }
    }
}

LinkedList源码分析/P200

中间节点不仅要存储元素对象的地址，还要存储前一个、后一个节点对象的地址，没有自身节点的地址吗？

二分法查找提高效率

指定位置增删元素的第一步：二分法定位