遍历List移除元素时踩坑点

1、问题描述

在遍历List并在循环体中移除元素时需要注意以下几点

  1. 移除元素后数据总量会越来越小，可能造成数组下标越界

  2. 移除元素后，每个元素原有位置也会发生改变，需确认移除的元素是否是真正需要移除的

  3. 由于删除元素后，每个元素位置前移，会有部分数据直接跳过循环

    例如 数组中有以下数据

    i 0 1 2 3 4
    val 1 2 3 4 5

    当 i = 1 时 移除元素2，3会前移，下标1的值变为3，下标2的值变为4，后面的元素依次前移

    当 i = 1 的循环体结束后，i 自增，进入 i = 2 的循环体，此时 i = 2 对应的值为4 ，3被跳过，不经过循环体

2、问题复现

假设我有一个数组，需要移除下标为 0，1，2，3 的元素

image-20231120125313864

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
@Test
   public void testRemove1(){
       List<Integer> numbers = new ArrayList<>();
       for (int i = 0; i < 5; i++) {
           numbers.add(i);
       }
       System.out.println("old_numbers:"+numbers);

       List<Integer> itemsToRemove = new ArrayList<>();
       itemsToRemove.add(0);
       itemsToRemove.add(1);
       itemsToRemove.add(2);
       itemsToRemove.add(3);
       System.out.println(itemsToRemove);

       //移除元素时数据总长度减小,元素原本位置改变
       // 不仅会造成数组下标越界，移除的元素也并非想要移除的元素
       for (int  integer : itemsToRemove) {
           numbers.remove(integer);
       }

       System.out.println("new_numbers:"+numbers);
   }

假设我只需要移除下标为 0，1 的元素，下标0 对应的值应为0，下标1 对应的值应为1

移除后的元素应该是 [2，3，4] 但结果却是 [1，3，4]

image-20231120125730760

3、解决方案

可以使用 ListIterator 来安全地在迭代过程中删除元素，而不影响后续元素的位置

ListIterator 是 Java 中 List 接口提供的一个迭代器，相比普通的迭代器，它具有双向遍历的能力，允许在迭代过程中插入、删除元素，以及获取当前位置的索引。这使得在使用 List 类型的集合时，特别是在需要在迭代过程中修改集合的情况下，ListIterator 是一个更加强大的工具。

image-20231120130455982

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
@Test
    public void testRemove2(){
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            numbers.add(i);
        }
        System.out.println("old_numbers:"+numbers);

        List<Integer> itemsToRemove = new ArrayList<>();
        itemsToRemove.add(0);
        itemsToRemove.add(1);
        itemsToRemove.add(2);
        itemsToRemove.add(3);
        System.out.println(itemsToRemove);

        // 使用 ListIterator 正序遍历并删除需要删除的元素
        ListIterator<Integer> iterator = numbers.listIterator();
        while (iterator.hasNext()) {
            int indexToRemove = iterator.nextIndex();
            Integer nextVal = iterator.next();// 移动到下一个位置

//            System.out.println("index:"+indexToRemove+",value:"+nextVal);

            if (itemsToRemove.contains(nextVal)){
                iterator.remove(); // 安全地移除当前元素
                System.out.println("移除元素 index:"+indexToRemove+",value:"+nextVal);
            }
        }


        System.out.println("new_numbers:"+numbers);
    }

如果需要根据下标移除元素可以逆序遍历，此时itemsToRemove.contains(indexToRemove)使用的是下标

image-20231120134702313

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
@Test
    public void testRemove3(){
        List<Integer> numbers = new ArrayList<>();
        for (int i = 0; i < 5; i++) {
            numbers.add(i);
        }
        System.out.println("old_numbers:"+numbers);

        List<Integer> itemsToRemove = new ArrayList<>();
        itemsToRemove.add(0);
        itemsToRemove.add(1);
        itemsToRemove.add(2);
        itemsToRemove.add(3);
        System.out.println(itemsToRemove);


        // 使用 ListIterator 逆序遍历并删除需要删除的元素
        ListIterator<Integer> iterator = numbers.listIterator(numbers.size());
        while (iterator.hasPrevious()) {
            int indexToRemove = iterator.previousIndex();
            Integer previousVal = iterator.previous();// 移动到上一个位置

            if (itemsToRemove.contains(indexToRemove)){
                iterator.remove(); // 安全地移除当前元素
                System.out.println("移除元素 index:"+indexToRemove+",value:"+previousVal);
            }
        }

        System.out.println("new_numbers:"+numbers);
    }

根据下标移除元素时正序遍历可能会出问题

image-20231120140147752

ListIterator常见方法

  • hasNext()：判断是否还有下一个元素。
  • hasPrevious()：判断是否还有上一个元素。
  • next()：返回下一个元素。
  • previous()：返回上一个元素。
  • nextIndex()：返回下一个元素的索引。
  • previousIndex()：返回上一个元素的索引。
  • add(E element)：在当前位置插入指定的元素。
  • set(E element)：用指定的元素替换上一次调用 next() 或 previous() 返回的元素。
  • remove()：移除上一次调用 next() 或 previous() 返回的元素。

ListIterator 两种初始化方式

ListIterator 有两个不同的初始化方式，分别是：

  1. ListIterator<Integer> iterator = numbers.listIterator()：通过这种方式初始化的 ListIterator 位于列表的开始位置，即索引为 0 的位置。当你使用 iterator.next() 时，它会返回列表的第一个元素。
  2. ListIterator<Integer> iterator = numbers.listIterator(numbers.size())：通过这种方式初始化的 ListIterator 位于列表的末尾位置，即索引为 list.size() 的位置。当你使用 iterator.previous() 时，它会返回列表的最后一个元素。

总的来说，这两种方式初始化的 ListIterator 分别定位在列表的开始和末尾位置，选择取决于你是希望从前向后遍历还是从后向前遍历。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
javaCopy codeList<String> myList = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));

// 从前向后遍历
ListIterator<String> iteratorForward = myList.listIterator();
while (iteratorForward.hasNext()) {
    System.out.print(iteratorForward.next() + " ");
}
// 输出: A B C D

System.out.println();

// 从后向前遍历
ListIterator<String> iteratorBackward = myList.listIterator(myList.size());
while (iteratorBackward.hasPrevious()) {
    System.out.print(iteratorBackward.previous() + " ");
}
// 输出: D C B A

在这个示例中，iteratorForward 从前向后遍历列表，而 iteratorBackward 从后向前遍历列表。