FaQs

ArrayList is an expansion method

  1. Construct an empty collection from ArrayList(), with an initial length of 0

  2. The first time you add an element, you create an array of length 10 and assign the element to the first position in the array

  3. The second time I add the element, the set is not empty, and since the size of the set +1 is less than the length of the array 10, I directly add the element to the second position of the array without expanding it

  4. Create an array of size 10+10*0.5 = 15 (multiplied by 1.5) and copy the references to the original array elements into the new array. And assigns the eleventh addition to the new array with subscript 10.

  5. When newCapacity -max_array_size > 0, use hugeCapacity(minCapacity) to expand capacity (minCapacity > MAX_ARRAY_SIZE). Integer.MAX_VALUE :MAX_ARRAY_SIZE

  6. An OutOfMemoryError is thrown when the element is added at integer.max_value + 1

The source code is as follows:

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

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

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
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);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}
Copy the code

ArrayList and LinkedLisL

  1. Both are list-based interfaces and are not thread-safe

  2. Arraylist is the underlying array, linkedList is the underlying list

  3. Array queries are fast for querying specific elements, and slow for inserting or deleting (arrays are contiguous chunks of memory, which move memory when inserting or deleting)

  4. Linked list does not require continuous memory, the current element stores the address of the last or next element, the query needs to start from the head to find one by one, the query efficiency is low, there is no need to move the memory when inserting, just change the reference point, so the insertion or deletion efficiency is high

  5. ArrayList is used in scenarios where there are many queries, few inserts, or few queries

  6. LinkedList is used in scenarios where insertions or deletions are high and queries are low