Java 基础 - List 遍历时为什么不能通过 for 循环进行删除，而使用 Iterator 可以？

旧城等待， 2022-10-29 11:25 111阅读 0赞

# 说明 #

List 在遍历时可以进行添加，删除操作吗？为什么？Iterator 是什么？可以进行上述操作吗？知道底层原理吗？

以上问题是我在面试时碰到的，在本篇博文中，我将通过源码对 List 遍历时的添加，删除操作的相关知识点进行总结。

注意，这里的操作都是针对正在遍历的 List 自身的操作。

首先，回答以上问题：

*  在普通的 for 循环中，可以进行数据的添加操作，但不能进行删除操作。
 *  在增强的 for 循环中，既不能进行添加操作，也不能进行删除操作。
 *  通过 Iterator 及相关扩展类，可以进行添加或删除操作。

接下来，我将通过示例和源码来解释为什么。

# 正文 #

## 普通 for 循环 ##

在普通 for 循环中，可以进行数据的添加，但是不能删除删除。原因是在删除时，由于坐标值的增加，会导致数据遗漏。

示例：

public static void main(String[] args) { 
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(2);
        nums.add(3);
        nums.add(4);
        for (int i = 0; i < nums.size(); i++) { 
            Integer num = nums.get(i);
            System.out.println(num);
            if (num.equals(2)) { 
                nums.remove(num);
            }
        }
    }
    ---- 输出 ----
    1
    2
    4

可以看到，在删除 2 后，下一个元素 3 在遍历时被遗漏了。

这是因为在删除 2 后，剩余的元素会整体向前移动一位，而坐标值仍是递增的，所以下一个坐标元素值相当于当前删除元素的下下一位元素值。对此，我们可以在删除元素时，将坐标值减 1。

if (num.equals(2)) { 
        nums.remove(num);
        i--;
    }

### List.remove ###

在以上示例中，我使用的是 ArrayList.remove(Object o) 方法，该方法会移除 List 中第一个满足目标值的元素。

// Removes the first occurrence of the specified element from this list, if it is present.
    public boolean remove(Object o) { 
        if (o == null) { 
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) { 
                    fastRemove(index);
                    return true;
                }
        } else { 
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) { 
                    // 调用 fastRemove 进行数据删除
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }
    
    // 在该方法中省略了边界值的校验，并不用返回删除元素值
    private void fastRemove(int index) { 
        // 记录了结构修改次数
        modCount++;
        // 计算该坐标之后的元素个数，并使之都向前移动一位
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

通过源码我们可以看到，在元素删除时，使用了 System.arraycopy 方法进行了元素位置的移动。

当我们使用坐标删除元素时，调用 ArrayList.remove(int index) 方法，该方法与 fastRemove 方法类似，但多了边界值的校验以及返回被删除元素值。

## 增强 for 循环 ##

在使用 foreach 循环遍历 list 时，既不能添加数据，也不能删除数据，当进行此操作时，会抛出 ConcurrentModificationException 异常。

示例：

public static void main(String[] args) { 
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(2);
        nums.add(3);
        nums.add(4);
        for (Integer num : nums) { 
            if (num.equals(2)) { 
                nums.remove(num);
            }
        }
    }
    
    ---- 输出 ----
    Exception in thread "main" java.util.ConcurrentModificationException
    	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:909)
    	at java.util.ArrayList$Itr.next(ArrayList.java:859)

通过异常信息我们可以看到，在数据删除后继续遍历时，在 ConcurrentModificationException 方法出抛出异常，而该方法是由 ArrayList 的内部类 Itr 的 next 方法调用的。而 Itr 正是 ArrayList 的 Iterator 接口的内部实现类。

foreach 为什么会使用 Itr 类？我们先将该类进行反编译：

public static void main(String[] args) { 
        List<Integer> nums = new ArrayList();
        nums.add(1);
        nums.add(2);
        nums.add(3);
        nums.add(4);
        Iterator var2 = nums.iterator();
    
        while(var2.hasNext()) { 
            Integer num = (Integer)var2.next();
            if (num.equals(2)) { 
                nums.remove(num);
            }
        }
    
    }

在反编译后，可以看到 foreach 创建了一个 Iterator 实例来进行集合的遍历。

那为什么使用的是 Iterator 实例进行遍历删除的，还会抛错？

再看代码，因为我们调用的是 list 自身的 remove 方法。在进行元素删除后，继续调用 next() 方法获取下一个元素，在该方法中首先会调用 checkForComodification() 判断 list 结构是否发生改变，若是则触发 fail-fast 机制抛出 ConcurrentModificationException 异常。

