Java ArrayList ArrayList (JDK1.8)

An overview of the

ArrayList is implemented based on arrays and supports dynamically expanded dynamic arrays. Compared with arrays, it is one of the most commonly used collection classes in development because of its automatic expansion feature.

This article is based on JDK1.8. Without further ado, let’s explore the source code of ArrayList

Let's GO !!!

The class diagram

As you can see from the class diagram, ArrayList implements four interfaces and inherits one abstract class. The four interfaces are as follows:

List interface, mainly provides the array to add, delete, modify, iteration traversal and other operations.
Cloneable interface, indicating that ArrayList supports cloning.
RandomAccess interface, indicating that ArrayList supports fast RandomAccess.
Serializable interface, which indicates that ArrayList supports serialization.

AbstractList is an inherited abstract class, which mainly provides iterating through related operations. AbstractList –> ArrayList AbstractList –> ArrayList AbstractList –> ArrayList The List interface defines the action behavior, and the AbstractList abstract class provides a reusable algorithm skeleton. The resulting ArrayList implementation class customizes its own implementation interface.

Note that ArrayList actually heavily overwrites the AbstractList abstract class’s method implementation; So AbstractList doesn’t make a lot of sense for ArrayList, but lots of other subclasses of AbstractList do.

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess.Cloneable.java.io.Serializable
{
    / /...
}
Copy the code

The source code parsing

Before parsing the source code, let’s take a look at all the methods in an ArrayList and pick out the core ones.

/ * * * * * * * * * * * * * * * * * * in the ArrayList constructor * * * * * * * * * * * * * * * /
// Default constructor
ArrayList()

// Capacity is the default capacity of ArrayList. When capacity is insufficient due to increased data, half of the previous capacity is added.
ArrayList(int capacity)

// Create an ArrayList containing the Collection
ArrayList(Collection<? extends E> collection)

/ * * * * * * * * * * * * * * * * * * in the ArrayList API * * * * * * * * * * * * * * * * * * * * /
// API defined in the Collection
boolean             add(E object)
boolean             addAll(Collection<? extends E> collection)
void                clear(a)
boolean             contains(Object object)
boolean             containsAll(Collection
        collection)
boolean             equals(Object object)
int                 hashCode(a)
boolean             isEmpty(a)
Iterator<E>         iterator(a)
boolean             remove(Object object)
boolean             removeAll(Collection
        collection)
boolean             retainAll(Collection
        collection)
int                 size(a)
<T> T[]             toArray(T[] array)
Object[]            toArray(a)

// Apis defined in AbstractCollection
void                add(int location, E object)
boolean             addAll(int location, Collection<? extends E> collection)
E                   get(int location)
int                 indexOf(Object object)
int                 lastIndexOf(Object object)
ListIterator<E>     listIterator(int location)
ListIterator<E>     listIterator(a)
E                   remove(int location)
E                   set(int location, E object)
List<E>             subList(int start, int end)

// ArrayList added API
Object               clone(a)
void                 ensureCapacity(int minimumCapacity)
void                 trimToSize(a)
void                 removeRange(int fromIndex, int toIndex)
Copy the code

attribute

ArrayList has very few properties, just two: elementData and size; Where elementData represents an array of elements; Size represents the number of elements in the elementData array. For example, the elementData array is 8 in length, but contains only 4 elements, so the size attribute is 4.

The size() method is often called when using ArrayList, and returns the number of elements used in the elementData array, which is currently 4; And when we add a new element, size refers to the subscript of the new element (array subscripts start at 0).

/** * Array of elements * When adding an element, if the array is not enough, a new array will be created and the elements of the original array will be copied to the new data; Finally, point the application variable to the new array */
transient Object[] elementData;

/** * The size of the array * size represents the number of elements that have been used with elementData, i.e. the size() method */
private int size;
Copy the code

A constructor

There are three constructors for ArrayList, as shown below.

