Arraylist和linkedlist的区别(JDK源码阅读)

快来打我* 2022-10-02 04:58 159阅读 0赞

小城大白兔 2019-06-17 08:01:00

ArrayList和LinkedList可以说是日常业务开发中最常使用的容器类了，同时，他们的区别也是面试高发区，虽然很简单，但是我们总是不能说的完整，今天就通过对他们源码的阅读来进一步加深理解。

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK]

首先，看他们类的定义可以发现：

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 1]

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 2]

他们都是实现了List接口，这个接口干了什么呢？

这个接口定义了对列表的一些基本操作，如add,contains,indexof,remove等基本方法，由他的实现类各自进行实现。

因此，当你只是需要一个列表进行常规的添加移除查找操作，那么ArrayList和LinkedList在使用体验(不考虑性能)上基本没有区别，你甚至不用关心他的内部实现，而是调用一些List接口的方法就ok。

那么他们的具体实现有哪些区别呢？

下面对他们常用的方法进行源码的阅读。

# 一、ArrayList #

# 1、成员变量 #

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 3]

ArrayList有两个成员变量，图中可以看到，一个Object的数组，一个int类型的size，用来定义数组的大小。

# 2、get()方法 #

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 4]

首先检查传入的index，然后返回数组在该index的值。

# 3、add()方法 #

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 5]

首先确保容量够用，然后**将新加入的对象放在数组尾部。**

# 4、remove()方法 #

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 6]

首先确保容量够用，然后计算出需要移动的数量，**例如size=10，要删除index=5的元素，则需要移动后面的四个元素，然后调用System.arraycopy()方法，将数组的后面4个依次向前移动一位，然后将数组最后一位置为null。**

# 二、LinkedList #

# 1、成员变量 #

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 7]

LinkedList本身的属性比较少，主要有三个，一个是size，表明当前有多少个节点；一个是first代表第一个节点；一个是last代表最后一个节点。

get()方法

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 8]

首先检查传入的index是否合法，然后调用了node(index)方法，那么来看看node()方法。

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 9]

判断index值是否大于总数的一半。

如果小于，则从first节点向后遍历，直到找到index节点，然后返回该节点的值。

如果大于，则从last节点向前遍历，直到找到index节点，然后返回该节点的值。

# 2、add()方法 #

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 10]

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 11]

add方法，直接调用了linklast方法，将传入的值作为最后一个节点链接在链表上。

# 3、remove()方法 #

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 12]

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 13]

remove方法的思路是什么呢？从头开始遍历链表，当找到要删除的节点，将他删除。删除的方法呢？将该节点的前后节点链接起来，类似于下图：

# 三、对比 #

由上面的常用方法可以发现

**1、ArrayList使用数组存储元素，因此在查询时速度较快，**直接返回该位置的元素即可，时间复杂度为O(1);

而LinkedList使用双向链表存储元素，在查询时需要从头或者尾遍历至查询元素，时间复杂度为O(n/2);

**2、**还是因为存储方式的问题，**ArrayList在插入或者删除时，需要移动插入位置之后的所有元素，因此速度较慢，**时间复杂度为O(n)。而**LinkedList只需要找到该位置，移动”指针”即可,**时间复杂度为O(1)。

# **四、结论** #

其实在日常的开发中，ArrayList更受欢迎，而且可以完成很多的任务，但是仍有一些特殊的情景适合使用LinkedList。他们的使用场景如下：

**当你对列表更多的进行查询，即获取某个位置的元素时，应当优先使用ArrayList；**

**当你对列表需要进行频繁的删除和增加，而很少使用查询时，优先使用LinkedList；**

# 五、注意事项 #

1、上述结论适用于普遍的情景，有些极端情况不一定符合。比如频繁的在数组结尾附近插入数据，ArrayList也快于LinkedList。

2、LinkedList使用的空间大于ArrayList，因为本质上，ArrayList在每个位置存储了元素，而LinkedList存储了元素+前面节点+后面节点。

# 六、扩展 #

我们知道ArrayList和LinkedList都是有size的，那么当添加的元素过多，他们怎么扩容呢？

**（1）ArrayList：**

ArrayList使用数组存储元素，因此扩容时为：

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 14]

可以看到，**每次扩容后的大小为之前的1.5倍。**

int newCapacity = oldCapacity + (oldCapacity >> 1);

而且之后有一个复制全部元素的操作，这个操作很费时间。

**（2）LinkedList**

由于**LinkedList是一个双向链表，因此不需要扩容机制，直接在前后添加元素即可。**

**因此：在使用ArrayList时，如果你能预估大小，最好直接定义初始容量，这样能节省频繁的扩容带来的额外开支。**

初始化定义容量的构造方法为：

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 15]

**更多资料展示如下，需要的小伙伴们转发，私信口令：资料，即可获得以下资料！！！**

![Arraylist和linkedlist的区别(JDK源码阅读)][Arraylist_linkedlist_JDK 16]

[Arraylist_linkedlist_JDK]: http://p1.pstatp.com/large/pgc-image/a10b24e95e1c47318085494bb3a8303a
[Arraylist_linkedlist_JDK 1]: /images/20220113/4b4736e4680146a49e44b94febbc2bdb.png
[Arraylist_linkedlist_JDK 2]: /images/20220113/b0398d6aca6942fe94fdfb9d6c87c060.png
[Arraylist_linkedlist_JDK 3]: http://p1.pstatp.com/large/pgc-image/e5cbbc3238cb476087d7d38bd2b9098b
[Arraylist_linkedlist_JDK 4]: http://p1.pstatp.com/large/pgc-image/03fd2894407040ce97671556c88272c2
[Arraylist_linkedlist_JDK 5]: http://p1.pstatp.com/large/pgc-image/da3021c260994df99b7b145cf6891cc0
[Arraylist_linkedlist_JDK 6]: /images/20220113/8b9bc04989ea4c22b6d653c7517c6e43.png
[Arraylist_linkedlist_JDK 7]: /images/20220113/fed50b7fbb6a410c8d10150736a18aa8.png
[Arraylist_linkedlist_JDK 8]: http://p1.pstatp.com/large/pgc-image/4b9a45d7af0540819abe4060a167b0d8
[Arraylist_linkedlist_JDK 9]: http://p1.pstatp.com/large/pgc-image/500897b070084052a81eb862b0ec109f
[Arraylist_linkedlist_JDK 10]: /images/20220113/37111dff652c42f7b5d9410aed11f182.png
[Arraylist_linkedlist_JDK 11]: http://p1.pstatp.com/large/pgc-image/28f35ea925204ecdb29782071578b89b
[Arraylist_linkedlist_JDK 12]: http://p1.pstatp.com/large/pgc-image/2ecfee00a6094e7b9b5ea8e70c58b4b7
[Arraylist_linkedlist_JDK 13]: /images/20220113/ede74c89736748769e5a8b25eb399dc8.png
[Arraylist_linkedlist_JDK 14]: http://p1.pstatp.com/large/pgc-image/437fc61f9f7c4e8dbd8c54b34ab9b62b
[Arraylist_linkedlist_JDK 15]: http://p1.pstatp.com/large/pgc-image/02db3584a68b4ff4800a7071de09af25
[Arraylist_linkedlist_JDK 16]: http://p1.pstatp.com/large/pgc-image/bad9fd93451e4310a4c5178aa2f16cdd