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

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();
	  }

  }

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

//正确
for(int i=0;i<list.size();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<list.size()) {
	if(list.get(i)%2==0) {
		list.remove(i);
	}else {
		i++;
	}
}

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

只能使用迭代器的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()方法依然是昂贵的,因为数组项必须移动。下面贴出示例代码以及运行结果

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的迭代器

另一篇博客Iterator简介 LinkedList使用迭代器优化移除批量元素原理
调用方法:list.iterator();

重点看下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)。

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

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

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

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

迭代器的处理

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

到此这篇关于Java List的remove()方法陷阱以及性能优化的文章就介绍到这了,更多相关Java List的remove() 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java中List遍历删除元素remove()的方法

    今天碰见根据条件进行list遍历remove的问题,第一时间就是简单for循环remove,只知道这么写不行,不安全,可是为什么呢?你想过吗?下面就关于List遍历remove的问题,深挖一下! 一.几种常见的遍历方式 1.普通for循环 2.高级for循环 3.iterator和removeIf 4.stream() 5.复制 6.普通for循环 --> 倒序方式 二.源码篇 1.普通for循环出错原因 public boolean remove(Object o) { if (o == nu

  • java ArrayList.remove()的三种错误用法以及六种正确用法详解

    java集合中,list列表应该是我们最常使用的,它有两种常见的实现类:ArrayList和LinkedList.ArrayList底层是数组,查找比较方便:LinkedList底层是链表,更适合做新增和删除.但实际开发中,我们也会遇到使用ArrayList需要删除列表元素的时候.虽然ArrayList类已经提供了remove方法,不过其中有潜在的坑,下面将介绍remove方法的三种错误用法以及六种正确用法. 1.错误用法 1.1.for循环中使用remove(int index),列表从前往后

  • Java List的remove()方法踩坑

    目录 1.普通for循环遍历List删除指定元素--错误!!! 2.for循环遍历List删除元素时,让索引同步调整--正确! 3.倒序遍历List删除元素--正确! 4.foreach遍历List删除元素--错误!!! 5.迭代删除List元素--正确! 6.迭代遍历,用list.remove(i)方法删除元素--错误!!! 7.List删除元素时,注意Integer类型和int类型的区别. 总结: Java的List在删除元素时,一般会用list.remove(o)/remove(i)方法.

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

    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(Inte

  • 浅谈java Iterator.remove()方法的用法(详解)

    实例如下: @Test public void tt(){ List<String> list = new ArrayList<String>(); list.add( "0" ); list.add( "1" ); list.add( "2" ); list.add( "3" ); list.add( "4" ); list.add( "5" ); list.a

  • Java list.remove( )方法注意事项

    这篇文章给大家简单介绍了Java list.remove( )方法注意事项,具体内容如下: List<Integer> integerList = new ArrayList<>(); 当我们要移除某个Item的时候 remove(int position):移除某个位置的Item remove(object object):移除某个对象 那么remove(12)到底是移除第12的item,还是移除内容为12的Item. 那就要看12到底是int类型还是Integer类型,如果是i

  • 解决Java Calendar类set()方法的陷阱

    在项目中,需要获取指定年份和月份的最后一天.我在网上找到了一个用Calendar类获取的方法,代码如下: import java.text.SimpleDateFormat; import java.util.Calendar; import java.util.Date; public class TestCalendar { public static void main(String[] args) { String s = new SimpleDateFormat("yyyy-MM-dd

  • 浅谈Java list.remove( )方法需要注意的两个坑

    list.remove 最近做项目的过程中,需要用到list.remove()方法,结果发现两个有趣的坑,经过分析后找到原因,记录一下跟大家分享一下. 代码 直接上一段代码,进行分析. public class Main { public static void main(String[] args) { List<String> stringList = new ArrayList<>();//数据集合 List<Integer> integerList = new

  • Java 集合的Contains和Remove方法

    一.包含与删除两种方法解析 1.boolean contains(Object o);判断集合中是否包含某个元素. package com.bjpowernode.java_learning; import java.util.*; ​ public class D85_1_ContainsMethod { public static void main(String[] args) { //创建集合 Collection c = new ArrayList(); //创建两个Integer类型

  • java ArrayList中的remove方法介绍

    先看一段代码,看看自定义的ArrayList中的remove设计是否有问题. public class MyArrayList { private Object[] mData = new Object[0]; private int mSize = 0; // 删除第i个元素 public void remove(int i) { if (i < 0 || i >= mSize) return; for (int index = i; index < mSize - 1; index+

  • Java虚拟机JVM性能优化(三):垃圾收集详解

    Java平台的垃圾收集机制显著提高了开发者的效率,但是一个实现糟糕的垃圾收集器可能过多地消耗应用程序的资源.在Java虚拟机性能优化系列的第三部分,Eva Andreasson向Java初学者介绍了Java平台的内存模型和垃圾收集机制.她解释了为什么碎片化(而不是垃圾收集)是Java应用程序性能的主要问题所在,以及为什么分代垃圾收集和压缩是目前处理Java应用程序碎片化的主要办法(但不是最有新意的). 垃圾收集(GC)的目的是释放那些不再被任何活动对象引用的Java对象所占用的内存,它是Java

  • Java性能优化技巧汇总

    本文实例汇总了Java性能优化技巧.分享给大家供大家参考.具体分析如下: 这里参考了些书籍,网络资源整理出来,适合于大多数Java应用 在JAVA程序中,性能问题的大部分原因并不在于JAVA语言,而是程序本身.养成良好的编码习惯非常重要,能够显著地提升程序性能. 1.尽量使用final修饰符. 带有final修饰符的类是不可派生的.在JAVA核心API中,有许多应用final的例子,例如java.lang.String.为String类指定final防止了使用者覆盖length()方法.另外,如

随机推荐