面经手册 · 第 8 篇《LinkedList 插入速度比 ArrayList 快？你确定吗？》

小傅哥

关注

发布于: 2020 年 08 月 31 日

面经手册 · 第8篇《LinkedList插入速度比ArrayList快？你确定吗？》

作者：小傅哥

博客：https://bugstack.cn

沉淀、分享、成长，让自己和他人都能有所收获！😄

一、前言

你以为考你个数据结构是要造火箭？

🚕汽车 75 马力就够奔跑了，那你怎么还想要 2.0 涡轮+9AT 呢？大桥两边的护栏你每次走的时候都会去摸吗？那怎么没有护栏的大桥你不敢上呢？

很多时候，你额外的能力才是自身价值的体现，不要以为你的能力就只是做个业务开发每天 CRUD，并不是产品让你写 CRUD，而是因为你的能力只能产品功能设计成 CRUD。

就像数据结构、算法逻辑、源码技能，它都是可以为你的业务开发赋能的，也是写出更好、更易扩展程序的根基，所以学好这份知识非常有必要。

*本文涉及了较多的代码和实践验证图稿，欢迎关注公众号：bugstack虫洞栈，回复下载得到一个链接打开后，找到 ID：19🤫获取！*

二、面试题

谢飞机，ArrayList 资料看了吧？嗯，那行问问你哈🦀

**问**：ArrayList 和 LinkedList，都用在什么场景呢？

**答**：啊，这我知道了。ArrayList 是基于数组实现、LinkedList 是基于双向链表实现，所以基于数据结构的不同，遍历和查找多的情况下用 ArrayList、插入和删除频繁的情况下用 LinkedList。

**问**：嗯，那 LinkedList 的插入效率一定比 ArrayList 好吗？

**答**：对，好！

送你个飞机✈，回去等消息吧！

其实，飞机回答的也不是不对，只是不全面。出门后不甘心买瓶肥宅水又回来，跟面试官聊了 2 个点，要到了两张图，如下；

如图，分别是；10万、100万、1000万，数据在两种集合下不同位置的插入效果，所以：，不能说 LinkedList 插入就快，ArrayList 插入就慢，还需要看具体的操作情况。

接下来我们带着数据结构和源码，具体分析下。

三、数据结构

Linked + List = 链表 + 列表 = LinkedList = 链表列表

LinkedList，是基于链表实现，由双向链条 next、prev，把数据节点穿插起来。所以，在插入数据时，是不需要像我们上一章节介绍的 ArrayList 那样，扩容数组。

但，又不能说所有的插入都是高效，比如中间区域插入，他还需要遍历元素找到插入位置。具体的细节，我们在下文的源码分析中进行讲解，也帮谢飞机扫除疑惑。

四、源码分析

1. 初始化

与 ArrayList 不同，LinkedList 初始化不需要创建数组，因为它是一个链表结构。而且也没有传给构造函数初始化多少个空间的入参，例如这样是不可以的，如下；

但是，构造函数一样提供了和 ArrayList 一些相同的方式，来初始化入参，如下这四种方式；

