Note: The JDK versions used in this series are Java8

The ArrayList class diagram looks like this:

The bottom layer of ArrayList is implemented by arrays, which are characterized by fixed size, whereas ArrayList implements dynamic expansion.

Some of the ArrayList variables are shown below, which will be used in the following analysis.

/** * Default capacity */
private static final int DEFAULT_CAPACITY = 10;
/** * empty object array */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** * An empty array */ created by the no-argument constructor
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * The cache variable that holds the array of data */
transient Object[] elementData;
/** * Number of elements */
private int size;
Copy the code

Initialize the ArrayList

An ArrayList is typically initialized using the following two constructors

1.1 No-parameter constructor

If no size is specified when initializing an ArrayList, an empty array is created.

public ArrayList(a) {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

1.2 Constructor to specify array size

Create an array of estimated size. The specified size only specifies the initial size of the array, which does not affect subsequent expansion. The specified value can save memory and time.

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 code

Two, add elements, dynamic capacity expansion

Arraylist.add (E E)

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
Copy the code

ElementData [size++] = e in add() is pretty easy to understand, insert the element at the size position, and then size++, we’ll focus on ensureCapacityInternal(size + 1);

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
Copy the code

The ensureCapacityInternal() method determines whether the cache variable elementData is empty, that is, if the element is being added for the first time, then the initial size is set to the default size of 10, otherwise the parameter passed in. The purpose of this method is to get the initialization array capacity. Call the ensureExplicitCapacity(minCapacity) method when the initial capacity is obtained.

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
Copy the code

The ensureExplicitCapacity(minCapacity) method is used to determine whether an element needs to be expanded. If minCapacity is 10 and elementData is 0 for the first time, the element needs to be expanded. Call the grow(minCapacity) method.

// The maximum size of the array
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // Expand the size to 1.5 times the original array length
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // If the capacity to be expanded is smaller than the capacity to be expanded, use the capacity to be expanded
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // If the expanded capacity is larger than the maximum array length, use the maximum integer length
    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 code

The grow(minCapacity) method expands the array by 1.5 times the size of the original array. If the calculated capacity is smaller than the required capacity, the required capacity is used. If the calculated capacity is larger than the maximum capacity of the array, call hugeCapacity(minCapacity). Expand the array to the maximum length of an integer, then point the elemetData array to the newly expanded memory space and copy the elements to the new space.

If the required collection capacity is very large, capacity expansion by 1.5 times consumes a lot of space. Therefore, you are advised to estimate the capacity during initialization.

Delete elements

ArrayList provides two methods for deleting elements, by index and element. The two types of deletion are essentially the same: after an element is deleted, the next element is moved forward at a time.

Arraylist. remove(int index)

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;
}
Copy the code

When an element is deleted, it determines whether the index is greater than the size of the ArrayList. If the index range is correct, the next element at the index position is assigned to the index position, the ArrayList size is -1, and the removed element is returned. Let’s say I want to remove an element with index 1:

Four,

The underlying ArrayList is an array implementation, and it can be dynamically expanded by 1.5 times the original size. Although it can be dynamically expanded, space is wasted when the array is very large. Therefore, it is recommended to estimate the size of the array during initialization. ArrayList allows you to insert duplicate and null values. ArrayList implements RandomAccess and supports fast RandomAccess, which means that you can quickly look up an element through an index, so using a for loop is more efficient. ArrayList is thread safe, can pass the Collections. SynchronizedList turned them into thread-safe Collections, but generally will not use, Vector and CopyOnWriteArrayList is thread-safe, Vector performance in general, Gradually replaced by CopyOnWriteArrayList.

Focus, don’t get lost

If you think the article is good, please pay attention to it, like it, and save it. Your support is the motivation for my creation. Thank you all.

If there is a problem with the article, please don’t be stingy with the writing, welcome to point out the message, I will check and revise in time.

If you want to see more things, you can search “Java Journey” on wechat to follow. “Java Journey” has compiled various middleware tutorials and various Java-related interview questions. This information can be obtained by scanning the QR code below to follow.