List的remove()方法陷阱+性能优化

>>强大,10k+点赞的 SpringBoot 后台管理系统竟然出了详细教程!

点击关注公众号,利用碎片时间学习

文章目录

  • 几种常见方法
  • 性能分析
  • 使用迭代器的方法删除元素
  • 原理 重点看一下LinkedList的迭代器
  • 先看看list.remove(idnex)是怎么处理的
  • 迭代器的处理

Java List在进行remove()方法是通常容易踩坑,主要有一下几点

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

几种常见方法

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

//错误的方法
for(int i=0;i<list.size();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();
   }
             
  }

3.使用for循环,并且同时改变索引;(正确)

//正确
for(int i=0;i<list.size();i++) {
 if(list.get(i)%2==0) {
  list.remove(i);
  i--;//在元素被移除掉后,进行索引后移
 }
}

4.使用for循环,倒序进行;(正确)

//正确
for(int i=list.size()-1;i>=0;i--) {
 if(list.get(i)%2==0) {
  list.remove(i);
 }
}

5.使用while循环,删除了元素,索引便不+1,在没删除元素时索引+1(正确)

//正确
int i=0;
while(i<list.size()) {
 if(list.get(i)%2==0) {
  list.remove(i);
 }else {
  i++;
 }
}

6.使用迭代器方法(正确,推荐)

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

//正确,并且推荐的方法
Iterator<Integer> 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()方法依然是昂贵的,因为数组项必须移动。下面贴出示例代码以及运行结果

List的remove()方法陷阱+性能优化
public class RemoveByIterator {

 public static void main(String[] args) {
  
  List<Integer> arrList1 = new ArrayList<>();
  for(int i=0;i<100000;i++) {
   arrList1.add(i);
  }
  
  List<Integer> linList1 = new LinkedList<>();
  for(int i=0;i<100000;i++) {
   linList1.add(i);
  }

  List<Integer> arrList2 = new ArrayList<>();
  for(int i=0;i<100000;i++) {
   arrList2.add(i);
  }
  
  List<Integer> 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<Integer> lst ,String name) {//利用迭代器remove偶数
  long sTime = new Date().getTime();
  Iterator<Integer> 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<Integer> list , String name) {//不使用迭代器remove偶数
  long sTime = new Date().getTime();
  int i=0;
  while(i<list.size()) {
   
   if(list.get(i)%2==0) {
    list.remove(i);
   }else {
    i++;
   }
  }
 
  System.out.println(name+"不使用迭代器的时间"+(new Date().getTime()-sTime)+"毫秒");
 }
}

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

引申阅读:https://blog.csdn.net/wsdfym/article/details/109633368

调用方法:list.iterator();

List的remove()方法陷阱+性能优化

重点看下remove方法

private class ListItr implements ListIterator<E{
        //返回的节点
        private Node<E> lastReturned;
        //下一个节点
        private Node<E> 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<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = 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)

List的remove()方法陷阱+性能优化
List的remove()方法陷阱+性能优化

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

List的remove()方法陷阱+性能优化

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

  • 删除2节点: get请求移动1次,remove(1)移动1次。
  • 删除4节点: get请求移动2次,remove(2)移动2次。

迭代器的处理

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

List的remove()方法陷阱+性能优化

来源:blog.csdn.net/wsdfym/article/details/90544839

推荐:

主流Java进阶技术(学习资料分享)

List的remove()方法陷阱+性能优化
PS:因为公众号平台更改了推送规则,如果不想错过内容,记得读完点一下“在看”,加个“星标”,这样每次新文章推送才会第一时间出现在你的订阅列表里。“在看”支持我们吧!

原文始发于微信公众号(Java笔记虾):List的remove()方法陷阱+性能优化