关于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插入做下比照，如下；

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

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，头插源码验证

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

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

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，尾插源码验证

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

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

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，两头插入源码验证

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

序号	办法	形容
1	list.remove();	与removeFirst()统一
2	list.remove(1);	删除Idx=1的地位元素节点，须要遍历定位
3	list.remove(“a”);	删除元素=”a”的节点，须要遍历定位
4	list.removeFirst();	删除首位节点
5	list.removeLast();	删除结尾节点
6	list.removeAll(Arrays.asList(“a”, “b”));	依照汇合批量删除，底层是Iterator删除

源码：

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

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

获取待删除节点的信息；元素item、元素下一个节点next、元素上一个节点prev。
如果上个节点为空则把待删除元素的下一个节点赋值给首节点，否则把待删除节点的下一个节点，赋值给待删除节点的上一个节点的子节点。
同样待删除节点的下一个节点next，也执行2步骤同样操作。
最初是把删除节点设置为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以上

关于java:面经手册-第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(流)

五、总结

六、系列文章

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于java:面经手册-第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(流)

五、总结

六、系列文章

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复