1. ArrayList(int initialCapacity)

ArrayList(int initialCapacity) constructor to create an elementData array based on the initialCapacity initialCapacity passed in. If we know the number of elements in advance when using ArrayList, we should use this constructor whenever possible to avoid data expansion, improve performance, and use memory wisely (without wasting anything).

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        // Initialize the capacity greater than 0, create an Object array
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        // Initialize the EMPTY_ELEMENTDATA object when the capacity is 0
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        // The parameter is abnormal
        throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}Copy the code

When initialCapcity is 0, an EMPTY_ELEMENTDATA object is used. Private static Final Object[] EMPTY_ELEMENTDATA = {} is an empty array. As you add elements, you expand the array to create the desired array.

2. ArryaList()

SonarLint () {if sonarLint is installed on your IDEA, you will be prompted to specify the initial capacity when creating collections

public ArrayList(a) {
    // The array is empty when it is created. The array of size 10 is initialized when the element is first added
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

The constructor uses the DEFAULTCAPACITY_EMPTY_ELEMENTDATA object. Private Static Final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {} Is an empty array.

“I was taught that the default size of ArrayList is 10 when the initialization size is not specified.”

An ArrayList is initialized to an empty array when the initialization size is not specified. But the ArrayList is initialized to an array of capacity 10 the first time an element is added. The reason for doing this is to save memory. Some scenarios may simply define an array without actually using it, and directly initializing an array of size 10 will cause unnecessary waste.

Careful friends might wonder: “Since these are empty arrays, why not just use the EMPTY_ELEMENTDATA empty array; Instead, you want to redefine a new empty array DEFAULTCAPACITY_EMPTY_ELEMENTDATA?”

Don’t worry, just say: “existence is reasonable.” The designer must have a special reason for doing this, and we’ll talk about the difference later when we talk about array expansion. DEFAULTCAPACITY_EMPTY_ELEMENTDATA’s first capacity expansion is 10, EMPTY_ELEMENTDATA’s first capacity expansion is 1.5 times, starting from 0; They start from different places.

3. ArrayList(Collection<? extends E> c)

ArrayList(Collection
c) constructor that uses the passed collection C as elementData for the ArrayList

public ArrayList(Collection<? extends E> c) {
    // Element pointing to c.toarray () toArray() creates a new array
    elementData = c.toArray();

    // The array is not empty
    if((size = elementData.length) ! =0) {
        // If the type of the collection element is not Object.class, copy it to object. class
        if (elementData.getClass() != Object[].class) {
            elementData = Arrays.copyOf(elementData, size, Object[].class);
        }
    } else {
        // The array is empty using the EMPTY_ELEMENTDATA object
        this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

When the elementData array is not empty, there is a type conversion because elementData is an array of type Object[].

The new element

The methods of adding elements are as follows:

Public Boolean add(E E) Adds an element to the array in sequence
Public void add(int index, E element) Adds an element at the specified index position
public boolean addAll(Collection
c) Adds elements sequentially after an array
public boolean addAll(int index, Collection
c) Extends an element at the specified index position

public boolean add(E e)

Inheriting from the AbstractList abstract class, add individual elements sequentially after an array.

public boolean add(E e) {
    // size is the number of elements in the current array, with +1 representing a new element
    ensureCapacityInternal(size + 1);
    Element [size] = e, size++
    elementData[size++] = e;
    // Add succeeded
    return true;
}
Copy the code

The method is only three lines of code, which looks relatively simple; Focus on what the EnrecapityInternal method does; As we know from the above introduction, the underlying implementation of ArrayList uses arrays, and its features support dynamic expansion; Therefore, when we add elements, we should consider whether the existing array capacity can support the addition of elements, if not, we should consider expanding the operation.

Let’s take a look at what the JDK designers did

The first STEP is the ensureCapacityInternal(int minCapacity) method, which ensures that the array has enough internal capacity to add elements.

At first, the calculateCapacity(Object[] elementData, int minCapacity) method is called to calculate the capacity required for this new operation. EnsureExplicitCapacity (int minCapacity) is then called to ensure sufficient capacity.

/** * Ensure that the array is large enough to add elements **@paramMinCapacity Minimum capacity */
private void ensureCapacityInternal(int minCapacity) {
    // Calculate the capacity
    int capacity = calculateCapacity(elementData, minCapacity);
    // Ensure that the capacity is sufficient -- if not, trigger expansion
    ensureExplicitCapacity(capacity);
}

Copy the code

STEP -2 Then let’s look at how the calculateCapacity(Object[] elementData, int minCapacity) method calculates the capacity required for this new operation.

If elementData is DEFAULTCAPACITY_EMPTY_ELEMENTDATA — when no initial capacity is specified; The value of minCapacity and DEFAULT_CAPACITY is larger.

/** * Calculate the capacity *@paramElementData element array *@paramMinCapacity Minimum capacity *@return int
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // If it is DEFAULT_CAPACITY, then it will start from 10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // DEFAULT_CAPACITY definition: private static final int DEFAULT_CAPACITY = 10;
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // If not, return the minimum required capacity
    return minCapacity;
}
Copy the code

Step-3 ensureExplicitCapacity How to ensure that the array capacity is sufficient for this new operation? As you can see from the code, grow() is triggered to perform expansion when the minimum required minCapacity is greater than the length of the elementData.length array.


/** * make sure the array has enough free space **@paramMinCapacity Minimum capacity */
private void ensureExplicitCapacity(int minCapacity) {
    AbstractList > < AbstractList > < AbstractList >
    modCount++;

    // minCapacity represents the minimum capacity required for this operation, and elementData.length represents the length of the current element array
    MinCapacity > elementdata.length
    if (minCapacity - elementData.length > 0) {
        // The minimum capacity can be specified (to meet current requirements)grow(minCapacity); }}Copy the code

Step4 See how to expand grow

/** * Capacity expansion * Compare the old capacity with the minCapacity after being expanded to 1.5. * If the old capacity is larger than 1.5 times, use the minCapacity. Otherwise, use the minCapacity@paramMinCapacity Minimum capacity required for a new operation */
private void grow(int minCapacity) {
    // Old capacity size The length of the elementData array
    int oldCapacity = elementData.length;
    // New capacity size == old + old bit operation (move 1 bit to the right) is roughly 1.5 times the old size
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // If the calculated new capacity is less than the specified minimum size, a new array of the specified minimum size is created
    // newCapacity < minCapacity. // newCapacity < minCapacity.
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    // If the new capacity is larger than the maximum value (there will be insufficient memory)
    // private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        // The hugeCapicaty method is used to ensure that the array created does not overflow when newCapacity exceeds the specified range
        newCapacity = hugeCapacity(minCapacity);
    }
    // Copy the original data to the new array
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Copy the code

After a round of explanation, we have a general idea of how an ArrayList can add elements. First, it calculates the minimum capacity required for the new element, then determines whether the current elementData array supports the new operation (whether the capacity is sufficient), and triggers the expansion mechanism when the capacity is insufficient. Copy the elements of the original array to the new array, and append new elements later.

Let’s take a look at the methods for the remaining additions

public void add(int index, E element)

AbstractList public void add(int index, E Element) ¶ Public void add(int index, E element) ¶

The source code is as follows:

/** * add element element * at index@param index
  * @param element
  */
public void add(int index, E element) {
    // Verify parameter validity
    rangeCheckForAdd(index);
    // Ensure that the capacity is available - if not, the capacity expansion mechanism will be triggered
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // All elements after the index position are moved one bit back
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // Add element at the specified location
    elementData[index] = element;
    // size + 1
    size++;
}

/** * Parameter validity verification * index > size This parameter is not allowed. Only existing indexes can be added */
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0) {
        throw newIndexOutOfBoundsException(outOfBoundsMsg(index)); }}Copy the code

EnsureCapacityInternal is used to ensure that the array size is sufficient for this new operation. The system.arrayCopy () method may need additional explanation.

Arraycopy (Object SRC, int scrPos, Object desc, int destPos, int Length), which is used to move elements in the specified source array from the specified position to the specified position in the target array

SRC: source array
SrcPos: the starting location of source array replication
Desc: Target array
DescPos: the starting position of the target array to fill data
Length: Number of elements to copy from the source array

Such as:

Int [] arr1 = {1,2,3,4,5,6,7,8,9,0};
Int [] arr2 = new int[4];
// Copy the data from the second position into the target array
System.arrayCopy(arr1, 1, arr2, 0.4);
Copy the code

public boolean addAll(Collection<? extends E> c)

public boolean addAll(Collection
c) extends from AbstractCollection abstract classes by adding elements sequentially after an array. If multiple elements are to be added, you are advised to use this method instead of adding each element one by one to avoid performance degradation caused by multiple capacity expansion.

The source code is as follows:

/** * add multiple elements to the end of the array *@paramC set c star@return boolean
  */
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    // Make sure the array is large enough for this element addition operation, just like adding a single element; Except instead of + 1, the size is + C. length
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // Copy the array
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    returnnumNew ! =0;
}
Copy the code

The code is relatively simple, similar to add(E E), but instead of adding one element, you add multiple elements

public boolean addAll(int index, Collection<? extends E> c)

public boolean addAll(int index, Collection
c) method extends from the AbstractList abstract class to add multiple elements at the specified index position

/** * add multiple elements c * at the specified index position@param index
  * @param c
  * @return boolean
  */
public boolean addAll(int index, Collection<? extends E> c) {
    // Check the validity of the index parameter
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    // Ensure that the data capacity meets the requirements of this operation - if not, expand the capacity
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // Move the element after index back by numNew
    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
    // Fill the free space with the elements to be added
    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    returnnumNew ! =0;
}

Copy the code

The code is relatively simple, first of all, or the capacity of the first reachable operation, so that the capacity of the array to meet the expansion operation; The second reason is that multiple elements need to be added to the index position, so all elements after the index position should be postponed by C. Length.

Remove elements

There are four methods to delete elements, as follows:

Public E remove(int index) Removes the element at the specified position and returns the original element at that position.
Public Boolean remove(Object o) Removes the first element whose value is O and returns whether the removal was successful.
Protected void removeRange(int fromIndex, int toIndex) removes multiple elements from [fromIndex, int toIndex].
public boolean removeAll(Collection
c) Remove specified elements in batches.

public E remove(int index)

Public E remove(int index) extends AbstractList abstract class AbstractList to remove elements at a specified location and return the original element at that location.

The source code is as follows:

/** * removes the element at position index and returns the element *@param index
  * @return E
  */
public E remove(int index) {
    // index validity check, if not, throw related exception
    rangeCheck(index);
    // The number of times the array is changed + 1.
    modCount++;
    Return (E) elementData[index] return (E) elementData[index]
    E oldValue = elementData(index);

    // ArrayList is not particularly suitable for deletion scenarios
    // The number of elements to move
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    // Set the last position of the array to NULL to help the GC
    // This operation is equivalent to elementData[size] = null; size --;
    // It is not recommended to write this in the development, because the emMM code should be readable
    elementData[--size] = null;

    return oldValue;
}

private void rangeCheck(int index) {
    // index validity check
    if (index >= size) {
        throw newIndexOutOfBoundsException(outOfBoundsMsg(index)); }}Copy the code

The code is relatively simple and easy to read, all related to the index of the first is the constant parameter validity check, and then obtain the index of the corresponding index element; Move the element after index forward, and finally return the value of the deleted element.

Note that deletion of an ArrayList is accompanied by a movement of array elements (unless you delete the last element each time, forget it), and that movement is a performance drain. So you can also see that ArrayList is not very well suited for scenarios where deletion is particularly frequent.

public boolean remove(Object o)

Public Boolean remove(Object O) ¶ Public Boolean remove(Object O) extends from AbstractCollection abstract classes.

The source code is as follows:

/** * removes the first element * with o@param o
* @return  boolean
*/
public boolean remove(Object o) {
    if (o == null) {
        // Iterate through the elementData array to find the index of the first O element and call the fastRemove method to delete it
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                // The actual method to perform the delete operation
                fastRemove(index);
                return true; }}else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true; }}return false;
}

