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

短命女 2022-01-27 04:45 313阅读 0赞

### 文章目录 ###

*   *  几种常见方法
     *  性能分析
     *  使用迭代器的方法删除元素
     *  原理 重点看一下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();
    	  }
                 
      }

*  使用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（）方法依然是昂贵的，因为数组项必须移动。下面贴出示例代码以及运行结果  
![在这里插入图片描述][2019052517530268.png]

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使用迭代器优化移除批量元素原理][Iterator_ LinkedList]  
调用方法：**list.iterator();**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center]  
重点看下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）。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 2]  
继续移除下一个元素需要重新再走一遍链表（步骤忽略当index大于半数，链表倒序查找）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 3]  
以上如果移除偶数指针做了6次移动。

*  删除2节点  
    get请求移动1次，remove（1）移动1次。
 *  删除4节点  
    get请求移动2次，remove（2）移动2次。

## 迭代器的处理 ##

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

[2019052517530268.png]: /images/20220127/ed6f38e4f2d84c42b22aedf875ecd487.png
[Iterator_ LinkedList]: https://blog.csdn.net/wsdfym/article/details/109633368
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20220127/ff9916ac42b6451e90b3c689dc4db5be.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20220127/32b4845b91ee4b60bcff3293c18a28e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20220127/b308ca6f999c46778cc2948c78ec43bf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20220127/b96a6d7a06ad41729a39704dac27db8d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dzZGZ5bQ_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20220127/af0b0bd49c2f492882185d25be2bf25f.png