List集合源码剖析

这是我参与11月更文挑战的第10天，活动详情查看：2021最后一次更文挑战！

大家都知道，List集合有三个常用子类：

ArrayList：底层结构是数组。线程不安全
LinkedList：底层结构是双向链表。线程不安全
Vector：底层结构是数组。线程安全

一、ArrayList解析
在这里插入图片描述
首先，我们看一下ArrayList属性

不难发现，底层是个数组，但数组不是定长吗？，因为ArrayList里面有自动扩容机制，所以他可以实现动态增长
再看看构造方法

再看看我们常用的方法：

添加元素时，我们首先应该检查该list是否需要扩容，才能插入元素
在这里插入图片描述
随后调用ensureExplicitCapacity（）来明确容量，我们再去看看这个方法写了什么

同样，我们去看看grow方法

扩容之后，他又调用copyOf方法，将原数据拷贝到新数组，
再去看copyOf方法

故此时，我们知道add（）实现时，首先检查数组容量是否足够，若不足

扩容到原来的1.5倍
第一次扩容后，若容量还是小于minCapacity，就将容量扩充为minCapacity
足够，直接添加
不足够，扩容后添加

再看看这个方法
在这里插入图片描述
接着往下看

此方法是由C/C++写的。
在看get方法：
不用想也知道分为2步：

检查角标是否越界
返回元素

在这里插入图片描述

set方法

在这里插入图片描述
默认插入数组末尾。

2. remove方法：

ArrayList在增长时需要数组拷贝复制，它的初始容量是10，每次扩容都增加为原来的1.5倍
删除元素不会减少容量，若希望减少，则调用trimToSize（）方法，
线程非安全，可以存放null值
因为其底层是数组，故其查询效率高，增删效率低
在这里插入图片描述
vector和ArrayList的区别：
vector与ArrayList最大的区别就是同步（线程安全）
方法上都加了synchronized的关键字。

如果想要ArrayList实现同步，可以这样

List list = (List) Collections.synchronizedList(new ArrayList<Integer>());
复制代码

还有一个区别，vector扩容会变为原来的2倍。
在这里插入图片描述
二、LinkedList：

实现了Deque接口，故我们可以操作它向队列和栈一样

看完变量，我们便知道了他是由双向链表实现的，故其增删效率肯定高于ArrayList
构造方法：

1.add：

2. remove：

其实主要还是改变last和next节点（变量）
3. get：
在这里插入图片描述

可以看见，get元素时遍历了链表，所以其查询效率较低。但为了加快速度，此处先判断下标若是小于长度的一半，就从头遍历，反之从尾遍历。（稍微快点）
set方法：

和get方法一样，根据下标判断如何遍历。
总结一下：