On the pit of deleting list in traversal

First of all, it introduces a case in the Alibaba protocol:

It is suggested that if you have time, you can go to Alibaba cloud to test the certification. If you pass the test, you will be issued an e-certification certificate, which is valid for two years.

List<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
for (String item : list) {
    if ("1".equals(item)) {
        list.remove(item);
    }
}

The execution result of the above code is sure to be unexpected, so try changing "1" in if to "2", will it be the same result? Please try it yourself.

The following describes a variable modCount in an ArrayList, which is used to record the number of changes to the current list.

  • First initialize the list:
List<String> list = new ArrayList<String>();
  • Then the assignment starts:
list.add("1");
list.add("2");

This step will judge the space first. If it is satisfied, put modCount+1, and then put the value into the elementdata array (the default length is 10).

  public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increases modcount!! increases the number of changes
        elementData[size++] = e;
        return true;
    }

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//More changes here

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

Beginning text

 public static void main(String[] args) {
        //Initialize list
        List<String> list = new ArrayList<String>();
        //Start assignment
        list.add("1");
        list.add("2");
        //Start traversal
        for (String item : list) {
            System.out.println(item);
            //Start by deleting 1
            if ("1".equals(item)) {
                list.remove(item);
            }
        }
        System.out.println("success");
    }
  • 1. Initialization & assignment
  • 2. ※ start traversing the list, and an assignment will be performed during traversing. Record the number of initial operation changes of traversal (later exception judgment)

  • 3. Judge whether the current cursor has completed the task before traversing. (note that this place will be used later)
  public boolean hasNext() {
            return cursor != size;
        }
  • 4. To get the next element, we will first judge checkforconformity (), and judge the original operation times and existing operation times when reading.
 final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }

Judge by returning the value of the current position. Failure is the exception above.

  • 5. Then enter remove to make a circular judgment and match. Finally, fastRemove()
    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;
    }

fastRemove will operate modCount + +;

    /*
     * Private remove method that skips bounds checking and does not
     * return the value removed.
     */
    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
    }

Only 1 was output and succeeded. Why not traverse to 2? Why didn't you make a mistake?

  • 6. Go back to step 2, because size has changed when element 1 is deleted in step 5. It is judged when traversing the second time that the traversal is completed (current cursor = size)
hasNext (cursor)0 != (size)2      :          true
remove Size - > 1; (element 1 is removed)
hasNext (cursor)1 != (size)1      :          false

 

 

 

 

7. Directly end the loop, and get the second element will not occur, so no judgment exception will be made.

 

 public static void main(String[] args) {
        //Initialize list
        List<String> list = new ArrayList<String>();
        //Start assignment
        list.add("1");
        list.add("2");
        //Start traversal
        for (String item : list) {
            System.out.println(item);
            //From delete 2
            if ("2".equals(item)) {
                list.remove(item);
            }
        }
        System.out.println("success");
    }

Traversal ended, but an exception was thrown.

  • 8. Because the size changes when element 2 is deleted, the cycle continues
hasNext (cursor)0 != (size)2      :          true
hasNext (cursor)1 != (size)2      :          true
remove Size - > 1; (element 1 is removed) modCount++
hasNext (cursor)2 != (size)1      :          true

 

 

 

 

 

  • 9. The traversal is successful. Then go to step 4. An exception occurs.

 

Published 38 original articles, won praise 16, visited 70000+
Private letter follow

Posted on Fri, 13 Mar 2020 21:02:45 -0700 by the-botman