/** * The number of operations + 1 * index elements move forward */
private void fastRemove(int index) {
    // Number of array operations + 1
    modCount++;
    // The number of elements to be migrated
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        // Move the element forward to fill in the index bit
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    }
    // Clear the last position to null for subsequent GC
    // elementData[size] = null; size --;
    elementData[--size] = null;
}
Copy the code

The first step is to iterate through the elementData array, find the first matching O element, return its subscript, and call fastRemove(int index) to delete it.

Note that ArrayList supports null-added elements.

protected void removeRange(int fromIndex, int toIndex)

Protected void removeRange(int fromIndex, int toIndex) extends AbstractList abstract class fromIndex, int toIndex Note that elements in the toIndex position are not included.

The source code is as follows:

 /** * Removes the element * in the fromIndex, toIndex range@paramFromIndex including *@paramToIndex does not include */
protected void removeRange(int fromIndex, int toIndex) {
    // Number of operations + 1
    modCount++;

    // All elements after toIndex need to be moved to the front
    int numMoved = size - toIndex;
    // So you can see why the right-hand side is), because it does not have + 1
    System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);

    // Calculates the new array length
    int newSize = size - (toIndex - fromIndex);
    // After the array is moved forward, all subsequent free positions are set to NULL
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    // Update the new length
    size = newSize;
}
Copy the code

