LinkedList插入速度比ArrayList快？你确定吗？
持续坚持原创输出，点击蓝字关注我吧 作者：小傅哥博客：https://bugstack.cn ❝ 沉淀、分享、成长，让自己和他人都能有所收获！😜 ❞ 目录 一、前言 二、面试题 三、数据结构 四、源码分析 1. 初始化 2. 插入 3. 删除 4. 遍历 五、总结 一、前言 你以为考你个数据结构是要造火箭？ 🚕汽车75马力就够奔跑了，那你怎么还想要2.0涡轮+9AT呢？大桥两边的护栏你每次走的时候都会去摸吗？那怎么没有护栏的大桥你不敢上呢？ 很多时候，你额外的能力才是自身价值的体现，不要以为你的能力就只是做个业务开发每天CRUD，并不是产品让你写CRUD，而是因为你的能力只能产品功能设计成CRUD。 就像数据结构、算法逻辑、源码技能，它都是可以为你的业务开发赋能的，也是写出更好、更易扩展程序的根基，所以学好这份知识非常有必要。 本文涉及了较多的代码和实践验证图稿，欢迎关注公众号：bugstack虫洞栈，回复下载得到一个链接打开后，找到ID：19🤫获取！ 二、面试题 谢飞机，ArrayList资料看了吧？嗯，那行问问你哈🦀 「问」：ArrayList和LinkedList，都用在什么场景呢？ 「答」：啊，这我知道了。ArrayList是基于数组实现、LinkedList是基于双向链表实现，所以基于数据结构的不同，遍历和查找多的情况下用ArrayList、插入和删除频繁的情况下用LinkedList。 「问」：嗯，那LinkedList的插入效率一定比ArrayList好吗？ 「答」：对，好！ 送你个飞机✈，回去等消息吧！ 其实，飞机回答的也不是不对，只是不全面。出门后不甘心买瓶肥宅水又回来，跟面试官聊了2个点，要到了两张图，如下； 小傅哥 bugstack.cn & ArrayList头插、尾插、中间 小傅哥 bugstack.cn & LinkedList头插、尾插、中间 如图，分别是；10万、100万、1000万，数据在两种集合下不同位置的插入效果，「所以：」，不能说LinkedList插入就快，ArrayList插入就慢，还需要看具体的操作情况。 接下来我们带着数据结构和源码，具体分析下。 三、数据结构 Linked + List = 链表 + 列表 = LinkedList = 链表列表 小傅哥 bugstack.cn & LinkedList数据结构 LinkedList，是基于链表实现，由双向链条next、prev，把数据节点穿插起来。所以，在插入数据时，是不需要像我们上一章节介绍的ArrayList那样，扩容数组。 但，又不能说所有的插入都是高效，比如中间区域插入，他还需要遍历元素找到插入位置。具体的细节，我们在下文的源码分析中进行讲解，也帮谢飞机扫除疑惑。 四、源码分析 1. 初始化 与ArrayList不同，LinkedList初始化不需要创建数组，因为它是一个链表结构。而且也没有传给构造函数初始化多少个空间的入参，例如这样是不可以的，如下； 「但是」，构造函数一样提供了和ArrayList一些相同的方式，来初始化入参，如下这四种方式； @Testpublicvoidtest_init(){//初始化方式；普通方式LinkedList<String>list01=newLinkedList<String>();list01.add("a");list01.add("b");list01.add("c");System.out.println(list01);//初始化方式；Arrays.asListLinkedList<String>list02=newLinkedList<String>(Arrays.asList("a","b","c"));System.out.println(list02);//初始化方式；内部类LinkedList<String>list03=newLinkedList<String>()\\{{add("a");add("b");add("c");}\\};System.out.println(list03);//初始化方式；Collections.nCopiesLinkedList<Integer>list04=newLinkedList<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]Processfinishedwithexitcode0 这些方式都可以初始化操作，按需选择即可。 2. 插入 LinkedList的插入方法比较多，List中接口中默认提供的是add，也可以指定位置插入。但在LinkedList中还提供了头插addFirst和尾插addLast。 关于插入这部分就会讲到为什么；有的时候LinkedList插入更耗时、有的时候ArrayList插入更好。 2.1 头插 先来看一张数据结构对比图，回顾下ArrayList的插入也和LinkedList插入做下对比，如下； 小傅哥 bugstack.cn & 插入对比 看上图我们可以分析出几点； ArrayList 头插时，需要把数组元素通过 Arrays.copyOf的方式把数组元素移位，如果容量不足还需要扩容。 LinkedList 头插时，则不需要考虑扩容以及移位问题，直接把元素定位到首位，接点链条链接上即可。 2.1.1 源码 这里我们再对照下LinkedList头插的源码，如下； privatevoidlinkFirst(Ee){finalNode<E>f=first;finalNode<E>newNode=newNode<>(null,e,f);first=newNode;if(f==null)last=newNode;elsef.prev=newNode;size++;modCount++;} first，首节点会一直被记录，这样就非常方便头插。 插入时候会创建新的节点元素， new Node<>(null, e, f)，紧接着把新的头元素赋值给first。 之后判断f节点是否存在，不存在则把头插节点作为最后一个节点、存在则用f节点的上一个链条prev链接。 最后记录size大小、和元素数量modCount。 modCount用在遍历时做校验，modCount != expectedModCount 2.1.2 验证 「ArrayList、LinkeList，头插源码验证」 @Testpublicvoidtest_ArrayList_addFirst(){ArrayList<Integer>list=newArrayList<Integer>();longstartTime=System.currentTimeMillis();for(inti=0;i<10000000;i++){list.add(0,i);}System.out.println("耗时："+(System.currentTimeMillis()-startTime));}@Testpublicvoidtest_LinkedList_addFirst(){LinkedList<Integer>list=newLinkedList<Integer>();longstartTime=System.currentTimeMillis();for(inti=0;i<10000000;i++){list.addFirst(i);}System.out.println("耗时："+(System.currentTimeMillis()-startTime));} 「比对结果：」 这里我们分别验证，10万、100万、1000万的数据量，在头插时的一个耗时情况。 如我们数据结构对比图中一样，ArrayList需要做大量的位移和复制操作，而LinkedList的优势就体现出来了，耗时只是实例化一个对象。 2.2 尾插 先来看一张数据结构对比图，回顾下ArrayList的插入也和LinkedList插入做下对比，如下； 小傅哥 bugstack.cn & 插入对比 看上图我们可以分析出几点； ArrayList 尾插时，是不需要数据位移的，比较耗时的是数据的扩容时，需要拷贝迁移。 LinkedList 尾插时，与头插相比耗时点会在对象的实例化上。 2.2.1 源码 这里我们再对照下LinkedList尾插的源码，如下； voidlinkLast(Ee){finalNode<E>l=last;finalNode<E>newNode=newNode<>(l,e,null);last=newNode;if(l==null)first=newNode;elsel.next=newNode;size++;modCount++;} 与头插代码相比几乎没有什么区别，只是first换成last 耗时点只是在创建节点上， Node<E> 2.2.2 验证 「ArrayList、LinkeList，尾插源码验证」 @Testpublicvoidtest_ArrayList_addLast(){ArrayList<Integer>list=newArrayList<Integer>();longstartTime=System.currentTimeMillis();for(inti=0;i<10000000;i++){list.add(i);}System.out.println("耗时："+(System.currentTimeMillis()-startTime));}@Testpublicvoidtest_LinkedList_addLast(){LinkedList<Integer>list=newLinkedList<Integer>();longstartTime=System.currentTimeMillis();for(inti=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(位置、元素)方法插入：」 publicvoidadd(intindex,Eelement){checkPositionIndex(index);if(index==size)linkLast(element);elselinkBefore(element,node(index));} 「位置定位node(index)：」 Node<E>node(intindex){//assertisElementIndex(index);if(index<(size>>1)){Node<E>x=first;for(inti=0;i<index;i++)x=x.next;returnx;}else{Node<E>x=last;for(inti=size-1;i>index;i--)x=x.prev;returnx;}} size >> 1，这部分的代码判断元素位置在左半区间，还是右半区间，在进行循环查找。 「执行插入：」 voidlinkBefore(Ee,Node<E>succ){//assertsucc!=null;finalNode<E>pred=succ.prev;finalNode<E>newNode=newNode<>(pred,e,succ);succ.prev=newNode;if(pred==null)first=newNode;elsepred.next=newNode;size++;modCount++;} 找到指定位置插入的过程就比较简单了，与头插、尾插，相差不大。 整个过程可以看到，插入中比较耗时的点会在遍历寻找插入位置上。 2.3.2 验证 「ArrayList、LinkeList，中间插入源码验证」 @Testpublicvoidtest_ArrayList_addCenter(){ArrayList<Integer>list=newArrayList<Integer>();longstartTime=System.currentTimeMillis();for(inti=0;i<10000000;i++){list.add(list.size()>>1,i);}System.out.println("耗时："+(System.currentTimeMillis()-startTime));}@Testpublicvoidtest_LinkedList_addCenter(){LinkedList<Integer>list=newLinkedList<Integer>();longstartTime=System.currentTimeMillis();for(inti=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删除 「源码：」 @Testpublicvoidtest_remove(){LinkedList<String>list=newLinkedList<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");」 publicbooleanremove(Objecto){if(o==null){for(Node<E>x=first;x!=null;x=x.next){if(x.item==null){unlink(x);returntrue;}}}else{for(Node<E>x=first;x!=null;x=x.next){if(o.equals(x.item)){unlink(x);returntrue;}}}returnfalse;} 这一部分是元素定位，和 unlink(x)解链。循环查找对应的元素，这部分没有什么难点。 「unlink(x)解链」 Eunlink(Node<E>x){//assertx!=null;finalEelement=x.item;finalNode<E>next=x.next;finalNode<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++;returnelement;} 这部分源码主要有以下几个知识点； 获取待删除节点的信息；元素item、元素下一个节点next、元素上一个节点prev。 如果上个节点为空则把待删除元素的下一个节点赋值给首节点，否则把待删除节点的下一个节点，赋值给待删除节点的上一个节点的子节点。 同样待删除节点的下一个节点next，也执行2步骤同样操作。 最后是把删除节点设置为null，并扣减size和modeCount数量。 4. 遍历 接下来说下遍历，ArrayList与LinkedList的遍历都是通用的，基本包括5种方式。 这里我们先初始化出待遍历的集合1千万数据； intxx=0;@Beforepublicvoidinit(){for(inti=0;i<10000000;i++){list.add(i);}} 4.1 普通for循环 @Testpublicvoidtest_LinkedList_for0(){longstartTime=System.currentTimeMillis();for(inti=0;i<list.size();i++){xx+=list.get(i);}System.out.println("耗时："+(System.currentTimeMillis()-startTime));} 4.2 增强for循环 @Testpublicvoidtest_LinkedList_for1(){longstartTime=System.currentTimeMillis();for(Integeritr:list){xx+=itr;}System.out.println("耗时："+(System.currentTimeMillis()-startTime));} 4.3 Iterator遍历 @Testpublicvoidtest_LinkedList_Iterator(){longstartTime=System.currentTimeMillis();Iterator<Integer>iterator=list.iterator();while(iterator.hasNext()){Integernext=iterator.next();xx+=next;}System.out.println("耗时："+(System.currentTimeMillis()-startTime))} 4.4 forEach循环 @Testpublicvoidtest_LinkedList_forEach(){longstartTime=System.currentTimeMillis();list.forEach(integer->{xx+=integer;});System.out.println("耗时："+(System.currentTimeMillis()-startTime));} 4.5 stream(流) @Testpublicvoidtest_LinkedList_stream(){longstartTime=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节省空间，首先它所占用的内存不是连续的，其次他还需要大量的实例化对象创造节点。虽然不一定节省空间，但链表结构也是非常优秀的数据结构，它能在你的程序设计中起着非常优秀的作用，例如可视化的链路追踪图，就是需要链表结构，并需要每个节点自旋一次，用于串联业务。 程序的精髓往往就是数据结构的设计，这能为你的程序开发提供出非常高的效率改变。可能目前你还不能用到，但万一有一天你需要去造🚀火箭了呢？ bugstack虫洞栈 沉淀、分享、成长，让自己和他人都能有所收获！ 作者小傅哥多年从事一线互联网Java开发，从19年开始编写工作和学习历程的技术汇总，旨在为大家提供一个较清晰详细的核心技能学习文档。如果本文能为您提供帮助，请给予支持(关注、点赞、分享)！ 感谢支持小傅哥原创，欢迎点击在看和转发 本文分享自微信公众号 - bugstack虫洞栈（bugstack）。如有侵权，请联系 support@oschina.cn 删除。本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
