ArrayList重拳出击，把LinkedList打翻慢，LinkedList底层是链表，查询慢。”、增删快”，你可以放过他！这是一个极度不负责任的总结，关键你会在很多地方看到这样的结论。害，我刚开始学Java的时候，也问过一个大佬，ArrayList和LinkedList有什么区别？“快点”给我。当时就觉得，老板真牛逼！后来研究了ArrayList和LinkedList的源码，发现确实前者是数组，后者是LinkedList，更加佩服老大了。！直到后来自己跑程序验证，才发现老大的结论太草率了！根本不是这样的！先普及一个概念-时间复杂度。在计算机科学中，算法的时间复杂度是定性描述该算法运行时间的函数。这是表示算法输入值的字符串长度的函数。时间复杂度通常用大O表示法表示，不包括该函数的低阶项和前导系数。使用这种方法时，时间复杂度可以说是渐近的，即考虑输入值的大小趋近于无穷大的情况。例如，如果算法对任何大小为n（必须大于）的输入最多花费运行时间，则其渐近时间复杂度为。增删改查，对应ArrayList和LinkedList，分别是add(Ee),remove(intindex),add(intindex,Eelement),get(intindex)，我一一分析一下你，和他们对应的时间复杂度，所以我理解ArrayList底层是数组，查询快，增删改慢；LinkedList底层是链表，查询慢，增删快。的时间复杂度为，因为是直接根据下标从底层数组中获取，与数组长度无关。publicEget(intindex){Objects.checkIndex(index,size);returnelementData(index);}这也是ArrayList最大的优势。2）add(Ee)方法默认会在数组末尾添加元素，但是需要考虑数组的扩容。如果不需要扩展，时间复杂度为。publicbooleanadd(Ee){modCount++;add(e,elementData,size);returntrue;}privatevoidadd(Ee,Object[]elementData,ints){if(s==elementData.length)elementData=grow();elementData[s]=e;size=s+1;}如果需要扩容，而且不是第一次（oldCapacity>0）扩容，内部执行的Arrays.copyOf()方法是耗时的关键，而原来array需要将元素复制到新的扩展数组中。privateObject[]grow(intminCapacity){intoldCapacity=elementData.length;if(oldCapacity>0||elementData!=DEFAULTCAPACITY_EMPTY_ELEMENTDATA){intnewCapacity=ArraysSupport.newLength(oldCapacity,minCapacity-oldCapacity,/*最小增长*/oldCapacity>>1/*preferredgrowth*/);returnelementData=Arrays.copyOf(elementData,newCapacity);}else{returnelementData=newObject[Math.max(DEFAULT_CAPACITY,minCapacity)];}}3)add(intindex,Eelement)方法将新元素插入到指定位置，考虑需要复制底层数组（根据前面的判断，如果扩容可能需要复制一次数组），按照最坏的打算（无论是否需要扩容或不是，必须执行System.arraycopy())，所以时间复杂度是。publicvoidadd(intindex,Eelement){rangeCheckForAdd(index);modCount++;finalints;Object[]elementData;if((s=size)==(elementData=this.elementData).length)elementData=grow();System.arraycopy(elementData,index,elementData,index+1,s-index);elementData[index]=element;size=s+1;}执行下面的代码，将silentbastard插入下标2的位置。ArrayListlist=newArrayList<>();list.add("沉默之王2");list.add("沉默之王3");list.add("沉默之王4");list.add("沉默之王五");list.add("沉默之王六");list.add("沉默之王七");list.add(2,"沉默之王八");System.arraycopy()执行完后，下载标记为2的元素就是silentquad，这个需要注意一下。也就是说，在数组中插入一个元素时，会依次复制插入位置之后的元素，所以下标2和下标3的元素为默王四。然后通过elementData[index]=element;将下标为2的元素赋值为沉默混蛋。然后执行size=s+1，数组长度变为7。4）remove(intindex)方法移除指定位置的元素Delete，考虑到需要复制底层数组，所以时间复杂度为。publicEremove(intindex){Objects.checkIndex(index,size);finalObject[]es=elementData;@SuppressWarnings("unchecked")EoldValue=(E)es[index];fastRemove(es,index);returnoldValue;}privatevoidfastRemove(Object[]es,inti){modCount++;finalintnewSize;if((newSize=size-1)>i)System.arraycopy(es,i+1,es,i,newSize-i);es[size=newSize]=null;}对于LinkedList：1）get(intindex)方法的时间复杂度为，因为它需要遍历整个链表。publicEget(intindex){checkElementIndex(index);returnnode(index).item;}LinkedList.Nodenode(intindex){//assertisElementIndex(index);if(index<(size>>1)){LinkedList.Nodex=first;for(inti=0;ix=last;for(inti=size-1;i>index;i--)x=x.prev;returnx;}}当下标小于链表长度的一半时，从前向后遍历；否则就是从后往前遍历，所以理论上来说，可以节省一半的时间。如果下标为0或list.size()-1，则时间复杂度为.在这种情况下，可以使用getFirst()和getLast()方法。publicEgetFirst(){finalLinkedList.Nodef=first;if(f==null)thrownewNoSuchElementException();returnf.item;}publicEgetLast(){finalLinkedList.Nodel=last;if(l==null)thrownewNoSuchElementException();returnl.item;}first和last直接存储在链表中，所以时间复杂度为。2)add(Ee)方法默认向链表尾部添加元素，所以时间复杂度为。publicbooleanadd(Ee){linkLast(e);returntrue;}voidlinkLast(Ee){finalLinkedList.Nodel=last;finalLinkedList.NodenewNode=newLinkedList.Node<>(l,e,null);last=newNode;if(l==null)first=newNode;elsel.next=newNode;size++;modCount++;}3)add(intindex,Eelement)方法在指定位置插入一个新元素，需要遍历先找到这个元素再插入，所以时间复杂度为。publicvoidadd(intindex,Eelement){checkPositionIndex(index);if(index==size)linkLast(element);elselinkBefore(element,node(index));}如果下标为0或者list.size()-1，时间复杂度为.在这种情况下，可以使用addFirst()和addLast()方法。publicvoidaddFirst(Ee){linkFirst(e);}privatevoidlinkFirst(Ee){finalLinkedList.Nodef=first;finalLinkedList.NodenewNode=newLinkedList.Node<>(null,e,f);first=newNode;if(f==null)last=newNode;elsef.prev=newNode;size++;modCount++;}linkLast()只需要最后更新。publicvoidaddLast(Ee){linkLast(e);}voidlinkLast(Ee){finalLinkedList.Nodel=last;finalLinkedList.NodenewNode=newLinkedList.Node<>(l,e,null);last=newNode;if(l==null)first=newNode;elsel.next=newNode;size++;modCount++;}应该是注意到有些文章说LinkedList插入元素的时间复杂度是近似的，其实是有问题的，因为add(intindex,Eelement)方法在插入元素的时候会调用node(index)去查找元素。这个方法之前已经确认过，时间复杂度为，即使后面调用linkBefore()方法插入也是如此。度是，整体时间复杂度还是。voidlinkBefore(Ee,LinkedList.Nodesucc){//assertsucc!=null;finalLinkedList.Nodepred=succ.prev;finalLinkedList.NodenewNode=newLinkedList.Node<>(pred,e,succ);succ.prev=newNode;if(pred==null)first=newNode;elsepred.next=newNode;size++;modCount++;}4)remove(intindex)方法删除指定位置的元素，考虑到考虑到需要调用node(index)方法来查找元素，所以时间复杂度为。publicEremove(intindex){checkElementIndex(index);returnunlink(node(index));}Eunlink(LinkedList.Nodex){//assertx!=null;finalEelement=x.item;finalLinkedList.Nodenext=x.next;finalLinkedList.Nodeprev=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;}通过时间复杂度的对比和源码分析，我相信你在选择的时候是有想法的吧？需要注意的是，如果列表非常大，ArrayList和LinkedList也有不同的内存使用情况。LinkedList的每个元素都有更多的开销，因为存储了前一个元素和下一个元素的地址。ArrayList没有这样的开销。毫无疑问，ArrayList在查询时比LinkedList更快；在插入和删除时，LinkedList并不比ArrayList快，因为它必须遍历列表。相反，ArrayList更加轻量，不需要在每个元素上维护上一个元素和下一个元素的地址。但是需要注意的是，如果ArrayList在增删改查时涉及到大量的数组副本，效率就另当别论了，因为这个过程是相当耗时的。对于初学者来说，一般不会涉及百万级的数据操作。如果你真的不知道用ArrayList还是LinkedList，想都不想就选ArrayList吧！按照下面的二维码进行操作。转载本文请联系沉默王二公众号。