The code is relatively simple, and we can see from the source why the right-hand toIndex is not included, because the second argument to the ArrayCopy method starts with toIndex and does not have + 1; The following code is relatively simple and can be read directly in the comments.

public boolean removeAll(Collection<? > c)

public boolean removeAll(Collection
c) method, derived from AbstractCollection abstract class, to batch delete specified elements.

The source code is as follows:

/** * Delete specified elements * in batches@param c
  * @return boolean
  */
@Override
public boolean removeAll(Collection
        c) {
    // set c to determine the operation
    Objects.requireNonNull(c);
    // Call the actual delete method (which shares logic with retainAll, depending on whether the value of parameter 2: Complement is false or true)
    return batchRemove(c, false);
}

/** * The actual delete method * batch remove operation *@paramComplement information. This method is used in removeAll and retainAll. This field is used to check whether "remove" or "retain" is valid when complement is false, and to delete when complement is true. To preserve */
private boolean batchRemove(Collection<? > c,boolean complement) {
    // Define a reference variable to point to elementData
    final Object[] elementData = this.elementData;
    // r is the simple traversal argument, w is the index argument to repopulate the array elements
    int r = 0, w = 0;
    // Whether to modify
    boolean modified = false;
    try {
        for (; r < size; r++) {
            // removeAll is false and retainAll is true
            // if I'm trying to drop taintains (elementData[r]) == true, I don't want it to be assigned to the array.
            // So it is set to false; And their relative positions don't change
            if (c.contains(elementData[r]) == complement) {
                // Place the new element from scratch
                // elementData[w] = elementData[r]; w++;elementData[w++] = elementData[r]; }}}finally {
        // When will it enter here? An exception occurred during a try
        if(r ! = size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; }// If w is different from size, it is removeAll
        if(w ! = size) {// Empty the array of useless index elements to help the GC
            for (int i = w; i < size; i++) {
                elementData[i] = null;
            }
            modCount += size - w;
            size = w;
            modified = true; }}return modified;
}

Copy the code

The code may look a bit long, but the logic is relatively clear, you friends look at the code comments should not be a problem ~~

Delete the operation of the source code explained here, generally speaking, or relatively simple; The main process is basically:

Find the index of the element to be deleted and delete it.
Elements after index are moved forward and variables such as size are updated.

Look for the element

Public int indexOf(Object O); public int indexOf(Object O);

/** * finds the first position * for the specified element o@paramO The element being searched *@returnInt If index does not exist returns -1 */
@Override
public int indexOf(Object o) {
    // ArrayList supports null values
    if (o == null) {
        for (int i = 0; i < size; i++) {
            if (elementData[i]==null) {
                returni; }}}else {
        for (int i = 0; i < size; i++) {
            if (o.equals(elementData[i])) {
                returni; }}}// Returns -1 if it does not exist
    return -1;
}

Copy the code

The code is not too hard to say, but simply iterating through the array of matched elements returns the index, with an extra note: ArrayList supports storing null values.

You may also use the lastIndexOf(Object O) method to find the position of the last specified element. The code is similar, but it starts at the back of the array

/** * finds the last subscript position * of the specified element@param o
  * @returnInt subscript position, returns -1 */ if none exists
@Override
public int lastIndexOf(Object o) {
    // The last occurrence of the index of the element o, it is simple to iterate over the first occurrence ~~
    if (o == null) {
        for (int i = size-1; i >= 0; i--) {
            if (elementData[i]==null) {
                returni; }}}else {
        for (int i = size-1; i >= 0; i--) {
            if (o.equals(elementData[i])) {
                returni; }}}// Returns -1 if it does not exist
    return -1;
}
Copy the code

Convert to an array

There are two methods to convert to an array, as follows:

Public Object[] toArray() converts an ArrayList to an Object[] array
Public

T[] toArray(T[] a) converts ArrayList to an array of the specified T generics

The source code for both is as follows:

/** * Convert ArrayList to an array of type Object *@return Object[]
  */
@Override
public Object[] toArray() {
    // Return Object[]; Converting to an array exposes the underlying elementData of an ArrayList
    return Arrays.copyOf(elementData, size);
}


public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}
Copy the code

We’re calling toArray (), may encounter abnormal Java. Lang. ClassCastException; This is because the toArray() method returns type Obejct[], which might throw an exception if we cast it to another type. This is because Java does not support downward conversions, so when we need to convert an ArrayList to an array and specify the type, we should use the following method.

In a real world, we’d prefer to return arrays that specify generics, so let’s take a look at how public

T[] toArray(T[] a) works and see what we need to look out for.

/** * Convert ArrayList to array * of the specified generics@param a
  * @return T[]
  */
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    If the array passed is smaller than size, copy a new array and return it
    if (a.length < size) {
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    }
    // "2" otherwise just copy the array
    System.arraycopy(elementData, 0, a, 0, size);
    // What is the purpose of this? I didn't get it
    if (a.length > size) {
        a[size] = null;
    }
    A = list.toarray (a); a = list.toarray (a); To use the
    return a;
}
Copy the code

