ArrayList (ArrayList)

The rest of the ArrayList class includes private inner classes that implement the iterator and subList sublists specified by the upper interface.

The iterator

According to the List interface specification, lists support two types of iterators: normal iterators inherited from collections and iterators that allow bidirectional traversal of the List itself. The ArrayList class uses class Itr and Class ListItr to customize the implementation of two iterators, which are also optimizations of AbstractList implementations.

Iterator

// Returns iterators for the elements in this list in the appropriate order
public Iterator<E> iterator(a) {
    return new Itr();
}
Copy the code

The ArrayList method returns an iterator object for the list, which can then be used to traverse the list.

Member variable & constructor

private class Itr implements Iterator<E> {
    int cursor;       // The index of the next element to be returned
    int lastRet = -1; // The index of the last returned element, reset to -1 if this element is removed by calling remove
    int expectedModCount = modCount; // The modCount value that the iterator thinks the list should have. If this expectation is violated, the iterator has detected concurrent modifications

    Itr() {}
}
Copy the code

The variable expectedModCount is initialized to the number of times the list structure is modified. If the list structure is modified during iterator traversal, the fast failure interrupt traversal will be introduced in detail in the source code below.

Iterator operation

// Returns true if the iterator also iterates over elements
public boolean hasNext(a) {
    returncursor ! = size; }Copy the code

The cursor is used to compare the length of the list. If the iterator is finished, the cursor == size will be used.

// Returns the next element of the iteration
public E next(a) {
    checkForComodification();
    int i = cursor;
    if (i >= size)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i + 1;
    return (E) elementData[lastRet = i];
}
Copy the code

// Verify concurrent changes. Use final definitions to prevent overwriting
final void checkForComodification(a) {
    if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
}
Copy the code

Next () is the main way iterators traverse the list, starting with a logic that runs through the iterator: Check of concurrent modification, through the list of modCount and iterators created expectedModCount comparison, if not equal means iterators generated after the list structure has been modified, will throw ConcurrentModificationException interrupt traversal, This is the main logic for iterators to fail quickly. After verifying concurrent changes, it enters normal logic:

1. Check the cursor value of the iterator if it is greater than the listsizeThrows if there is no value to returnNoSuchElementException;
2. If the cursor value is greater than the length of the list array, the list structure has been modified, and a concurrent modification exception is thrownConcurrentModificationException;
3. The final will becursorIncrementing, equals the index of the next element, and returns the current element, solastRetAssigns the index of the current element.

// Removes the last element returned by the iterator from the list. This method can only be called once per next() call
public void remove(a) {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();
    try {
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw newConcurrentModificationException(); }}Copy the code

First check the value of lastRet, which in normal traversal is equal to the index of the last returned element. If it is less than 0, no previous calls to next() have returned elements (or this method has been executed), so there are no elements to delete, IllegalStateException is thrown, and the logic to check for concurrent changes is executed.

After normal validation, remove() of the external class is called to remove the elements of the specified index in the list. We then assign the value of lastRet to cursor, because the index of the next element to be iterated over after deleting an element is still the current index. According to the ArstractList document specification, after the iterator deletes an element, lastRet is reset to -1. This also shows another case where lastRet < 0 is generated in the first step. As a final step, do not forget to update the expectedModCount to the new modCount, since removing the element will also change the list structure so that the iterator can be traversed properly.

And in this code, in order to further prevent concurrent modification, capture all IndexOutOfBoundsException, throws concurrent modification abnormalities.

The iterator contains another traversal method, forEachRemaining, which is used to traverse the remaining elements at one time. The code logic is relatively clear, and it does not do source code parsing.

ListIterator

// Returns a list iterator for the elements in this list, starting at the specified position in the list. The specified index indicates that the initial call to Next will
// The first element returned. The initial call to Previous returns the element of the specified index minus one
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}
// Returns a list iterator for the elements in this list
public ListIterator<E> listIterator(a) {
    return new ListItr(0);
}
Copy the code

These are two ways to get list iterators in ArrayList. The ListIterator is inherited from the normal iterator and implements ListIterator, so the logic for backward traversal is the same as in Itr, with forward traversal and some other methods added.

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        cursor = index;
    }
}

public E previous(a) {
    checkForComodification();
    int i = cursor - 1;
    if (i < 0)
        throw new NoSuchElementException();
    Object[] elementData = ArrayList.this.elementData;
    if (i >= elementData.length)
        throw new ConcurrentModificationException();
    cursor = i;
    return (E) elementData[lastRet = i];
}

