ArrayList删除节点

ArrayList的remove方法，进行删除的时候，数组的长度不变，但被删除的节点之后的数据会前移，看源码可知。

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
33
34
35
36
37
38
39
40
41
42
43
44
public E remove(int index) {
      // 先检查下标索引是是否越界
      rangeCheck(index);
      // ArrayList的修改次数加1
      modCount++;
      // 获取索引对应的元素值
      E oldValue = elementData(index);
      // 获取删除元素后，需要移动的元素的个数
      int numMoved = size - index - 1;
      if (numMoved > 0)
          // 将元素进行移动拷贝
          System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
      // 最后将多出的位置设置为空，这样说明是没有引用的对象了
      elementData[--size] = null; // Let gc do its work
      // 返回删除的旧值
      return oldValue;
}

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

如果这样操作就会有问题：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ArrayList<String> list = new ArrayList<String>();
list.add("java");
list.add("android");
list.add("android");
list.add("c");
list.add("c++");
list.add("c");

public void remove1(ArrayList<String> list) {
    for (inti=0; i<list.size(); i++) {
        String s = list.get(i);
        if (s.equals("android")) {
            list.remove(s);
        }
    }
}

public void remove2(ArrayList<String> list) {
    for (Strings: list) {
        if (s.equals("android")) {
            list.remove(s);
        }
    }
}

remove1 方法执行后第二个 “android” 字符串没有被删掉。看源码可知最终删除会执行 System.arraycopy 方法而导致删除元素时涉及到数组元素的移动，所以在遍历第一个字符串 “android” 时因为符合删除条件，所以将该元素从数组中删除，并且将后一个元素移动（也就是第二个字符串 “android”）至当前位置，导致下一次循环遍历时后一个字符串 “android” 并没有被遍历到，所以无法删除，同时由于每删除一次 size 也减一，所以其实每次都会向前移位，也会导致越来越多的元素无法被遍历获取。
remove2 方法运行会报 for-each 著名的并发修改异常 java.util.ConcurrentModificationException，因为迭代器内部会维护一些索引位置数据，要求在迭代过程中容器不能发生结构性变化（添加、插入、删除，修改数据不算），否则这些索引位置数据就失效了。

那么如何正确的删除节点。该造上面两个方法即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//从尾部循环
public void remove1(ArrayList<String> list) {
    for(int i=list.size()-1; i>=0; i--) {
        String s = list.get(i);
        if (s.equals("android")) {
            list.remove(s);
        }
    }
}
//利用迭代器
public static void remove2(ArrayList<String> list) {
    Iterator<String> iterator = list.iterator();
    while(iterator.hasNext()){
        if (iterator.next().equals("android")) {
            iterator.remove();
        }
    }
}

Iterator 和 ListIterator 的区别

区别主要如下：

  • ListIterator 有 add() 方法，可以向 List 中添加对象，而 Iterator 不能。
  • ListIterator 和 Iterator 都有 hasNext() 和 next() 方法，可以实现顺序向后遍历，但是 ListIterator 有 hasPrevious() 和 previous() 方法，可以实现逆向（顺序向前）遍历，Iterator 就不可以。
  • ListIterator 可以定位当前的索引位置，通过 nextIndex() 和 previousIndex() 可以实现，Iterator 没有此功能。
  • 都可实现删除对象，但是 ListIterator 可以实现对象的修改，通过 set() 方法可以实现，Iterator 仅能遍历，不能修改。
  • ListIterator 是 Iterator 的子接口。

    注意：容器类提供的迭代器都会在迭代中间进行结构性变化检测，如果容器发生了结构性变化，就会抛出 ConcurrentModificationException，所以不能在迭代中间直接调用容器类提供的 add、remove 方法，如需添加和删除，应调用迭代器的相关方法。

为什么使用 for-each 时调用 List 的 remove 方法元素会抛出 ConcurrentModificationException 异常

首先Java 提供了一个 Iterable 接口返回一个迭代器，常用的 Collection、List、Set 等都实现了这个接口，该接口的 iterator() 方法返回一个标准的 Iterator 实现，实现 Iterable 接口允许对象成为 for-each 语句的目标来遍历底层集合序列，因此使用 for-each 方式遍历列表在编译后实质是迭代器的形式实现。之所以会出现 ConcurrentModificationException 异常我们需要去看下最常见的 ArrayList 中 iterator() 方法的实现（别的集合 iterator 类似），如下：

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
    private class Itr implements Iterator<E> {
    protected int limit = ArrayList.this.size;  //集合列表的个数尺寸
    int cursor;       //下一个元素的索引位置
    int lastRet = -1; //上一个元素的索引位置
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor < limit;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        //modCount用于记录ArrayList集合的修改次数，初始化为0，
        //每当集合被修改一次（结构上面的修改，内部update不算），
        //如add、remove等方法，modCount + 1，所以如果modCount不变，
        //则表示集合内容没有被修改。
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        int i = cursor;
        //如果下一个元素的索引位置超过了集合长度抛出异常
        if (i >= limit)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        //调用一次cursor加一次
        cursor = i + 1;
        //返回当前一个元素
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        //lastRet每次在remove成功后都需要在next()中重新赋值，
        //否则调用一次后再调用为-1异常，因此使用迭代器的remove方法
        //前必须先调用next()方法。
        if (lastRet < 0)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
            limit--;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    ......
}

通过上面的源码发现迭代操作中都有判断 modCount!=expectedModCount 的操作，在 ArrayList 中 modCount 是当前集合的版本号，每次修改（增、删）集合都会加 1，expectedModCount 是当前迭代器的版本号，在迭代器实例化时初始化为 modCount，所以当调用 ArrayList.add() 或 ArrayList.remove() 时只是更新了 modCount 的状态，而迭代器中的 expectedModCount 未修改，因此才会导致再次调用 Iterator.next() 方法时抛出 ConcurrentModificationException 异常。而使用 Iterator.remove() 方法没有问题是因为 Iterator 的 remove() 方法中有同步 expectedModCount 值，所以当下次再调用 next() 时检查不会抛出异常。这其实是一种快速失败机制，机制的规则就是当多个线程对 Collection 进行操作时若其中某一个线程通过 Iterator 遍历集合时该集合的内容被其他线程所改变，则抛出 ConcurrentModificationException 异常。
因此在使用 Iterator 遍历操作集合时应该保证在遍历集合的过程中不会对集合产生结构上的修改，如果在遍历过程中需要修改集合元素则一定要使用迭代器提供的修改方法而不是集合自身的修改方法，此外 for-each 循环遍历的实质是迭代器，使用迭代器的 remove() 方法前必须先调用迭代器的 next() 方法且不允许调用一次 next() 方法后调用多次 remove() 方法。