## 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.