Java List的remove()方法陷阱以及性能優(yōu)化

更新時(shí)間：2021年10月31日 15:23:05 作者：wsdfym

Java List在進(jìn)行remove（）方法是通常容易踩坑，本文就詳細(xì)的介紹一下陷阱以及性能優(yōu)化，感興趣的可以了解一下

Java List在進(jìn)行remove（）方法是通常容易踩坑，主要有一下幾點(diǎn)

循環(huán)時(shí)：?jiǎn)栴}在于，刪除某個(gè)元素后，因?yàn)閯h除元素后，后面的元素都往前移動(dòng)了一位，而你的索引+1，所以實(shí)際訪問的元素相對(duì)于刪除的元素中間間隔了一位。

幾種常見方法

1.使用for循環(huán)不進(jìn)行額外處理時(shí)（錯(cuò)誤）

//錯(cuò)誤的方法
for(int i=0;i<list.size();i++) {
	if(list.get(i)%2==0) {
		list.remove(i);
	}
}

2.使用foreach循環(huán)（錯(cuò)誤）

for(Integer i:list) {
    if(i%2==0) {
     	list.remove(i);
    }
}

拋出異常：java.util.ConcurrentModificationException；
foreach的本質(zhì)是使用迭代器實(shí)現(xiàn)，每次進(jìn)入for (Integer i:list) 時(shí)，會(huì)調(diào)用ListItr.next()方法；
繼而調(diào)用checkForComodification()方法， checkForComodification()方法對(duì)操作集合的次數(shù)進(jìn)行了判斷，如果當(dāng)前對(duì)集合的操作次數(shù)與生成迭代器時(shí)不同，拋出異常

public E next() {
	checkForComodification();
	if (!hasNext()) {
		 throw new NoSuchElementException();
	}
	 lastReturned = next;
	next = next.next;
	nextIndex++;
	return lastReturned.item;
 }
 // checkForComodification()方法對(duì)集合遍歷前被修改的次數(shù)與現(xiàn)在被修改的次數(shù)做出對(duì)比
final void checkForComodification() {
	  if (modCount != expectedModCount) {
	  		 throw new ConcurrentModificationException();
	  }
             
  }

使用for循環(huán)，并且同時(shí)改變索引；（正確）

//正確
for(int i=0;i<list.size();i++) {
	if(list.get(i)%2==0) {
		list.remove(i);
		i--;//在元素被移除掉后，進(jìn)行索引后移
	}
}

使用for循環(huán)，倒序進(jìn)行；（正確）

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

使用while循環(huán)，刪除了元素，索引便不+1，在沒刪除元素時(shí)索引+1（正確）

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

4.使用迭代器方法（正確,推薦）

只能使用迭代器的remove()方法，使用列表的remove()方法是錯(cuò)誤的

//正確，并且推薦的方法
Iterator<Integer> itr = list.iterator();
while(itr.hasNext()) {
	if(itr.next()%2 ==0)
		itr.remove();
}

性能分析

下面來談?wù)劗?dāng)數(shù)據(jù)量過大時(shí)候，需要?jiǎng)h除的元素較多時(shí)，如何用迭代器進(jìn)行性能的優(yōu)化，對(duì)于ArrayList這幾乎是致命的，從一個(gè)ArrayList中刪除批量元素都是昂貴的時(shí)間復(fù)雜度為O（n²），那么接下來看看LinkeedList是否可行。LinkedList暴露了兩個(gè)問題，一個(gè)：是每次的Get請(qǐng)求效率不高，而且，對(duì)于remove的調(diào)用同樣低效，因?yàn)檫_(dá)到位置I的代價(jià)是昂貴的。

是每次的Get請(qǐng)求效率不高
需要先get元素，然后過濾元素。比較元素是否滿足刪除條件。

remove的調(diào)用同樣低效
LinkedList的remove（index），方法是需要先遍歷鏈表，先找到該index下的節(jié)點(diǎn)，再處理節(jié)點(diǎn)的前驅(qū)后繼。

以上兩個(gè)問題當(dāng)遇到批量級(jí)別需要處理時(shí)時(shí)間復(fù)雜度直接上升到O（n²）

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

對(duì)于LinkedList，對(duì)該迭代器的remove（）方法的調(diào)用只花費(fèi)常數(shù)時(shí)間，因?yàn)樵谘h(huán)時(shí)該迭代器位于需要被刪除的節(jié)點(diǎn)，因此是常數(shù)操作。對(duì)于一個(gè)ArrayList，即使該迭代器位于需要被刪除的節(jié)點(diǎn)，其remove（）方法依然是昂貴的，因?yàn)閿?shù)組項(xiàng)必須移動(dòng)。下面貼出示例代碼以及運(yùn)行結(jié)果

在這里插入圖片描述

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偶數(shù)
		long sTime = new Date().getTime();
		Iterator<Integer> itr = lst.iterator();
		while(itr.hasNext()) {
			
			if(itr.next()%2 ==0)
				itr.remove();
		}
		
		System.out.println(name+"使用迭代器時(shí)間:"+(new Date().getTime()-sTime)+"毫秒");
	}
	
	public static void removeEvens(List<Integer> list , String name) {//不使用迭代器remove偶數(shù)
		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+"不使用迭代器的時(shí)間"+(new Date().getTime()-sTime)+"毫秒");
	}
}

原理重點(diǎn)看一下LinkedList的迭代器

另一篇博客Iterator簡(jiǎn)介 LinkedList使用迭代器優(yōu)化移除批量元素原理
調(diào)用方法：list.iterator();

在這里插入圖片描述

重點(diǎn)看下remove方法

private class ListItr implements ListIterator<E> {
        //返回的節(jié)點(diǎn)
        private Node<E> lastReturned;
        //下一個(gè)節(jié)點(diǎn)
        private Node<E> next;
        //下一個(gè)節(jié)點(diǎn)索引
        private int nextIndex;
        //修改次數(shù)
        private int expectedModCount = modCount;

        ListItr(int index) {
            //根據(jù)傳進(jìn)來的數(shù)字設(shè)置next等屬性，默認(rèn)傳0
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }
        //直接調(diào)用節(jié)點(diǎn)的后繼指針
        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();
            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }
        //返回節(jié)點(diǎn)的前驅(qū)
        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }
        /**
        * 最重要的方法，在LinkedList中按一定規(guī)則移除大量元素時(shí)用這個(gè)方法
        * 為什么會(huì)比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)的過程是
先逐一移動(dòng)指針，再找到要移除的Node，最后再修改這個(gè)Node前驅(qū)后繼等移除Node。如果有批量元素要按規(guī)則移除的話這么做時(shí)間復(fù)雜度O（n²）。但是使用迭代器是O（n）。

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

LinkedList是雙向鏈表，這里示意圖簡(jiǎn)單畫個(gè)單鏈表
比如要移除鏈表中偶數(shù)元素，先循環(huán)調(diào)用get方法，指針逐漸后移獲得元素，比如獲得index = 1；指針后移兩次才能獲得元素。
當(dāng)發(fā)現(xiàn)元素值為偶數(shù)是。使用idnex移除元素，如list.remove(1)；鏈表先Node node(int index)返回該index下的元素，與get方法一樣。然后再做前驅(qū)后繼的修改。所以在remove之前相當(dāng)于做了兩次get請(qǐng)求。導(dǎo)致時(shí)間復(fù)雜度是O（n）。

在這里插入圖片描述