List集合源码剖析

大家都知道，List集合有三个常用子类：
ArrayList：底层结构是数组。线程不安全
LinkedList：底层结构是双向链表。线程不安全
Vector：底层结构是数组。线程安全
一、ArrayList解析

首先，我们看一下ArrayList属性

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

再看看我们常用的方法：

添加元素时，我们首先应该检查该list是否需要扩容，才能插入元素

随后调用ensureExplicitCapacity（）来明确容量，我们再去看看这个方法写了什么

同样，我们去看看grow方法

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

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

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

接着往下看

此方法是由C/C++写的。
在看get方法：
不用想也知道分为2步：
检查角标是否越界
返回元素

set方法

默认插入数组末尾。

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
构造方法：

add：

remove：

其实主要还是改变last和next节点（变量）
get：

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

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

底层实现是数组，故其查询效率高，线程非安全
ArrayList的默认初始化容量是10，每次扩容时候增加原先容量的一半，也就是变为原来的1.5倍
在增删时候，需要数组的拷贝复制(navite 方法由C/C++实现)

LinkedList：

底层实现是双向链表[双向链表方便实现往前遍历]，故其增删效率高，也是线程非安全的
Vector：
底层是数组，现在已少用，被ArrayList替代，原因有两个：
Vector所有方法都是同步，有性能损失。
Vector初始length是10 超过length时以100%比率增长，相比于ArrayList更多消耗内存。
和ArrayList最大的区别便是线程安全，扩容时变为原来2倍

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/96860.html

List集合源码剖析

相关推荐