java中LinkedList使用迭代器优化移除批量元素原理分析

魁首哥

作者

java中LinkedList使用迭代器优化移除批量元素原理分析

小编给大家分享一下java中LinkedList使用迭代器优化移除批量元素原理分析，相信大部分人都还不怎么了解，因此分享这篇文章给大家参考一下，希望大家阅读完这篇文章后大有收获，下面让我们一起去了解一下吧！

具体如下：

publicinterfaceIterator<E>{/***是否还有下一个元素*/booleanhasNext();/***下一个元素*/Enext();/***从集合中删除最后一个返回的元素*/defaultvoidremove(){thrownewUnsupportedOperationException("remove");}/***传入一个Consumer对剩余的每个元素执行指定的操作，直到所有元素已处理或操作引发异常*/defaultvoidforEachRemaining(Consumer<?superE>action){//requireNonNull静态方法将会在参数为null时主动抛出NullPointerException异常。Objects.requireNonNull(action);while(hasNext())action.accept(next());}}

publicinterfaceListIterator<E>extendsIterator<E>{/***是否有后继*/booleanhasNext();/***后继节点*/Enext();/***是否有前驱*/booleanhasPrevious();/***前驱节点*/Eprevious();/***下一个节点的下标*/intnextIndex();/***前驱节点的下标*/intpreviousIndex();/***移除元素*/voidremove();/***替换最后返回的元素*/voidset(Ee);/***插入一个结点到最后返回的元素之后*/voidadd(Ee);}

普通版 ArrayListdie迭代器

调用方法：list.iterator();

publicIterator<E>iterator(){returnnewItr();}

privateclassItrimplementsIterator<E>{intcursor;//当前下标intlastRet=-1;//最后一个元素的索引，没有返回1intexpectedModCount=modCount;//创建迭代器时列表被修改的次数，防止多线程操作。快速失败/***先检查一下是否列表已经被修改过*做一些简单的越界检查*返回元素，并且记录下返回元素的下标给lastRet，当前下标+1，*/publicEnext(){checkForComodification();inti=cursor;if(i>=size)thrownewNoSuchElementException();Object[]elementData=ArrayList.this.elementData;if(i>=elementData.length)thrownewConcurrentModificationException();cursor=i+1;return(E)elementData[lastRet=i];}/***调用ArrayListdie自身的remove方法移除元素*ArrayListdie自身的remove会修改modCount的值所以需要更新迭代器的expectedModCount*expectedModCount=modCount;*/publicvoidremove(){if(lastRet<0)thrownewIllegalStateException();checkForComodification();try{ArrayList.this.remove(lastRet);cursor=lastRet;lastRet=-1;expectedModCount=modCount;}catch(IndexOutOfBoundsExceptionex){thrownewConcurrentModificationException();}}//把剩下为next遍历的所有元素做一个遍历消费@Override@SuppressWarnings("unchecked")publicvoidforEachRemaining(Consumer<?superE>consumer){Objects.requireNonNull(consumer);finalintsize=ArrayList.this.size;inti=cursor;if(i>=size){return;}finalObject[]elementData=ArrayList.this.elementData;if(i>=elementData.length){thrownewConcurrentModificationException();}while(i!=size&&modCount==expectedModCount){consumer.accept((E)elementData[i++]);}//updateonceatendofiterationtoreduceheapwritetrafficcursor=i;lastRet=i-1;checkForComodification();}//检查是否列表已经被修改了finalvoidcheckForComodification(){if(modCount!=expectedModCount)thrownewConcurrentModificationException();}}

增强版本 ArrayListdie迭代器

实现了ListIterator接口，ListIterator接口继承Iterator接口。并且ListItr extends Itr。Itr有的方法其都有。并且增加了

hasPrevious 是否有前驱
nextIndex 下一个索引位置
previousIndex 前驱的索引位置
previous 前驱元素
set 替换最后返回的元素
add 插入一个结点到最后返回的元素之后

privateclassListItrextendsItrimplementsListIterator<E>{ListItr(intindex){super();cursor=index;}publicbooleanhasPrevious(){returncursor!=0;}publicintnextIndex(){returncursor;}publicintpreviousIndex(){returncursor-1;}publicEprevious(){checkForComodification();inti=cursor-1;if(i<0)thrownewNoSuchElementException();Object[]elementData=ArrayList.this.elementData;if(i>=elementData.length)thrownewConcurrentModificationException();cursor=i;return(E)elementData[lastRet=i];}//根据lastRet设置元素publicvoidset(Ee){if(lastRet<0)thrownewIllegalStateException();checkForComodification();try{ArrayList.this.set(lastRet,e);expectedModCount=modCount;}catch(IndexOutOfBoundsExceptionex){thrownewConcurrentModificationException();}}publicvoidadd(Ee){checkForComodification();try{inti=cursor;ArrayList.this.add(i,e);cursor=i+1;lastRet=-1;expectedModCount=modCount;}catch(IndexOutOfBoundsExceptionex){thrownewConcurrentModificationException();}}}

重点看一下LinkedList的迭代器

调用方法：list.iterator();

重点看下remove方法

privateclassListItrimplementsListIterator<E>{//返回的节点privateNode<E>lastReturned;//下一个节点privateNode<E>next;//下一个节点索引privateintnextIndex;//修改次数privateintexpectedModCount=modCount;ListItr(intindex){//根据传进来的数字设置next等属性，默认传0next=(index==size)?null:node(index);nextIndex=index;}//直接调用节点的后继指针publicEnext(){checkForComodification();if(!hasNext())thrownewNoSuchElementException();lastReturned=next;next=next.next;nextIndex++;returnlastReturned.item;}//返回节点的前驱publicEprevious(){checkForComodification();if(!hasPrevious())thrownewNoSuchElementException();lastReturned=next=(next==null)?last:next.prev;nextIndex--;returnlastReturned.item;}/***最重要的方法，在LinkedList中按一定规则移除大量元素时用这个方法*为什么会比list.remove效率高呢;*/publicvoidremove(){checkForComodification();if(lastReturned==null)thrownewIllegalStateException();Node<E>lastNext=lastReturned.next;unlink(lastReturned);if(next==lastReturned)next=lastNext;elsenextIndex--;lastReturned=null;expectedModCount++;}publicvoidset(Ee){if(lastReturned==null)thrownewIllegalStateException();checkForComodification();lastReturned.item=e;}publicvoidadd(Ee){checkForComodification();lastReturned=null;if(next==null)linkLast(e);elselinkBefore(e,next);nextIndex++;expectedModCount++;}}

LinkedList 源码的remove(int index)的过程是
先逐一移动指针，再找到要移除的Node，最后再修改这个Node前驱后继等移除Node。如果有批量元素要按规则移除的话这么做时间复杂度O（n²）。但是使用迭代器是O（n）。

先看看list.remove（idnex）是怎么处理的

LinkedList是双向链表，这里示意图简单画个单链表
比如要移除链表中偶数元素，先循环调用get方法，指针逐渐后移获得元素，比如获得index = 1；指针后移两次才能获得元素。
当发现元素值为偶数是。使用idnex移除元素，如list.remove(1)；链表先Node node(int index)返回该index下的元素，与get方法一样。然后再做前驱后继的修改。所以在remove之前相当于做了两次get请求。导致时间复杂度是O（n）。