@Testpublic void test_init() {    // 初始化方式；普通方式    LinkedList<String> list01 = new LinkedList<String>();    list01.add("a");    list01.add("b");    list01.add("c");    System.out.println(list01);        // 初始化方式；Arrays.asList    LinkedList<String> list02 = new LinkedList<String>(Arrays.asList("a", "b", "c"));    System.out.println(list02);        // 初始化方式；内部类    LinkedList<String> list03 = new LinkedList<String>()\\{        {add("a");add("b");add("c");}    \\};    System.out.println(list03);        // 初始化方式；Collections.nCopies    LinkedList<Integer> list04 = new LinkedList<Integer>(Collections.nCopies(10, 0));    System.out.println(list04);}
// 测试结果
[a, b, c][a, b, c][a, b, c][0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Process finished with exit code 0

复制代码

这些方式都可以初始化操作，按需选择即可。

2. 插入

LinkedList 的插入方法比较多，List 中接口中默认提供的是 add，也可以指定位置插入。但在 LinkedList 中还提供了头插addFirst和尾插addLast。

关于插入这部分就会讲到为什么；有的时候 LinkedList 插入更耗时、有的时候 ArrayList 插入更好。

2.1 头插

先来看一张数据结构对比图，回顾下 ArrayList 的插入也和 LinkedList 插入做下对比，如下；

看上图我们可以分析出几点；

ArrayList 头插时，需要把数组元素通过Arrays.copyOf的方式把数组元素移位，如果容量不足还需要扩容。
LinkedList 头插时，则不需要考虑扩容以及移位问题，直接把元素定位到首位，接点链条链接上即可。

2.1.1 源码

这里我们再对照下LinkedList头插的源码，如下；

private void linkFirst(E e) {    final Node<E> f = first;    final Node<E> newNode = new Node<>(null, e, f);    first = newNode;    if (f == null)        last = newNode;    else        f.prev = newNode;    size++;    modCount++;}

复制代码

first，首节点会一直被记录，这样就非常方便头插。
插入时候会创建新的节点元素，new Node<>(null, e, f)，紧接着把新的头元素赋值给 first。
之后判断 f 节点是否存在，不存在则把头插节点作为最后一个节点、存在则用 f 节点的上一个链条 prev 链接。
最后记录 size 大小、和元素数量 modCount。modCount 用在遍历时做校验，modCount != expectedModCount

2.1.2 验证

ArrayList、LinkeList，头插源码验证

@Testpublic void test_ArrayList_addFirst() {    ArrayList<Integer> list = new ArrayList<Integer>();    long startTime = System.currentTimeMillis();    for (int i = 0; i < 10000000; i++) {        list.add(0, i);    }    System.out.println("耗时：" + (System.currentTimeMillis() - startTime));}
@Testpublic void test_LinkedList_addFirst() {    LinkedList<Integer> list = new LinkedList<Integer>();    long startTime = System.currentTimeMillis();    for (int i = 0; i < 10000000; i++) {        list.addFirst(i);    }    System.out.println("耗时：" + (System.currentTimeMillis() - startTime));}

复制代码

比对结果：

这里我们分别验证，10 万、100 万、1000 万的数据量，在头插时的一个耗时情况。
如我们数据结构对比图中一样，ArrayList 需要做大量的位移和复制操作，而 LinkedList 的优势就体现出来了，耗时只是实例化一个对象。

2.2 尾插

先来看一张数据结构对比图，回顾下 ArrayList 的插入也和 LinkedList 插入做下对比，如下；

看上图我们可以分析出几点；

ArrayList 尾插时，是不需要数据位移的，比较耗时的是数据的扩容时，需要拷贝迁移。
LinkedList 尾插时，与头插相比耗时点会在对象的实例化上。

2.2.1 源码

这里我们再对照下LinkedList尾插的源码，如下；

void linkLast(E e) {    final Node<E> l = last;    final Node<E> newNode = new Node<>(l, e, null);    last = newNode;    if (l == null)        first = newNode;    else        l.next = newNode;    size++;    modCount++;}

复制代码

与头插代码相比几乎没有什么区别，只是 first 换成 last
耗时点只是在创建节点上，Node<E>

2.2.2 验证

ArrayList、LinkeList，尾插源码验证

@Testpublic void test_ArrayList_addLast() {    ArrayList<Integer> list = new ArrayList<Integer>();    long startTime = System.currentTimeMillis();    for (int i = 0; i < 10000000; i++) {        list.add(i);    }    System.out.println("耗时：" + (System.currentTimeMillis() - startTime));}
@Testpublic void test_LinkedList_addLast() {    LinkedList<Integer> list = new LinkedList<Integer>();    long startTime = System.currentTimeMillis();    for (int i = 0; i < 1000000; i++) {        list.addLast(i);    }    System.out.println("耗时：" + (System.currentTimeMillis() - startTime));}

复制代码

比对结果：

这里我们分别验证，10 万、100 万、1000 万的数据量，在尾插时的一个耗时情况。
如我们数据结构对比图中一样，ArrayList 不需要做位移拷贝也就不那么耗时了，而 LinkedList 则需要创建大量的对象。所以这里 ArrayList 尾插的效果更好一些。

2.3 中间插

先来看一张数据结构对比图，回顾下 ArrayList 的插入也和 LinkedList 插入做下对比，如下；

看上图我们可以分析出几点；

ArrayList 中间插入，首先我们知道他的定位时间复杂度是 O(1)，比较耗时的点在于数据迁移和容量不足的时候扩容。
LinkedList 中间插入，链表的数据实际插入时候并不会怎么耗时，但是它定位的元素的时间复杂度是 O(n)，所以这部分以及元素的实例化比较耗时。

2.3.1 源码

这里看下 LinkedList 指定位置插入的源码；

使用 add(位置、元素)方法插入：

public void add(int index, E element) {    checkPositionIndex(index);    if (index == size)        linkLast(element);    else        linkBefore(element, node(index));}

复制代码

位置定位 node(index)：

Node<E> node(int index) {    // assert isElementIndex(index);    if (index < (size >> 1)) {        Node<E> x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {        Node<E> x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}

复制代码

size >> 1，这部分的代码判断元素位置在左半区间，还是右半区间，在进行循环查找。

执行插入：

void linkBefore(E e, Node<E> succ) {    // assert succ != null;    final Node<E> pred = succ.prev;    final Node<E> newNode = new Node<>(pred, e, succ);    succ.prev = newNode;    if (pred == null)        first = newNode;    else        pred.next = newNode;    size++;    modCount++;}

复制代码

找到指定位置插入的过程就比较简单了，与头插、尾插，相差不大。
整个过程可以看到，插入中比较耗时的点会在遍历寻找插入位置上。

2.3.2 验证

ArrayList、LinkeList，中间插入源码验证

@Testpublic void test_ArrayList_addCenter() {    ArrayList<Integer> list = new ArrayList<Integer>();    long startTime = System.currentTimeMillis();    for (int i = 0; i < 10000000; i++) {        list.add(list.size() >> 1, i);    }    System.out.println("耗时：" + (System.currentTimeMillis() - startTime));}
@Testpublic void test_LinkedList_addCenter() {    LinkedList<Integer> list = new LinkedList<Integer>();    long startTime = System.currentTimeMillis();    for (int i = 0; i < 1000000; i++) {        list.add(list.size() >> 1, i);    }    System.out.println("耗时：" + (System.currentTimeMillis() - startTime));}

复制代码

比对结果：

这里我们分别验证，10 万、100 万、1000 万的数据量，在中间插时的一个耗时情况。
可以看到 Linkedlist 在中间插入时，遍历寻找位置还是非常耗时了。所以不同的情况下，需要选择不同的 List 集合做业务。

3. 删除

讲了这么多插入的操作后，删除的知识点就很好理解了。与 ArrayList 不同，删除不需要拷贝元素，LinkedList 是找到元素位置，把元素前后链连接上。基本如下图；

确定出要删除的元素 x，把前后的链接进行替换。
如果是删除首尾元素，操作起来会更加容易，这也就是为什么说插入和删除快。但中间位置删除，需要遍历找到对应位置。

3.1 删除操作方法

源码：

@Testpublic void test_remove() {    LinkedList<String> list = new LinkedList<String>();    list.add("a");    list.add("b");    list.add("c");        list.remove();    list.remove(1);    list.remove("a");    list.removeFirst();    list.removeLast();    list.removeAll(Arrays.asList("a", "b"));}

复制代码

3.2 源码

删除操作的源码都差不多，分为删除首尾节点与其他节点时候，对节点的解链操作。这里我们举例一个删除其他位置的源码进行学习，如下；

list.remove("a");

public boolean remove(Object o) {    if (o == null) {        for (Node<E> x = first; x != null; x = x.next) {            if (x.item == null) {                unlink(x);                return true;            }        }    } else {        for (Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item)) {                unlink(x);                return true;            }        }    }    return false;}

复制代码

这一部分是元素定位，和 unlink(x)解链。循环查找对应的元素，这部分没有什么难点。

unlink(x)解链

E unlink(Node<E> x) {    // assert x != null;    final E element = x.item;    final Node<E> next = x.next;    final Node<E> prev = x.prev;        if (prev == null) {        first = next;    } else {        prev.next = next;        x.prev = null;    }        if (next == null) {        last = prev;    } else {        next.prev = prev;        x.next = null;    }        x.item = null;    size--;    modCount++;    return element;}

复制代码

这部分源码主要有以下几个知识点；

获取待删除节点的信息；元素 item、元素下一个节点 next、元素上一个节点 prev。
如果上个节点为空则把待删除元素的下一个节点赋值给首节点，否则把待删除节点的下一个节点，赋值给待删除节点的上一个节点的子节点。
同样待删除节点的下一个节点 next，也执行 2 步骤同样操作。
最后是把删除节点设置为 null，并扣减 size 和 modeCount 数量。

4. 遍历

接下来说下遍历，ArrayList 与 LinkedList 的遍历都是通用的，基本包括 5 种方式。

这里我们先初始化出待遍历的集合 1 千万数据；

int xx = 0;@Beforepublic void init() {    for (int i = 0; i < 10000000; i++) {        list.add(i);    }}

复制代码

4.1 普通 for 循环

@Testpublic void test_LinkedList_for0() {    long startTime = System.currentTimeMillis();    for (int i = 0; i < list.size(); i++) {        xx += list.get(i);    }    System.out.println("耗时：" + (System.currentTimeMillis() - startTime));}

复制代码

4.2 增强 for 循环

@Testpublic void test_LinkedList_for1() {    long startTime = System.currentTimeMillis();    for (Integer itr : list) {        xx += itr;    }    System.out.println("耗时：" + (System.currentTimeMillis() - startTime));}

复制代码

4.3 Iterator 遍历

@Testpublic void test_LinkedList_Iterator() {    long startTime = System.currentTimeMillis();    Iterator<Integer> iterator = list.iterator();    while (iterator.hasNext()) {        Integer next = iterator.next();        xx += next;    }    System.out.println("耗时：" + (System.currentTimeMillis() - startTime))}

复制代码

4.4 forEach 循环

@Testpublic void test_LinkedList_forEach() {    long startTime = System.currentTimeMillis();    list.forEach(integer -> {        xx += integer;    });    System.out.println("耗时：" + (System.currentTimeMillis() - startTime));}

复制代码

4.5 stream(流)

@Testpublic void test_LinkedList_stream() {    long startTime = System.currentTimeMillis();    list.stream().forEach(integer -> {        xx += integer;    });    System.out.println("耗时：" + (System.currentTimeMillis() - startTime));}

复制代码

那么，以上这 5 种遍历方式谁最慢呢？按照我们的源码学习分析下吧，欢迎留下你的答案在评论区！

五、总结

ArrayList 与 LinkedList 都有自己的使用场景，如果你不能很好的确定，那么就使用 ArrayList。但如果你能确定你会在集合的首位有大量的插入、删除以及获取操作，那么可以使用 LinkedList，因为它都有相应的方法；addFirst、addLast、removeFirst、removeLast、getFirst、getLast，这些操作的时间复杂度都是 O(1)，非常高效。
LinkedList 的链表结构不一定会比 ArrayList 节省空间，首先它所占用的内存不是连续的，其次他还需要大量的实例化对象创造节点。虽然不一定节省空间，但链表结构也是非常优秀的数据结构，它能在你的程序设计中起着非常优秀的作用，例如可视化的链路追踪图，就是需要链表结构，并需要每个节点自旋一次，用于串联业务。
程序的精髓往往就是数据结构的设计，这能为你的程序开发提供出非常高的效率改变。可能目前你还不能用到，但万一有一天你需要去造🚀火箭了呢？

六、系列文章

发布于: 2020 年 08 月 31 日阅读数: 833

原文链接:【http://xie.infoq.cn/article/9f116bfad546bc5fd0538ba56】。文章转载请联系作者。

小傅哥

关注

沉淀、分享、成长，让自己和他人都有所收获 2019.04.03 加入

作者小傅哥，一线互联网 java 工程师、架构师，开发过交易&营销、写过运营&活动、设计过中间件也倒腾过中继器、IO板卡。不只是写Java语言，也搞过C#、PHP，是一个技术活跃的折腾者。

评论 (1 条评论)

发布

二哥不再迷茫

如果只是测试插入速度的话，用一个固定的Integer比较好吧，这样计算的时间就不包含自动转换之类的耗时了。我本地1000万数据，ArrayList尾插入Integer 1 的话耗时100多毫秒。

2020 年 08 月 31 日 18:08

 0 回复

没有更多了

创作场景

面经手册 · 第 8 篇《LinkedList 插入速度比 ArrayList 快？你确定吗？》

一、前言

二、面试题

三、数据结构

四、源码分析

1. 初始化

2. 插入

2.1 头插

2.1.1 源码

2.1.2 验证

2.2 尾插

2.2.1 源码

2.2.2 验证

2.3 中间插

2.3.1 源码

2.3.2 验证

3. 删除

3.1 删除操作方法

3.2 源码

4. 遍历

4.1 普通 for 循环

4.2 增强 for 循环

4.3 Iterator 遍历

4.4 forEach 循环

4.5 stream(流)

五、总结

六、系列文章

小傅哥

评论 (1 条评论)