【容器源码篇】List容器（LinkedList，ArrayList，Vector的特点）

⭐容器继承关系

🎈List容器

🗒️LinkedList源码解析

双向链表结构：LinkedList 内部以双向链表的形式存储元素，每个节点包含对前后节点的引用。这种结构使得在链表中插入和删除元素的操作效率较高，因为不需要像数组那样移动大量元素。

非同步（非线程安全）：LinkedList 不是线程安全的，如果需要在多线程环境下使用，需要手动进行同步处理，或者考虑使用线程安全的容器类。

插入和删除效率高：由于双向链表的特性，对于大量的插入和删除操作，LinkedList 的效率通常比 ArrayList 更高。

随机访问效率低：与 ArrayList 不同，LinkedList 的随机访问（根据索引查找元素）效率较低，因为需要从头或尾开始遍历链表，直到找到目标位置。

空间开销较大：相比于数组，链表结构本身会带来一定的额外空间开销，因为需要存储节点之间的引用关系。

LinkedList采用双向链表实现的列表

其中Node是私有的内部类

构造函数

获取第一个元素和最后一个元素

移除第一个并返回第一个元素，移除最后一个并返回最后一个元素

unlinkFirst()方法 和 unlinkLast()方法

首先获取第一个节点存储的元素和下一个节点的引用。
将当前节点的item和next置为null，帮助垃圾回收。（如果不将其引用设为null，尽管该节点已经从链表结构中移除，但由于可能存在其他地方仍持有对该节点的引用，导致垃圾回收器无法正确判断其是否可回收）
更新链表的第一个节点为下一个节点。
如果下一个节点为空，则更新最后一个节点为null；否则更新下一个节点的prev(前一个)为null。
减少链表的大小并更新 修改次数(modCount++)。
返回被删除节点存储的元素。

remove()方法

首先保存节点x存储的元素、下一个节点、上一个节点的引用。
如果节点x没有上一个节点，则说明它是链表的第一个节点，将链表的第一个节点指向下一个节点。
如果节点x没有下一个节点，则说明它是链表的最后一个节点，将链表的最后一个节点指向上一个节点。
更新节点x的上一个节点和下一个节点的引用为null。
将节点x的元素引用设置为null，减少内存占用。
更新链表的大小和修改次数。
返回节点x存储的元素。

add()方法

首先，函数获取当前链表的最后一个节点last。
创建一个新的节点newNode，将其值设置为e，并将其next指向null。
将last指向新节点newNode。
如果链表为空（即last为null），则将first也指向新节点newNode。
如果链表不为空，则将last的next指向新节点newNode。

get()获取元素

该函数用于获取链表中指定索引位置的节点。若索引值小于链表长度的一半，则从头节点开始遍历，若索引值大于等于链表长度的一半，则从尾节点开始遍历，最后返回找到的节点

遍历

🔎三种遍历方式的耗时

package List;

import java.util.Iterator;
import java.util.LinkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<Integer> list=new LinkedList<>();
        for(int i=0;i<10;i++){
            list.add(i);
        }
        System.out.println(list.size());
        list.addFirst(10);
        list.add(3,20);
        list.remove(3);
        LinkedList<Integer>list1=new LinkedList<>();
        for(int i=0;i<100000;i++){
            list.add(i);
        }
        traverseByIterator(list);
        traverseByIndex(list);
        traverseByFor(list);
    }
    public static void traverseByIterator(LinkedList<Integer> list){
        long start=System.currentTimeMillis();
        Iterator<Integer>iterator=list.iterator();
        while(iterator.hasNext()){
            iterator.next();
        }
        long end=System.currentTimeMillis();
        System.out.println("迭代器: "+(end-start));
    }
    public static void traverseByIndex(LinkedList<Integer> list){
        long start=System.currentTimeMillis();
        for(int i=0;i<list.size();i++){
            list.get(i);
        }
        long end=System.currentTimeMillis();
        System.out.println("随机索引: "+(end-start));
    }
    public static void traverseByFor(LinkedList<Integer> list){
        long start=System.currentTimeMillis();
        for(Integer i:list){
            i.intValue();
        }
        long end=System.currentTimeMillis();
        System.out.println("for-each: "+(end-start));
    }
}

