Introduction to the
ArrayList is one of the more commonly used data structures in Java collections frameworks. AbstractList implements the List interface. The bottom layer implements dynamic change of capacity size based on array. Allow NULL. The RandomAccess, Cloneable and Serializable interfaces are also implemented, so ArrayList supports fast access, replication, and serialization.
Member variables
The underlying ArrayList is based on arrays to implement dynamic capacity changes.
/** * The size of the ArrayList (the number of elements it contains). */ private int size; // Transient Object[] elementData;Copy the codeNote: Size above refers to how many elements are actually in elementData, while elementData.length is the collection capacity, indicating how many elements can be held at most.
The default initial capacity is 10.
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
Copy the codeThis variable is defined in AbstractList. Records the number of operations on List. The main use is in Iterator, to prevent collections from being modified during iteration.
protected transient int modCount = 0;
Copy the codeThe following two variables are used in constructors
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Copy the codeWhat’s the difference between two empty arrays? We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added. In simple terms, the first time you add an element, you know that the elementData is initialized from an empty constructor or from a parameter constructor. To determine how to expand capacity.
The constructor
- No tragedy constructor
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeNote: The comment says to construct an empty list of size 10, but the constructor simply assigns an empty array to elementData, which grows to 10 the first time an element is added.
- Construct an ArrayList whose initialCapacity is initialCapacity
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the codeDEFAULTCAPACITY_EMPTY_ELEMENTDATA is assigned to elementData when using the no-argument constructor. When initialCapacity is zero, EMPTY_ELEMENTDATA is assigned to elementData. Initialize an object array of size initialCapacity and assign it to elementData when initialCapacity is greater than zero.
- Constructor to construct an ArrayList using the specified Collection
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if((size = elementData.length) ! = 0) { // c.toArray might (incorrectly) notreturn Object[] (see 6260652)
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else{ // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeConvert Collection to an array and assign to elementData, and assign the number of elements in elementData to size. If size is not zero, the class type of elementData is determined to be Object[]. If not, a conversion is performed. If size is zero, assign EMPTY_ELEMENTDATA to elementData, equivalent to new ArrayList(0).
Analysis of main operation methods
- The add operation
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the codeEach time you add an element to a collection, you check the size of the collection. Then increase size by 1. So if elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA we’re going to take the maximum value of DEFAULT_CAPACITY and minCapacity 10. This is where EMPTY_ELEMENTDATA differs from DEFAULTCAPACITY_EMPTY_ELEMENTDATA. It also validates the above statement that using the no-tragedy constructor initializes capacity 10 on the first addition of an element. Incrementing modCount by one in ensureExplicitCapacity records the number of operations, and then expanding the collection if minCapacity is greater than the length of elementData. Obviously elementData has zero length when the element is first added. Let’s look at the grow function.
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the codeA simple and clear function, the default capacity will be increased to 1.5 times the original capacity. However, expansion may not be applicable, may be too small, may be too large. That’s why we have these two if judgments. If 1.5 times is too small, then we assign the required capacity to newCapacity. If 1.5 times is too large or the required capacity is too large, then newCapacity = (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE to expand capacity. It then copies the data from the original array into a new array of size newCapacity and assigns the new array to elementData.
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
returnnumNew ! = 0; } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index;if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
returnnumNew ! = 0; }Copy the codeAdd (int index, E element), addAll(Collection<? Extends E> c), addAll(int index, Collection<? Extends E> c) the extends E> c) operation is to check the size of the collection first to ensure that the array is not out of bounds. The elements of the old array are then copied into a new array using the system.arrayCopy () method.
- The remove operation
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
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
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
}
Copy the codeWhen we call remove(int index), we first check if the index is valid and then determine if the element to be removed is in the last position in the array. If index is not the last, the system.arrayCopy () method is called again to copy the array. So basically we’re going to start at index + 1 and we’re going to move all the elements forward one place. Then empty the last position of the array, size-1. If index is the last element, empty the last position of the array, size-1. When we call remove(Object O), we separate o into whether or not it is empty. We then iterate through the array to find the first index that corresponds to o, and then call fastRemove to delete the element with index. In fact, the fastRemove(int index) method and remove(int index) method are basically the same.
- Get operation
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
Copy the codeBecause ArrayList is based on arrays at the bottom, fetching elements is fairly straightforward, just by calling array random access.
The iterator iterator
If you’ve ever worked with a collection, you can’t remove a collection while iterating through it with a for, because remove changes the size of the collection. Thus easy to cause the inaccurate array subscript crossing the line, even more serious will throw ConcurrentModificationException.
Foreach traversal is equivalent to iterator. To understand the cause of the exception, we must also go through the source code.
public Iterator<E> iterator() {
return new Itr();
}
Copy the codeIt returns an Itr object directly.
private class Itr implements Iterator<E> {
int cursor; // index of next element to returnint lastRet = -1; // index of last element returned; - 1if no such
int expectedModCount = modCount;
public boolean hasNext() {
returncursor ! = size; } @SuppressWarnings("unchecked")
public E next() {
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];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
Copy the codeFrom the source, ArrayList defines an internal class Itr that implements the Iterator interface. There are three member variables inside the Itr. Cursor: Represents the index of the next element to access. LastRet: represents the subscript of the last element to access. ExpectedModCount: Indicates the expected number of changes to the ArrayList. The initial value is modCount.
Let’s look at the three main functions of Itr.
The hasNext implementation is relatively simple; if the subscript of the next element is equal to the size of the collection, the proof is final.
The Next method is also not complicated, but it is critical. First check whether expectedModCount and modCount are equal. Then check whether the cursor exceeds the set size and array length. Then assign cursor to lastRet and return the element with subscript lastRet. Finally, increase the cursor by 1. Start with cursor = 0, lastRet = -1; Each time the next method is called, the cursor and lastRet increment by one.
The remove method first checks whether the lastRet value is less than 0 and then checks whether the expectedModCount and modCount are equal. Next comes the key, calling the remove method of ArrayList directly to remove the element with subscript lastRet. It then assigns lastRet to CURSOR, reassigns lastRet to -1, and reassigns modCount to expectedModCount.
Let’s analyze the Itr operation step by step. As shown in Figure 1, start with cursor pointing to an element with subscript 0 and lastRet pointing to an element with subscript -1, which is null. Each time next is called, the cursor and lastRet increment by 1, respectively. When Next returns “C”, cursor and lastRet are 3 and 2, respectively [Figure 2].
At this point, remove is called. Note that it is the remove of ArrayList, not the remove of Itr. The D and E elements are moved directly forward by one, leaving the last position empty, and the modCount increases by one. You can see from the remove method. [Fig.3].
Cursor = 3, size = 4, not at the end of the array, so the loop continues. ExpectedModCount is not equal to modCount because modCount is modified by the remove method in the previous step. This is the reason why ConcurrentModificationException anomalies. PNG also shows that the exception comes from the checkForComodification method in the inner Itr class of ArrayList.
Exception resolution:
Simply call iterator.remove(). Because the expectedModCount = modCount operation is added to this method. But there are drawbacks to this remove method.
- Only remove operations can be performed, but add and clear operations are not available in Itr.
- You must call next before calling remove. Because Remove checked lastRet in the first place. LastRet initializes at -1.
- You can only call remove once after next. Because remove reinitializes lastRet to -1
Bottom line: ArrayList implements dynamically variable capacity based on arrays. The capacity expansion mechanism is to expand the capacity by 1.5 times of the original capacity. If 1.5 times is too small, then we assign the required capacity to newCapacity. If 1.5 times is too large or the required capacity is too large, then newCapacity = (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE to expand capacity. After capacity expansion, the element accuracy is ensured by copying the array, so minimize capacity expansion. Maximum storage capacity of an ArrayList: integer.max_value. Size is the number of elements stored in the collection. Elementdata. length is the length of the array, indicating the maximum number of elements that can be stored. If you want to iterate and remove at the same time, you must use iterator. “Remove” must be followed by “Next” and “remove” can only be used once after “next”.