Question:
How does this process work inside ArrayList ? I would like to know the details of the implementation. How does it operate with meanings? In particular, what the grow() method does and how.
Answer:
First, let's figure out in what ways the ArrayList can be increased.
1) using add(T element) method
2) using the add(int index, T element) method
3) using the addAll(Collection<? extends T> c) method
4) using the addAll(int index, Collection<? extends T> c) method
Let's analyze each of the methods separately:
1) Here is the source code for the add(T element) method:
public boolean add(E e) {
modCount++;
add(e, elementData, size);
return true;
}
It increments the variable modCount (the number of structural conversions). Here is an excerpt from javadoc 1.4:
This field is used by the iterator and implements the implementation of the iterator returned by the iterator and listIterator methods. If the value of this field changes unexpectedly, the iterator (or list iterator) will throw a ConcurrentModificationException in response to the following actions: delete, previous, set, or add. This provides fault-tolerant behavior rather than non-deterministic behavior in the face of concurrent modification during iteration.
Then it calls the add(E e, Object[], int s) method. And then it returns true, since it should return this value, as it is specified in Collection.add(E e) .
Let's analyze this method add(E e, Object[] elementData, int s) . Here is the source code:
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
The variable e is our element to be created. In the variable elementData – an array of all elements (may not be completely filled), and s – the number of elements actually located in the array of elements. If the array is not completely filled, we add an element to the array and increase the variable containing the number of actually located elements. Otherwise, in addition to this, we first increase the size of the array using the grow() method.
Let's take a look at this grow() method. Here is the source code:
private Object[] grow() {
return grow(size + 1);
}
This means that it only calls another grow method, but this time with the int minCapacity parameter, into which we put the value of the variable containing the number of actually located elements, increased by one. Here is its source code:
private Object[] grow(int minCapacity) {
int oldCapacity = elementData.length;
if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
int newCapacity = ArraysSupport.newLength(oldCapacity,
minCapacity - oldCapacity, /* minimum growth */
oldCapacity >> 1 /* preferred growth */);
return elementData = Arrays.copyOf(elementData, newCapacity);
} else {
return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
}
}
If the array is not empty, then we increase our original array by a length equal to half (rounding down) the old length, if the resulting length is not more than the maximum length of the array ( Integer.MAX_VALUE - 8 ), otherwise equal to the maximum length of the array if oldLength + minGrowth less the maximum length of the array, otherwise equal to Integer.MAX_VALUE .
Otherwise, we re-initialize the array, passing in a reference to an array of objects of length 10 or minCapacity if minCapacity > 10.
If anyone is interested in the ArraysSupport.newLength code, here are the sources (I just found it from java 13 ):
public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
// assert oldLength >= 0
// assert minGrowth > 0
int newLength = Math.max(minGrowth, prefGrowth) + oldLength;
if (newLength - MAX_ARRAY_LENGTH <= 0) {
return newLength;
}
return hugeLength(oldLength, minGrowth);
}
private static int hugeLength(int oldLength, int minGrowth) {
int minLength = oldLength + minGrowth;
if (minLength < 0) { // overflow
throw new OutOfMemoryError("Required array length too large");
}
if (minLength <= MAX_ARRAY_LENGTH) {
return MAX_ARRAY_LENGTH;
}
return Integer.MAX_VALUE;
}
The parsing of the add(T element) method is complete.
2) Here is the source code for the add(int index, T element) method:
public void add(int index, E element) {
rangeCheckForAdd(index);
modCount++;
final int s;
Object[] elementData;
if ((s = size) == (elementData = this.elementData).length)
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
elementData[index] = element;
size = s + 1;
}
rangeCheckForAdd(int index) throws an error if index not one of the real elements. modCount is traditionally increasing. Then we increase the length of the array using the grow() method, if there is no room for the new element, and shift all the elements to the right of the index where the element is to be inserted to the right, inserting the object to be inserted into the resulting "empty space". The internal variable length has traditionally been increased.
3) Here is the source code for the addAll(Collection<? extends T> c) method:
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
modCount traditionally increasing. We get an array from the collection so that we can insert the array using the standard method. If the collection to be inserted is empty, then return false . If the collection being inserted does not fit into the array, we increase it. Then we add the "collection" to the very end of the array. The internal variable length has traditionally been increased. We report on the successful completion of the work.
4) Here is the source code for the addAll(int index, Collection<? extends T> c) method:
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
modCount++;
int numNew = a.length;
if (numNew == 0)
return false;
Object[] elementData;
final int s;
if (numNew > (elementData = this.elementData).length - (s = size))
elementData = grow(s + numNew);
int numMoved = s - index;
if (numMoved > 0)
System.arraycopy(elementData, index,
elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size = s + numNew;
return true;
}
rangeCheckForAdd(int index) performs the same function as inserting a single element. We do the same as in addAll(Collection<? extends T> c) , up to the line with the creation of the numMoved variable, which stores the number of real array elements following index inclusively (remember that iteration starts from 0!). If they exist at all, then we move them to the right, freeing up space for the inserted collection. Then the collection is inserted into the range starting at index . The internal variable length has traditionally been increased. We report on the successful completion of the work.
Thank you for your attention. If you notice a mistake or inaccuracy, tell me about it, I am ready to accept any criticism.