转载

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

PS:推荐大家先去了解一下链表这个数据结构。

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

首先,看他们类的定义可以发现:

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

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

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

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

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

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

ArrayList

成员变量

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

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

get()方法

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

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

add()方法

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

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

remove()方法

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

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

LinkedList

成员变量

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

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

get()方法

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

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

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

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

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

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

add()方法

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

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

remove()方法

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

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的,那么当添加的元素过多,他们怎么扩容呢?

ArrayList:

ArrayList使用数组存储元素,因此扩容时为:

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

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

int newCapacity = oldCapacity + (oldCapacity >> 1);
复制代码

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

LinkedList:

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

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

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

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

2018-10-11 完成

原文  https://juejin.im/post/5cff45ac6fb9a07ecd3d52bf
正文到此结束
Loading...