public boolean hasPrevious(a) {
    returncursor ! =0;
}
Copy the code

The forward traversal method is similar to the implementation logic of next(), except that the cursor is “slid” forward. And when the cursor goes to 0 it can’t do the previous traversal. In addition, two methods are provided to get the index of the before and after elements:

// Returns the index of the element to be returned by subsequent calls to next. If the list iterator is at the end of the list, return the list size
public int nextIndex(a) {
    return cursor;
}
// Returns the index of the element to be returned by subsequent calls to previous. If the list iterator is at the beginning of the list, -1 is returned
public int previousIndex(a) {
    return cursor - 1;
}
Copy the code

Other methods

public void add(E e) {
    checkForComodification();
    try {
        int i = cursor;
        ArrayList.this.add(i, e);
        cursor = i + 1;
        lastRet = -1;
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw newConcurrentModificationException(); }}Copy the code

According to the documentation, this method has no effect on subsequent calls to next() until the element is cursor, whereas a call to previous() returns the element. Therefore, after insertion, the cursor is incremented by 1, lastRet is reset to -1, and the value of the expectedModCount is updated.

// Replace the last element returned by next or previous with the specified element (optional),
// This call can only be made if remove and add have not been called since the last call to next or previous
public void set(E e) {
    if (lastRet < 0)
        throw new IllegalStateException();
    checkForComodification();
    try {
        ArrayList.this.set(lastRet, e);
    } catch (IndexOutOfBoundsException ex) {
        throw newConcurrentModificationException(); }}Copy the code

Method disallows calls after remove() and add(), so lastRet is checked first, and if reset to -1, indicates an illegal state. It then checks for concurrent modifications, and finally calls the set () method of the ArrayList directly to replace the elements.

The iterators supported in ArrayList are relatively simple, but control the iterator over the list is very convenient, and the fast failure mechanism controls the list modification very carefully.

Child list

SubList is an operational property unique to List lists. The returned child List is supported by the parent List, so unstructural changes to the child List are reflected in the parent List and vice versa. Structural changes are those that change the size of the list or otherwise mess with it so that ongoing iterations may produce incorrect results. In ArrayList, sublists have internal SubList implementations that inherit AbstractList to implement basic logical and iterator operations for lists.

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this.0, fromIndex, toIndex);
}

static void subListRangeCheck(int fromIndex, int toIndex, int size) {
    if (fromIndex < 0)
        throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
    if (toIndex > size)
        throw new IndexOutOfBoundsException("toIndex = " + toIndex);
    if (fromIndex > toIndex)
        throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                           ") > toIndex(" + toIndex + ")");
}
Copy the code

This method is the only method in the list that retrieves a sublist of elements within the range by two indexes of the parameter. If necessary, check the validity of the parameters: the start index cannot be less than 0, the end index cannot be larger than the list length, and the start index cannot be larger than the end index. According to the documentation, if fromIndex and toIndex are equal, the list returned is empty. Then a sublist is constructed from the parameters.

SubList

private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount; }}Copy the code

An AbstractList type reference is maintained internally. ParentOffset represents an offset from the parent list, equal to the fromIndex of the child list, which is used when operating on parent. Offset, in addition, records an offset from the top-level list, which will be set when creating a sublist from a sublist, otherwise equal to fromIndex; Size records the length of the sublist, and modCount controls concurrent operations.

The method logic of SubList is basically the same as that of ArrayList, except that the array of lists to operate on is an array from the top-level parent list.

public E get(int index) {
    rangeCheck(index);
    checkForComodification();
    return ArrayList.this.elementData(offset + index);
}

public void add(int index, E e) {
    rangeCheckForAdd(index);
    checkForComodification();
    parent.add(parentOffset + index, e);
    this.modCount = parent.modCount;
    this.size++;
}

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, offset, fromIndex, toIndex);
}
Copy the code

The get method retrieves the elements of the sublist, and the methods other than checkindex and concurrent modification are familiar. The value is retrieved from the array of the ArrayList through offset + index. In the Add method, the added elements are added via the parent list object that is held. Finally, the subList method creates the subList with an offset, the only difference from arrayList.sublist (). ParentOffset and offset can be seen from these variables.

Java container source code learning analysis topic — ArrayList source code learning (2)