Java List的remove()方法陷阱以及性能优化

Java List的remove()方法陷阱以及性能优化

java List在进行remove（）方法是通常容易踩坑，主要有一下几点

循环时：问题在于，删除某个元素后，因为删除元素后，后面的元素都往前移动了一位，而你的索引+1，所以实际访问的元素相对于删除的元素中间间隔了一位。

几种常见方法

1.使用for循环不进行额外处理时（错误）

//错误的方法

for(int i=0;i

if(list.get(i)%2==0) {

list.remove(i);

}

}

2.使用foreach循环（错误）

for(Integer i:list) {

if(i%2==0) {

list.remove(i);

}

}

抛出异常：java.util.ConcurrentModificationException；

foreach的本质是使用迭代器实现，每次进入for (Integer i:list) 时，会调用ListItr.next()方法；

继而调用checkForComodification()方法， checkForComodification()方法对操作集合的次数进行了判断，如果当前对集合的操作次数与生成迭代器时不同，抛出异常

public E next() {

checkForComodification();

if (!hasNext()) {

throw new NoSuchElementException();

}

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.item;

}

// checkForComodification()方法对集合遍历前被修改的次数与现在被修改的次数做出对比

final void checkForComodification() {

if (modCount != expectedModCount) {

throw new ConcurrentModificationException();

}

}

使用for循环，并且同时改变索引；（正确）

//正确

for(int i=0;i

if(list.get(i)%2==0) {

list.remove(i);

i--;//在元素被移除掉后，进行索引后移

}

}

使用for循环，倒序进行；（正确）

//正确

for(int i=list.size()-1;i>=0;i--) {

if(list.get(i)%2==0) {

list.remove(i);

}

}

使用while循环，删除了元素，索引便不+1，在没删除元素时索引+1（正确）

//正确

int i=0;

while(i

if(list.get(i)%2==0) {

list.remove(i);

}else {

i++;

}

}

4.使用迭代器方法（正确,推荐）

只能使用迭代器的remove()方法，使用列表的remove()方法是错误的

//正确，并且推荐的方法

Iterator itr = list.iterator();

while(itr.hasNext()) {

if(itr.next()%2 ==0)

itr.remove();

}

性能分析

下面来谈谈当数据量过大时候，需要删除的元素较多时，如何用迭代器进行性能的优化，对于ArrayList这几乎是致命的，从一个ArrayList中删除批量元素都是昂贵的时间复杂度为O（n²），那么接下来看看LinkeedList是否可行。LinkedList暴露了两个问题，一个：是每次的Get请求效率不高，而且，对于remove的调用同样低效，因为达到位置I的代价是昂贵的。

是每次的Get请求效率不高

需要先get元素，然后过滤元素。比较元素是否满足删除条件。

remove的调用同样低效

LinkedList的remove（index），方法是需要先遍历链表，先找到该index下的节点，再处理节点的前驱后继。

以上两个问题当遇到批量级别需要处理时时间复杂度直接上升到O（n²）

使用迭代器的方法删除元素

对于LinkedList，对该迭代器的remove（）方法的调用只花费常数时间，因为在循环时该迭代器位于需要被删除的节点，因此是常数操作。对于一个ArrayList，即使该迭代器位于需要被删除的节点，其remove（）方法依然是昂贵的，因为数组项必须移动。下面贴出示例代码以及运行结果

public class RemoveByIterator {

public static void main(String[] args) {

List arrList1 = new ArrayList<>();

for(int i=0;i<100000;i++) {

arrList1.add(i);

}

List linList1 = new LinkedList<>();

for(int i=0;i<100000;i++) {

linList1.add(i);

}

List arrList2 = new ArrayList<>();

for(int i=0;i<100000;i++) {

arrList2.add(i);

}

List linList2 = new LinkedList<>();

for(int i=0;i<100000;i++) {

linList2.add(i);

}

removeEvens(arrList1,"ArrayList");

removeEvens(linList1,"LinkedList");

removeEvensByIterator(arrList2,"ArrayList");

removeEvensByIterator(linList2,"LinkedList");

}

public static void removeEvensByIterator(List lst ,String name) {//利用迭代器remove偶数

long sTime = new Date().getTime();

Iterator itr = lst.iterator();

while(itr.hasNext()) {

if(itr.next()%2 ==0)

itr.remove();

}

System.out.println(name+"使用迭代器时间:"+(new Date().getTime()-sTime)+"毫秒");

}

public static void removeEvens(List list , String name) {//不使用迭代器remove偶数

long sTime = new Date().getTime();

int i=0;

while(i

if(list.get(i)%2==0) {

list.remove(i);

}else {

i++;

}

}

System.out.println(name+"不使用迭代器的时间"+(new Date().getTime()-sTime)+"毫秒");

}

}