final void checkForComodification() { 
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

在 checkForComodification() 方法中，则通过 modCount 值判断结构发生改变，在创建 Itr 对象时，实例变量 expectedModCount 被赋值为 modCount。

## Iterator ##

在通过 Iterator 及其扩展类遍历 list 时，可以进行数据的添加和删除。

示例：

public static void main(String[] args) { 
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(2);
        nums.add(3);
        nums.add(4);
        Iterator<Integer> iterator = nums.iterator();
        while (iterator.hasNext()) { 
            Integer num = iterator.next();
            System.out.println(num);
            if (num.equals(2)) { 
                iterator.remove();
            }
        }
        System.out.println("res size : " + nums.size());
    
        ListIterator<Integer> listIterator = nums.listIterator();
        while (listIterator.hasNext()) { 
            Integer num = listIterator.next();
            if (num.equals(3)) { 
                listIterator.add(5);
            }
        }
        System.out.println("new size : " + nums.size());
    }
    
    ---- 输出 ----
    1
    2
    3
    4
    res size : 3
    new size : 4

通过以上示例可以看出，Iterator 的实现类 Itr 遍历删除数据，不会发生数据遗漏，而该实例对象只能进行数据的获取和删除，通过 ListIterator 的实现类 ListItr 遍历，则可以进行数据的添加。

ListIterator 是 Iterator 的扩展类，对 List 集合有更多的操作，允许回溯，修改，添加，删除等操作。

注意，在删除时，我们调用的是 Iterator 的 remove() 方法，在该方法中调用了 list 自身的 remove 方法。

那可以通过以下操作进行删除吗？

Iterator<Integer> iterator = nums.iterator();
    while (iterator.hasNext()) { 
        iterator.remove();
    }

答案是**否定**的，执行时会抛出 IllegalStateException 异常。

接下来，通过源码来了解 Iterator 的工作原理。

### ArrayList.Itr ###

该类是 ArrayList 对 Iterator 接口的内部实现类，是 AbstractList.Itr 的优化版本。

private class Itr implements Iterator<E> { 
            int cursor; // 下一个要返回元素的
            int lastRet = -1;  // 最后已返回元素的坐标，默认值为 -1
            int expectedModCount = modCount;
    
            Itr() { }
            .....
            
    }

通过源码可以看到，在 Itr 类内部有三个实例变量，分别表示为下个元素的坐标，当前元素坐标，及结构修改次数标记。

#### remove ####

public void remove() { 
        // 判断是否调用过 next() 方法
        if (lastRet < 0)
            throw new IllegalStateException();
        // 检查结构是否有变化
        checkForComodification();
    
        try { 
            // 调用 list 自身的方法删除元素
            ArrayList.this.remove(lastRet);
            // 坐标赋值
            cursor = lastRet;
            lastRet = -1;
            // 给 expectedModCount 重新赋值
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) { 
            throw new ConcurrentModificationException();
        }
    }

在 remove 方法中，主要进行了以下操作：

*  首先判断 lastRet 的值，也就是当前返回元素的坐标，该值又是通过 next() 方法进行设置，所以在不调用 next() 方法直接 remove 会抛出 IllegalStateException 异常
 *  接着判断数据结构是否被其他线程修改
 *  调用 ArrayList 自身的 remove 方法删除元素
 *  修改坐标 cursor 设置为当前 lastRet，lastRet 值设置为 -1，这样防止了数据遗漏
 *  最后为 expectedModCount 重新赋值

通过源码可以看到，Itr 通过自带坐标的修改及 expectedModCount 值的使用，避免了数据遗漏及并发修改数据的可能性。

### ArrayList.ListItr ###

该类是 Iterator 的扩展类，继承自 Itr 类并实现了 ListIterator 接口。  
通过该类在遍历时可以进行回溯，更新，添加，删除等操作。

添加示例：

public static void main(String[] args) { 
        List<Integer> nums = new ArrayList<>();
        nums.add(1);
        nums.add(2);
        nums.add(3);
        nums.add(4);
        ListIterator<Integer> listIterator = nums.listIterator();
        while (listIterator.hasNext()) { 
            Integer num = listIterator.next();
            System.out.println(num);
            if (num.equals(3)) { 
                listIterator.add(5);
            }
        }
        System.out.println("新遍历输出 : ");
        nums.forEach(System.out::println);
    }
    ---- 输出 ----
    1
    2
    3
    4
    新遍历输出 : 
    1
    2
    3
    5
    4

可以看出，在进行添加操作时，并不是直接在末尾直接添加，而是在当前值的下个位置进行插入，新插入的值在当前的遍历过程中会被忽略。

#### add ####

public void add(E e) { 
        checkForComodification();
    
        try { 
            // 在下个元素位置进行插入
            int i = cursor;
            ArrayList.this.add(i, e);
            // 跳过最新插入值
            cursor = i + 1;
            lastRet = -1;
            // 重新标记 modCount
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) { 
            throw new ConcurrentModificationException();
        }
    }

通过源码可以看到，在插入时的坐标是 cursor 值，而该值表示的是下个元素的坐标；也是调用的 ArrayList 自身的 add 方法，在添加完成后重新为坐标赋值，cursor 值跳过了新插入值，lastRet 设置为 -1，并重新标记了 modCount。

至此，关于 List 不同方式遍历时的数据操作的特性已经介绍完毕。ListIterator 还有多种其他用法，有兴趣的同学可以阅读其源码。

# 总结 #

对于 List 遍历时的删除，应该通过 Iterator 来实现。普通的 for 循环会造成数据遗漏，不过可以通过代码修改坐标来避免，但在增强 for 循环中，数据的添加或删除都会触发 fast-fail，导致抛出异常。

Iterator 的底层原理则是通过三个实例变量，控制遍历的前后坐标及标记数据结构修改次数状态来保证遍历中的数据操作正确性。