A study of the interview question “ArrayList loop remove() will use Iterator”

Two months ago I was in an interview and I was asked how an ArrayList loops over and deletes elements, and I said “Iterator.” When the interviewer asked me why I wanted to use Iterator instead of foreach, I didn’t answer. Now that I think about it, I think I should fix it. So I wrote a small demo and read the source code to verify it.

Here are four cases of the ArrayList loop remove() that I validated, and their results (based on Oracle JDk1.8) :

//List<Integer> list = new ArrayList<>(); //list.add(1); //list.add(2); //list.add(3); //list.add(4); // Code snippets for the 4 cases of loop remove() : //# 1
for (Integer integer : list) {
    list.remove(integer); } result: Exceptionin thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
    at java.util.ArrayList$Itr.next(ArrayList.java:851)
-----------------------------------------------------------------------------------

//# 2
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) {
    Integer integer = iterator.next();
    list.remove(integer); } result: Exceptionin thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
    at java.util.ArrayList$Itr.next(ArrayList.java:851)
-----------------------------------------------------------------------------------


//# 3
for(int i = 0; i < list.size(); i++) { list.remove(i); } System.out.println(list); Results: [2, 4] -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- / /# 4
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){ iterator.next(); iterator.remove(); } System.out.println(list.size()); Result :(the only one that gets the expected value) 0Copy the code

It can be seen that only the last of these cases can get the expected result, and the others are either abnormal or not, so let’s analyze them one by one.

# 1

//# 1
for (Integer integer : list) {
    list.remove(integer); } result: Exceptionin thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
    at java.util.ArrayList$Itr.next(ArrayList.java:851)Copy the code

Through the exception stack, We can positioning is in the interior of the ArrayList class Itr checkForComodification methods included the ConcurrentModificationException anomalies (about this exception is how to return a responsibility we aside) we open the ArrayList source Code, located at line 901:

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

This method of throwing exceptions actually does one thing, check modCount! ExpectedModCount = expectedModCount = expectedModCount = expectedModCount = expectedModCount = expectedModCount = expectedModCount = expectedModCount = expectedModCount

/**
 * The number of times this list has been <i>structurally modified</i>.
 * Structural modifications are those that change the size of the
 * list, or otherwise perturb it in such a fashion that iterations in
 * progress may yield incorrect results.
 *
 * <p>This field is used by the iterator and list iterator implementation
 * returned by the {@code iterator} and {@code listIterator} methods.
 * If the value of this field changes unexpectedly, the iterator (or list
 * iterator) will throw a {@code ConcurrentModificationException} in
 * response to the {@code next}, {@code remove}, {@code previous},
 * {@code set} or {@code add} operations.  This provides
 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in
 * the face of concurrent modification during iteration.
 *
 * <p><b>Use of this field by subclasses is optional.</b> If a subclass
 * wishes to provide fail-fast iterators (and list iterators), then it
 * merely has to increment this field in its {@code add(int, E)} and
 * {@code remove(int)} methods (and any other methods that it overrides
 * that result in structural modifications to the list).  A single call to
 * {@code add(int, E)} or {@code remove(int)} must add no more than
 * one to this field, or the iterators (and list iterators) will throw
 * bogus {@code ConcurrentModificationExceptions}.  If an implementation
 * does not wish to provide fail-fast iterators, this field may be
 * ignored.
 */
protected transient int modCount = 0;Copy the code

This field is used to record the number of times the set has been modified by a subset class with fail-fast behavior. EnsureExplicitCapacity (int minCapacity), a method in the call chain of add(E E), increments modCount:

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

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

We called Add (E E) 4 times when we initialized the list so now modCount is 4

expectedModCount
ArrayList
Iterator
Itr
modCount

Itr
foreach
Iterator
Itr

Cycle:

next()
checkForComodification()

list.remove()

ArrayList
remove(Object o)
fastRemove(index)

fastRemove(index)
modCount
modCount
add(E e)
4
++
5

Moving on to the next iteration:

next()
next()
checkForComodification()
modCount
fastRemove(index)
5
expectedModCount
modCount ! = expectedModCount
fail-fast

# 2

//# 2
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) {
    Integer integer = iterator.next();
    list.remove(integer); } result: Exceptionin thread "main" java.util.ConcurrentModificationException
    at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
    at java.util.ArrayList$Itr.next(ArrayList.java:851)Copy the code

Foreach is optimized for Iterator calls at compile time, so just look at #1.

# 3

//# 3
for(int i = 0; i < list.size(); i++) { list.remove(i); } System.out.println(list); Results: [2, 4]Copy the code

This kind of po-faced nonsense might happen when you get sleepy writing code… Instead of writing it, let’s use println() :

Remove (0) remove(0) list: [1, 2, 3, 4] remove(0) list.size()=4 [2, 3, 4] next loop I =1 next loop list.size()=3 :trueRemove (1) remove(1) list.size()=2 remove(1) list.size()=2 remove(1) list: [2, 4] next loop I =2 next loop list.size()=2 :false


Process finished with exit code 0Copy the code

In fact, the Itr in ArrayList solves this problem by using cursors and the index of the last return value, which will be explained in #4.

# 4

This is exactly how it works, using remove() of the iterator Itr of ArrayList instead of remove() of ArrayList itself. Let’s debug and see what happens:

Iterations:

Itr initialization: cursor = 0; Last return value index lastRet = -1; ExpectedModCount = modCount = 4;

hasNext()
size

next()
checkForComodification()
expectedModCount
modCount
ConcurrentModificationException
0
0
0

Iterator.remove () : similarly checkForComodification() then calls remove(lastRet) of ArrayList to remove the last returned element, after which modCount will increase

After the deletion is complete, the cursor is assigned to the last return index, which is actually the cursor is moved back one space to the previous position. Then the last return index is reset to the initial value -1, and finally the expectedModCount is reset to the new modCount after the last step is completed

size
remove()
- 1
remove()
remove()
0
size
remove()
expectedModCount
modCount
fail-fast

ArrayList loop remove() to use Iterator to do a little research, did not consider the concurrent scenario, this article wrote about 3 hours, after writing this article office left me a person, I should go back, today 1024 programmers section, everyone happy holidays!

---

2017.10.25 update # 1

Thank you @llearn for reminding us that #3 can also be used in a clever way to get the correct result.

For (int I = 0; i < list.size(); ) { list.remove(0); } System.out.println(list);

2017.10.25 update # 2

Thanks to @chinlong for providing another way to avoid Iterator, which is to loop backwards (I thought of that when I wrote the article, but didn’t verify it myself), thanks to @chinlong:

However, no one and I like a way to delete. I heard someone say that iterating backwards is slightly faster. for (int i = list.size() -1; i >= 0; i– ) { list.remove(i); } System.out.println(list);