🗒️ArrayList源码解析

基于数组：ArrayList 内部通过数组来存储元素，可以根据需要自动调整大小。

随机访问效率高：由于基于数组，ArrayList 支持通过索引进行快速的随机访问，获取指定位置的元素效率较高。

非同步（非线程安全）：ArrayList 不是线程安全的，如果需要在多线程环境下使用，需要手动进行同步处理，或者考虑使用线程安全的容器类。

插入和删除效率较低：相对于 LinkedList，在中间插入或删除元素的效率较低，因为需要移动后续元素。

空间管理：由于 ArrayList 的底层是数组，数组的大小是固定的，当元素数量超出数组容量时，会触发扩容操作，这时会重新分配一个更大的数组，并将原数组中的元素复制到新数组中。这种机制可能会带来一定的性能开销。

ArrayList底层基于数组实现

add()方法

向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容，扩容操作最终都是通过grow()方法完成的。

set() 赋值操作

get() 取值操作

remove() 方法

首先，函数进行索引检查，确保指定的索引在有效范围内，否则抛出IndexOutOfBoundsException异常。
然后，更新列表的修改次数modCount。
接着，获取要移除的元素的值并存储在oldValue变量中。
然后，判断要移除的元素 后面还有多少个元素，如果大于0，则使用System.arraycopy方法将后续元素左移，以填补移除元素后留下的空位。
最后，将列表的大小减1，并将最后一个元素置为null，以便垃圾回收器将其回收。
最后，返回被移除的元素的值oldValue。

遍历

toArray()

Fail-Fast机制

ArrayList也采用了快速失败的机制，通过记录modCount参数来实现，在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

🔎三种遍历方式耗时

package List;

import java.util.ArrayList;
import java.util.Iterator;

public class ArrayListDemo {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0;i<5;i++){
            list.add(i);
        }
        list.add(0); //允许有相同的元素
        list.remove(2);
        list.add(3,9);

        //遍历
        ArrayList<Integer>list1=new ArrayList<>();
        for(int i=0;i<100000;i++){
            list1.add(i);
        }
        traverseByIterator(list1);
        traverseByIndex(list1);
        traverseByFor(list1);
    }

    public static void traverseByIterator(ArrayList<Integer> list) {
        long start = System.currentTimeMillis();
        Iterator<Integer> iterator=list.iterator();
        while(iterator.hasNext()){
            iterator.next();
        }
        long end = System.currentTimeMillis();
        System.out.println("迭代器 "+(end-start));
    }
    public static void traverseByIndex(ArrayList<Integer> list) {
        long start = System.currentTimeMillis();
        for(int i=0;i<list.size();i++){
            list.get(i);
        }
        long end = System.currentTimeMillis();
        System.out.println("索引 "+(end-start));
    }
    public static void traverseByFor(ArrayList<Integer> list) {
        long start = System.currentTimeMillis();
        for(Integer i:list){
            i.toString();
        }
        long end = System.currentTimeMillis();
        System.out.println("for "+(end-start));
    }
}

🗒️Vector

线程安全：Vector 是线程安全的，所有方法都使用 synchronized 进行同步，这意味着多个线程可以安全地访问 Vector 的内容而不会出现数据竞争问题。

基于数组：Vector 内部同样使用数组来存储元素，可以根据需要自动调整大小。

插入和删除效率较低：与 ArrayList 类似，在中间插入或删除元素的效率较低，因为需要移动后续元素。同时，由于线程安全性的考虑，Vector 的操作可能比 ArrayList 慢一些。

空间管理：Vector 与 ArrayList 一样，在元素数量超出数组容量时，会触发扩容操作，重新分配更大的数组并将原数组中的元素复制到新数组中。