We can see that when the length of array A passed in is less than the length of the elements in the ArrayList collection, the copy generates a new array. Otherwise copy elementData into the A array.

Considering that a new array may be returned at <1>, so even <2> returns an array of A; It is best to use a = list.toarray (a).

Other common methods

Other, more common methods, For example, determine whether the set contains an element contains(Object O) method, get the element at the specified position get(int index), set the element at the specified position set(int index, E element), clear the array clear(), and a more interesting but less common way to create subList(int fromIndex, int toIndex)

Because it is relatively simple, one time (IP man: I want one dozen ten!!)

/** * If contains contains element O *, we can see that the contains method relies on indexOf *@param o
  * @return boolean
  */
@Override
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

/** * gets the element * with the specified index bit@param index
  * @return E
  */
@Override
public E get(int index) {
    // Check parameters
    rangeCheck(index);

    // return elementData[index]; Don't get pressure ~
    return elementData(index);
}

/** * Sets the element at the specified index position and returns the value of the old element at the index position * and the value of the old element (equivalent to replacement) *@param index
  * @param element
  * @return E
  */
@Override
public E set(int index, E element) {
    // Check parameters
    rangeCheck(index);
    // Simple operation of data ~~
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}


/** * Clear the collection */
@Override
public void clear(a) {
    // The number of operations on the array is + 1
    modCount++;
    // Iterate through the number group, set all to null, and update the size value
    for (int i = 0; i < size; i++) {
        elementData[i] = null;
    }

    size = 0;
}


 /** * create subarray * note: SubList is not a read-only array, but an array that shares the same elementData as the parent array. In other words, operations on subList affect the parent array * it's just fromIndex and toIndex that limit what can be viewed *@paramFromIndex start subscript *@paramToIndex ending subscript * is a [fromIndex, toIndex) effect */
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this.0, fromIndex, toIndex);
}
Copy the code

