The beauty of design patterns by Wang Zheng Study notes

What happens when you add or delete collection elements while traversing?

• While traversing the collection elements through the iterator, adding or deleting the elements in the collection may lead to a certain element being traversed repeatedly or not being traversed.
• Unexpected behavior or pending behavior: whether the operation result is right or wrong depends on the situation.

For example, delete the element

public interface Iterator<E> {
  boolean hasNext();
  void next();
  E currentItem();
}

public class ArrayIterator<E> implements Iterator<E> {
  private int cursor;
  private ArrayList<E> arrayList;
  public ArrayIterator(ArrayList<E> arrayList) {
    this.cursor = 0;
    this.arrayList = arrayList;
  }
  @Override
  public boolean hasNext() {
    return cursor < arrayList.size();
  }
  @Override
  public void next() {
    cursor++;
  }
  @Override
  public E currentItem() {
    if (cursor >= arrayList.size()) {
      throw new NoSuchElementException();
    }
    return arrayList.get(cursor);
  }
}

public interface List<E> {
  Iterator iterator();
}

public class ArrayList<E> implements List<E> {
  //...
  public Iterator iterator() {
    return new ArrayIterator(this);
  }
  //...
}

public class Demo {
  public static void main(String[] args) {
    List<String> names = new ArrayList<>();
    names.add("a");
    names.add("b");
    names.add("c");
    names.add("d");
    Iterator<String> iterator = names.iterator();
    iterator.next();
    names.remove("a");
  }
}

• The bottom layer of ArrayList corresponds to the data structure of array. When the 55th line of code is executed, four elements a, b, c and d are stored in the array, and the cursor of the iterator points to element a.
• When you finish executing line 56, the cursor points to element b. there is no problem here.
• When we execute the code in line 57, we delete element a from the array, and the three elements b, c and d will move forward one bit in turn. This will cause the cursor to point to element b, but now it will point to element c.
• If the code in line 57 deletes not the element in front of the cursor (element a) and the element where the cursor is located (element b), but the element behind the cursor (elements c and d), there will be no problem and no element cannot be traversed.

For example, add elements

public class Demo {
  public static void main(String[] args) {
    List<String> names = new ArrayList<>();
    names.add("a");
    names.add("b");
    names.add("c");
    names.add("d");
    Iterator<String> iterator = names.iterator();
    iterator.next();
    names.add(0, "x");
  }
}

• After executing the code in line 10, the array contains four elements a, b, c and d. the cursor points to the element b, and element a has been skipped.
• After executing the code in line 11, we insert x into the position with subscript 0, and the four elements a, b, c and d move one bit back in turn. At this time, the cursor points to element a again. Element a is repeatedly pointed to by the cursor twice, that is, element a is repeatedly traversed.
• Similar to deletion, if we add an element after the cursor, there will be no problem.

How to deal with the pending behavior caused by changing the collection during traversal?

• One is that elements are not allowed to be added or deleted during traversal.
  • The first solution is difficult to implement. We need to determine the time points at which the traversal starts and ends.
  • We can easily get the time node at the beginning of traversal. We can take the point in time when the iterator is created as the point in time when the traversal begins.
  • When traversing to the last element, even if it ends, in actual software development, you don't have to traverse all elements every time you use an iterator to traverse elements. For example, if we find an element with a specified value, we end the traversal ahead of time.
  • Define a new interface finishIteration() in the iterator class to actively inform the container that the iterator is used up and you can add or delete elements. However, this requires programmers to actively call this function after using the iterator, which also increases the development cost and is easy to miss.
• The other is to make the traversal report an error after adding or deleting elements.
  • The second solution is more reasonable.
  • We define a member variable modCount in ArrayList to record the number of times the collection has been modified. Each time the collection calls the function of adding or deleting elements, it will add 1 to modCount.
  • When creating an iterator by calling the iterator() function on the set, we pass the modCount value to the expectedModCount member variable of the iterator. After that, every time we call the hasNext(), next(), currentItem() functions on the iterator, we will check whether the modCount on the set is equal to expectedModCount. That is, after creating the iterator, Whether modCount has changed.
  • If the two values are different, it means that the elements stored in the collection have changed, or the elements have been added or deleted. The iterator previously created can no longer run correctly. If we continue to use it, we will produce unexpected results. Therefore, we choose the fail fast solution, throw a runtime exception and end the program, Let the programmer fix the bug caused by improper use of iterators as soon as possible.

How to safely delete collection elements while traversing?

• Like the Java language, in addition to the most basic methods mentioned above, the iterator class also defines a remove() method, which can safely delete the elements in the collection while traversing the collection. However, it should be noted that it does not provide a method to add elements. After all, the main function of the iterator is traversal, and adding elements to the iterator itself is not appropriate.
• The remove() method provided in the Java iterator is limited. It can only delete the previous element pointed to by the cursor, and a next() function can only be followed by at most one remove() operation. Calling remove() multiple times will report an error.
• The iterator class adds a lastRet member variable to record the previous element pointed to by the cursor. When deleting this element through the iterator, we can update the cursor and lastRet value in the iterator to ensure that an element cannot be traversed due to the deletion of an element.
• If we delete elements through the container and want to update the cursor value in the iterator to ensure that there is no error in the traversal, we need to maintain the iterators created by the container and whether each iterator is still in use. The code implementation becomes more complex.