关于java:面经手册-第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 一些雷同的形式，来初始化入参，如下这四种形式；

@Test
public 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 插入做下比照，如下；

看上图咱们能够剖析出几点；

1. ArrayList 头插时，须要把数组元素通过 Arrays.copyOf 的形式把数组元素移位，如果容量有余还须要扩容。
2. 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，头插源码验证

@Test
public 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));
}

@Test
public 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 插入做下比照，如下；

看上图咱们能够剖析出几点；

1. ArrayList 尾插时，是不须要数据位移的，比拟耗时的是数据的扩容时，须要拷贝迁徙。
2. 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，尾插源码验证

@Test
public 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));
}

@Test
public 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 插入做下比照，如下；

看上图咱们能够剖析出几点；

1. ArrayList 两头插入，首先咱们晓得他的定位工夫复杂度是 O(1)，比拟耗时的点在于数据迁徙和容量有余的时候扩容。
2. 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，两头插入源码验证

@Test
public 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));
}

@Test
public 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 删除操作方法

源码：

@Test
public 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;
}

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

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

4. 遍历

接下来说下遍历，ArrayList 与 LinkedList 的遍历都是通用的，根本包含 5 种形式。

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

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

4.1 一般 for 循环

@Test
public 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 循环

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

4.3 Iterator 遍历

@Test
public 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 循环

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

4.5 stream(流)

@Test
public 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 节俭空间，首先它所占用的内存不是间断的，其次他还须要大量的实例化对象发明节点。尽管不肯定节俭空间，但链表构造也是十分优良的数据结构，它能在你的程序设计中起着十分优良的作用，例如可视化的链路追踪图，就是须要链表构造，并须要每个节点自旋一次，用于串联业务。
• 程序的精华往往就是数据结构的设计，这能为你的程序开发提供出十分高的效率扭转。可能目前你还不能用到，但万一有一天你须要去造???? 火箭了呢？

六、系列文章

• ArrayList 也这么多常识？一个指定地位插入就把谢飞机面晕了！
• HashMap 外围常识，扰动函数、负载因子、扩容链表拆分，深度学习
• 简历写成这样，谁要你呀!
• 工作 5 年的学习路线资源汇总
• 懂设计模式能力面试到 20k 以上