Discussion on traversal mode

ArrayList supports three traversal methods, which are discussed below:

throughInteratorIterator traversal

Integer value = null;
Iterator it = list.iterator();
while (it.hasNext()) {
    value = (Integer)it.next();
}
Copy the code

Random access, traversal by index value, becauseArrayListTo achieve theRandomAccessInterface, so it supports random access to elements by index values

Integer value = null;
int size = list.size();
for (int i = 0; i < size; i++) {
    value = (Integer)list.get(i);
}
Copy the code

The for loop iterates


Integer value = null;
for (Integer integ : list) {
    value = integ;
}
Copy the code

The test compares the efficiency of the three, and obtains the traversalArrayListIs most efficient using random access (that is, access by index) and least efficient using iterators

conclusion

This article focuses on the properties, constructors, and core methods of ArrayList.

An ArrayList has only two attributes, elementData to store elements and size to store the number of elements.

An ArrayList has three constructors, Public ArrayList(), public ArrayList(int initialCapacity), ArrayList(Collection
c); Note that the no-argument constructor first initializes to 0 and only expands to 10 on the first addition of elements.

Core methods mainly introduced several categories, respectively: new elements, delete elements, query elements, and some common methods.

When adding an element, the ArrayList is a dynamic array that supports dynamic expansion. Therefore, when adding an element, it will ensure whether the remaining capacity of the array supports the operation of adding an element. If the remaining capacity does not meet the requirement, the expansion mechanism will be triggered.