原理 重点看一下LinkedList的迭代器

另一篇博客 Iterator简介 LinkedList使用迭代器优化移除批量元素原理

调用方法：list.iterator();

重点看下remove方法

private class ListItr implements ListIterator {

//返回的节点

private Node lastReturned;

//下一个节点

privatehttp:// Node next;

//下一个节点索引

private int nextIndex;

//修改次数

private int expectedModCount = modCount;

ListItr(int index) {

//根据传进来的数字设置next等属性，默认传0

next = (index == size) ? null : node(index);

nextIndex = index;

}

//直接调用节点的后继指针

public E next() {

checkForComodification();

if (!hasNext())

throw new NoSuchElementException();

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.item;

}

//返回节点的前驱

public E previous() {

checkForComodification();

if (!hasPrevious())

throw new NoSuchElementException();

lastReturned = next = (next == null) ? last : next.prev;

nextIndex--;

return lastReturned.item;

}

/**

* 最重要的方法，在LinkedList中按一定规则移除大量元素时用这个方法

* 为什么会比list.remove效率高呢;

*/

public void remove() {

checkForComodification();

if (lastReturned == null)

throw new IllegalStateException();

Node lastNext = lastReturned.next;

unlink(lastReturned);

if (next == lastReturned)

next = lastNext;

else

nextIndex--;

lastReturnhttp://ed = null;

expectedModCount++;

}

public void set(E e) {

if (lastReturned == null)

throw new IllegalStateException();

checkForComodification();

lastReturned.item = e;

}

public void add(E e) {

checkForComodification();

lastReturned = null;

if (next == null)

linkLast(e);

else

linkBefore(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）。

继续移除下一个元素需要重新再走一遍链表（步骤忽略当index大于半数，链表倒序查找）

以上如果移除偶数指针做了6次移动。

删除2节点

get请求移动1次，remove（1）移动1次。

删除4节点

get请求移动2次，remove（2）移动2次。

迭代器的处理

迭代器的next指针执行一次一直向后移动的操作。一共只需要移动4次。当元素越多时这个差距会越明显。整体上移除批量元素是O（n），而使用list.remove(index)移除批量元素是O（n²）

if(list.get(i)%2==0) {

list.remove(i);

}

}

2.使用foreach循环（错误）

for(Integer i:list) {

if(i%2==0) {

list.remove(i);

}

}

抛出异常：java.util.ConcurrentModificationException；

foreach的本质是使用迭代器实现，每次进入for (Integer i:list) 时，会调用ListItr.next()方法；

继而调用checkForComodification()方法， checkForComodification()方法对操作集合的次数进行了判断，如果当前对集合的操作次数与生成迭代器时不同，抛出异常

public E next() {

checkForComodification();

if (!hasNext()) {

throw new NoSuchElementException();

}

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.item;

}

// checkForComodification()方法对集合遍历前被修改的次数与现在被修改的次数做出对比

final void checkForComodification() {

if (modCount != expectedModCount) {

throw new ConcurrentModificationException();

}

}

使用for循环，并且同时改变索引；（正确）

//正确

for(int i=0;i

if(list.get(i)%2==0) {

list.remove(i);

i--;//在元素被移除掉后，进行索引后移

}

}

使用for循环，倒序进行；（正确）

//正确

for(int i=list.size()-1;i>=0;i--) {

if(list.get(i)%2==0) {

list.remove(i);

}

}

使用while循环，删除了元素，索引便不+1，在没删除元素时索引+1（正确）

//正确

int i=0;

while(i

if(list.get(i)%2==0) {

list.remove(i);

}else {

i++;

}

}

4.使用迭代器方法（正确,推荐）

只能使用迭代器的remove()方法，使用列表的remove()方法是错误的

//正确，并且推荐的方法

Iterator itr = list.iterator();

while(itr.hasNext()) {

if(itr.next()%2 ==0)

itr.remove();

}

性能分析

下面来谈谈当数据量过大时候，需要删除的元素较多时，如何用迭代器进行性能的优化，对于ArrayList这几乎是致命的，从一个ArrayList中删除批量元素都是昂贵的时间复杂度为O（n²），那么接下来看看LinkeedList是否可行。LinkedList暴露了两个问题，一个：是每次的Get请求效率不高，而且，对于remove的调用同样低效，因为达到位置I的代价是昂贵的。

是每次的Get请求效率不高

需要先get元素，然后过滤元素。比较元素是否满足删除条件。

remove的调用同样低效

LinkedList的remove（index），方法是需要先遍历链表，先找到该index下的节点，再处理节点的前驱后继。

以上两个问题当遇到批量级别需要处理时时间复杂度直接上升到O（n²）

使用迭代器的方法删除元素

对于LinkedList，对该迭代器的remove（）方法的调用只花费常数时间，因为在循环时该迭代器位于需要被删除的节点，因此是常数操作。对于一个ArrayList，即使该迭代器位于需要被删除的节点，其remove（）方法依然是昂贵的，因为数组项必须移动。下面贴出示例代码以及运行结果

public class RemoveByIterator {

public static void main(String[] args) {

List arrList1 = new ArrayList<>();

for(int i=0;i<100000;i++) {

arrList1.add(i);

}

List linList1 = new LinkedList<>();

for(int i=0;i<100000;i++) {

linList1.add(i);

}

List arrList2 = new ArrayList<>();

for(int i=0;i<100000;i++) {

arrList2.add(i);

}

List linList2 = new LinkedList<>();

for(int i=0;i<100000;i++) {

linList2.add(i);

}

removeEvens(arrList1,"ArrayList");

removeEvens(linList1,"LinkedList");

removeEvensByIterator(arrList2,"ArrayList");

removeEvensByIterator(linList2,"LinkedList");

}

public static void removeEvensByIterator(List lst ,String name) {//利用迭代器remove偶数

long sTime = new Date().getTime();

Iterator itr = lst.iterator();

while(itr.hasNext()) {

if(itr.next()%2 ==0)

itr.remove();

}

System.out.println(name+"使用迭代器时间:"+(new Date().getTime()-sTime)+"毫秒");

}

public static void removeEvens(List list , String name) {//不使用迭代器remove偶数

long sTime = new Date().getTime();

int i=0;

while(i

if(list.get(i)%2==0) {

list.remove(i);

}else {

i++;

}

}

System.out.println(name+"不使用迭代器的时间"+(new Date().getTime()-sTime)+"毫秒");

}

}

原理 重点看一下LinkedList的迭代器

另一篇博客 Iterator简介 LinkedList使用迭代器优化移除批量元素原理

调用方法：list.iterator();

重点看下remove方法

private class ListItr implements ListIterator {

//返回的节点

private Node lastReturned;

//下一个节点

privatehttp:// Node next;

//下一个节点索引

private int nextIndex;

//修改次数

private int expectedModCount = modCount;

ListItr(int index) {

//根据传进来的数字设置next等属性，默认传0

next = (index == size) ? null : node(index);

nextIndex = index;

}

//直接调用节点的后继指针

public E next() {

checkForComodification();

if (!hasNext())

throw new NoSuchElementException();

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.item;

}

//返回节点的前驱

public E previous() {

checkForComodification();

if (!hasPrevious())

throw new NoSuchElementException();

lastReturned = next = (next == null) ? last : next.prev;

nextIndex--;

return lastReturned.item;

}

/**

* 最重要的方法，在LinkedList中按一定规则移除大量元素时用这个方法

* 为什么会比list.remove效率高呢;

*/

public void remove() {

checkForComodification();

if (lastReturned == null)

throw new IllegalStateException();

Node lastNext = lastReturned.next;

unlink(lastReturned);

if (next == lastReturned)

next = lastNext;

else

nextIndex--;

lastReturnhttp://ed = null;

expectedModCount++;

}

public void set(E e) {

if (lastReturned == null)

throw new IllegalStateException();

checkForComodification();

lastReturned.item = e;

}

public void add(E e) {

checkForComodification();

lastReturned = null;

if (next == null)

linkLast(e);

else

linkBefore(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）。

继续移除下一个元素需要重新再走一遍链表（步骤忽略当index大于半数，链表倒序查找）

以上如果移除偶数指针做了6次移动。

删除2节点

get请求移动1次，remove（1）移动1次。

删除4节点

get请求移动2次，remove（2）移动2次。

迭代器的处理

迭代器的next指针执行一次一直向后移动的操作。一共只需要移动4次。当元素越多时这个差距会越明显。整体上移除批量元素是O（n），而使用list.remove(index)移除批量元素是O（n²）

if(list.get(i)%2==0) {

list.remove(i);

i--;//在元素被移除掉后，进行索引后移

}

}

使用for循环，倒序进行；（正确）

//正确

for(int i=list.size()-1;i>=0;i--) {

if(list.get(i)%2==0) {

list.remove(i);

}

}

使用while循环，删除了元素，索引便不+1，在没删除元素时索引+1（正确）

//正确

int i=0;

while(i

if(list.get(i)%2==0) {

list.remove(i);

}else {

i++;

}

}

4.使用迭代器方法（正确,推荐）

只能使用迭代器的remove()方法，使用列表的remove()方法是错误的

//正确，并且推荐的方法

Iterator itr = list.iterator();

while(itr.hasNext()) {

if(itr.next()%2 ==0)

itr.remove();

}

性能分析

下面来谈谈当数据量过大时候，需要删除的元素较多时，如何用迭代器进行性能的优化，对于ArrayList这几乎是致命的，从一个ArrayList中删除批量元素都是昂贵的时间复杂度为O（n²），那么接下来看看LinkeedList是否可行。LinkedList暴露了两个问题，一个：是每次的Get请求效率不高，而且，对于remove的调用同样低效，因为达到位置I的代价是昂贵的。

是每次的Get请求效率不高

需要先get元素，然后过滤元素。比较元素是否满足删除条件。

remove的调用同样低效

LinkedList的remove（index），方法是需要先遍历链表，先找到该index下的节点，再处理节点的前驱后继。

以上两个问题当遇到批量级别需要处理时时间复杂度直接上升到O（n²）

使用迭代器的方法删除元素

对于LinkedList，对该迭代器的remove（）方法的调用只花费常数时间，因为在循环时该迭代器位于需要被删除的节点，因此是常数操作。对于一个ArrayList，即使该迭代器位于需要被删除的节点，其remove（）方法依然是昂贵的，因为数组项必须移动。下面贴出示例代码以及运行结果

public class RemoveByIterator {

public static void main(String[] args) {

List arrList1 = new ArrayList<>();

for(int i=0;i<100000;i++) {

arrList1.add(i);

}

List linList1 = new LinkedList<>();

for(int i=0;i<100000;i++) {

linList1.add(i);

}

List arrList2 = new ArrayList<>();

for(int i=0;i<100000;i++) {

arrList2.add(i);

}

List linList2 = new LinkedList<>();

for(int i=0;i<100000;i++) {

linList2.add(i);

}

removeEvens(arrList1,"ArrayList");

removeEvens(linList1,"LinkedList");

removeEvensByIterator(arrList2,"ArrayList");

removeEvensByIterator(linList2,"LinkedList");

}

public static void removeEvensByIterator(List lst ,String name) {//利用迭代器remove偶数

long sTime = new Date().getTime();

Iterator itr = lst.iterator();

while(itr.hasNext()) {

if(itr.next()%2 ==0)

itr.remove();

}

System.out.println(name+"使用迭代器时间:"+(new Date().getTime()-sTime)+"毫秒");

}

public static void removeEvens(List list , String name) {//不使用迭代器remove偶数

long sTime = new Date().getTime();

int i=0;

while(i

if(list.get(i)%2==0) {

list.remove(i);

}else {

i++;

}

}

System.out.println(name+"不使用迭代器的时间"+(new Date().getTime()-sTime)+"毫秒");

}

}

原理 重点看一下LinkedList的迭代器

另一篇博客 Iterator简介 LinkedList使用迭代器优化移除批量元素原理

调用方法：list.iterator();

重点看下remove方法

private class ListItr implements ListIterator {

//返回的节点

private Node lastReturned;

//下一个节点

privatehttp:// Node next;

//下一个节点索引

private int nextIndex;

//修改次数

private int expectedModCount = modCount;

ListItr(int index) {

//根据传进来的数字设置next等属性，默认传0

next = (index == size) ? null : node(index);

nextIndex = index;

}

//直接调用节点的后继指针

public E next() {

checkForComodification();

if (!hasNext())

throw new NoSuchElementException();

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.item;

}

//返回节点的前驱

public E previous() {

checkForComodification();

if (!hasPrevious())

throw new NoSuchElementException();

lastReturned = next = (next == null) ? last : next.prev;

nextIndex--;

return lastReturned.item;

}

/**

* 最重要的方法，在LinkedList中按一定规则移除大量元素时用这个方法

* 为什么会比list.remove效率高呢;

*/

public void remove() {

checkForComodification();

if (lastReturned == null)

throw new IllegalStateException();

Node lastNext = lastReturned.next;

unlink(lastReturned);

if (next == lastReturned)

next = lastNext;

else

nextIndex--;

lastReturnhttp://ed = null;

expectedModCount++;

}

public void set(E e) {

if (lastReturned == null)

throw new IllegalStateException();

checkForComodification();

lastReturned.item = e;

}

public void add(E e) {

checkForComodification();

lastReturned = null;

if (next == null)

linkLast(e);

else

linkBefore(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）。

继续移除下一个元素需要重新再走一遍链表（步骤忽略当index大于半数，链表倒序查找）

以上如果移除偶数指针做了6次移动。

删除2节点

get请求移动1次，remove（1）移动1次。

删除4节点

get请求移动2次，remove（2）移动2次。

迭代器的处理

迭代器的next指针执行一次一直向后移动的操作。一共只需要移动4次。当元素越多时这个差距会越明显。整体上移除批量元素是O（n），而使用list.remove(index)移除批量元素是O（n²）

if(list.get(i)%2==0) {

list.remove(i);

}else {

i++;

}

}

4.使用迭代器方法（正确,推荐）

只能使用迭代器的remove()方法，使用列表的remove()方法是错误的

//正确，并且推荐的方法

Iterator itr = list.iterator();

while(itr.hasNext()) {

if(itr.next()%2 ==0)

itr.remove();

}

性能分析

下面来谈谈当数据量过大时候，需要删除的元素较多时，如何用迭代器进行性能的优化，对于ArrayList这几乎是致命的，从一个ArrayList中删除批量元素都是昂贵的时间复杂度为O（n²），那么接下来看看LinkeedList是否可行。LinkedList暴露了两个问题，一个：是每次的Get请求效率不高，而且，对于remove的调用同样低效，因为达到位置I的代价是昂贵的。

是每次的Get请求效率不高

需要先get元素，然后过滤元素。比较元素是否满足删除条件。

remove的调用同样低效

LinkedList的remove（index），方法是需要先遍历链表，先找到该index下的节点，再处理节点的前驱后继。

以上两个问题当遇到批量级别需要处理时时间复杂度直接上升到O（n²）

使用迭代器的方法删除元素

对于LinkedList，对该迭代器的remove（）方法的调用只花费常数时间，因为在循环时该迭代器位于需要被删除的节点，因此是常数操作。对于一个ArrayList，即使该迭代器位于需要被删除的节点，其remove（）方法依然是昂贵的，因为数组项必须移动。下面贴出示例代码以及运行结果

public class RemoveByIterator {

public static void main(String[] args) {

List arrList1 = new ArrayList<>();

for(int i=0;i<100000;i++) {

arrList1.add(i);

}

List linList1 = new LinkedList<>();

for(int i=0;i<100000;i++) {

linList1.add(i);

}

List arrList2 = new ArrayList<>();

for(int i=0;i<100000;i++) {

arrList2.add(i);

}

List linList2 = new LinkedList<>();

for(int i=0;i<100000;i++) {

linList2.add(i);

}

removeEvens(arrList1,"ArrayList");

removeEvens(linList1,"LinkedList");

removeEvensByIterator(arrList2,"ArrayList");

removeEvensByIterator(linList2,"LinkedList");

}

public static void removeEvensByIterator(List lst ,String name) {//利用迭代器remove偶数

long sTime = new Date().getTime();

Iterator itr = lst.iterator();

while(itr.hasNext()) {

if(itr.next()%2 ==0)

itr.remove();

}

System.out.println(name+"使用迭代器时间:"+(new Date().getTime()-sTime)+"毫秒");

}

public static void removeEvens(List list , String name) {//不使用迭代器remove偶数

long sTime = new Date().getTime();

int i=0;

while(i

if(list.get(i)%2==0) {

list.remove(i);

}else {

i++;

}

}

System.out.println(name+"不使用迭代器的时间"+(new Date().getTime()-sTime)+"毫秒");

}

}

原理 重点看一下LinkedList的迭代器

另一篇博客 Iterator简介 LinkedList使用迭代器优化移除批量元素原理

调用方法：list.iterator();

重点看下remove方法

private class ListItr implements ListIterator {

//返回的节点

private Node lastReturned;

//下一个节点

privatehttp:// Node next;

//下一个节点索引

private int nextIndex;

//修改次数

private int expectedModCount = modCount;

ListItr(int index) {

//根据传进来的数字设置next等属性，默认传0

next = (index == size) ? null : node(index);

nextIndex = index;

}

//直接调用节点的后继指针

public E next() {

checkForComodification();

if (!hasNext())

throw new NoSuchElementException();

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.item;

}

//返回节点的前驱

public E previous() {

checkForComodification();

if (!hasPrevious())

throw new NoSuchElementException();

lastReturned = next = (next == null) ? last : next.prev;

nextIndex--;

return lastReturned.item;

}

/**

* 最重要的方法，在LinkedList中按一定规则移除大量元素时用这个方法

* 为什么会比list.remove效率高呢;

*/

public void remove() {

checkForComodification();

if (lastReturned == null)

throw new IllegalStateException();

Node lastNext = lastReturned.next;

unlink(lastReturned);

if (next == lastReturned)

next = lastNext;

else

nextIndex--;

lastReturnhttp://ed = null;

expectedModCount++;

}

public void set(E e) {

if (lastReturned == null)

throw new IllegalStateException();

checkForComodification();

lastReturned.item = e;

}

public void add(E e) {

checkForComodification();

lastReturned = null;

if (next == null)

linkLast(e);

else

linkBefore(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）。

继续移除下一个元素需要重新再走一遍链表（步骤忽略当index大于半数，链表倒序查找）

以上如果移除偶数指针做了6次移动。

删除2节点

get请求移动1次，remove（1）移动1次。

删除4节点

get请求移动2次，remove（2）移动2次。

迭代器的处理

迭代器的next指针执行一次一直向后移动的操作。一共只需要移动4次。当元素越多时这个差距会越明显。整体上移除批量元素是O（n），而使用list.remove(index)移除批量元素是O（n²）

if(list.get(i)%2==0) {

list.remove(i);

}else {

i++;

}

}

System.out.println(name+"不使用迭代器的时间"+(new Date().getTime()-sTime)+"毫秒");

}

}

原理 重点看一下LinkedList的迭代器

另一篇博客 Iterator简介 LinkedList使用迭代器优化移除批量元素原理

调用方法：list.iterator();

重点看下remove方法

private class ListItr implements ListIterator {

//返回的节点

private Node lastReturned;

//下一个节点

privatehttp:// Node next;

//下一个节点索引

private int nextIndex;

//修改次数

private int expectedModCount = modCount;

ListItr(int index) {

//根据传进来的数字设置next等属性，默认传0

next = (index == size) ? null : node(index);

nextIndex = index;

}

//直接调用节点的后继指针

public E next() {

checkForComodification();

if (!hasNext())

throw new NoSuchElementException();

lastReturned = next;

next = next.next;

nextIndex++;

return lastReturned.item;

}

//返回节点的前驱

public E previous() {

checkForComodification();

if (!hasPrevious())

throw new NoSuchElementException();

lastReturned = next = (next == null) ? last : next.prev;

nextIndex--;

return lastReturned.item;

}

/**

* 最重要的方法，在LinkedList中按一定规则移除大量元素时用这个方法

* 为什么会比list.remove效率高呢;

*/

public void remove() {

checkForComodification();

if (lastReturned == null)

throw new IllegalStateException();

Node lastNext = lastReturned.next;

unlink(lastReturned);

if (next == lastReturned)

next = lastNext;

else

nextIndex--;

lastReturnhttp://ed = null;

expectedModCount++;

}

public void set(E e) {

if (lastReturned == null)

throw new IllegalStateException();

checkForComodification();

lastReturned.item = e;

}

public void add(E e) {

checkForComodification();

lastReturned = null;

if (next == null)

linkLast(e);

else

linkBefore(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）。

继续移除下一个元素需要重新再走一遍链表（步骤忽略当index大于半数，链表倒序查找）

以上如果移除偶数指针做了6次移动。

删除2节点

get请求移动1次，remove（1）移动1次。

删除4节点

get请求移动2次，remove（2）移动2次。

迭代器的处理

迭代器的next指针执行一次一直向后移动的操作。一共只需要移动4次。当元素越多时这个差距会越明显。整体上移除批量元素是O（n），而使用list.remove(index)移除批量元素是O（n²）

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。