We can see from the source code related to the deletion of elements that The ArrayList is accompanied by a large number of operations to move elements every time, so we can see that the ArrayList is not so suitable for the scene of frequent addition and deletion.

Query elements and some of the more common methods, the code is relatively simple; I believe my friends can read it directly.

Another thing to note: We in converting ArrayList into an array, calling toArray () method may throw an exception. Java lang. ClassCastException, this is because the method return type is the Object [], does not support down conversion type, So when we need to return an array of specified generics, we can use the T[] toArray(T[] a) method.

The last thing to note is that ArrayLists support null storage.

An overview of the

The class diagram

The source code parsing

attribute

A constructor

1. ArrayList(int initialCapacity)

2. ArryaList()

3. ArrayList(Collection<? extends E> c)

The new element

public boolean add(E e)

public void add(int index, E element)

public boolean addAll(Collection<? extends E> c)

public boolean addAll(int index, Collection<? extends E> c)

Remove elements

public E remove(int index)

public boolean remove(Object o)

protected void removeRange(int fromIndex, int toIndex)

public boolean removeAll(Collection<? > c)

Look for the element

Convert to an array

Other common methods

Discussion on traversal mode

conclusion

Related Posts

How does Apache Pulsar challenge Kafka?

Java functional programming and Lambda expressions

Validation is used in SpringBoot