ArrayList source code interpretation

ArrayList class top comment:

List interface size variable array implementation. All optional list operations are implemented and all elements, including NULL, are allowed. In addition to implementing the List interface, this class also provides methods to manipulate the size of the array internally used to store the List. (This class is roughly equivalent to the Vector class, except that it is not synchronized.)

Size, isEmpty, get, set, iterator, and listIterator operations all run at a fixed time. The Add operation runs in apportioned fixed time, that is, it takes O(n) time to add n elements. All other operations run in linear time (roughly speaking). This implementation has a lower constant factor than the one used for the LinkedList implementation.

Each ArrayList instance has one capacity. This capacity refers to the size of the array used to store list elements. It is always at least equal to the size of the list. As you add more elements to an ArrayList, its capacity automatically grows. The details of the growth strategy are not specified because it is not as simple as adding elements to share fixed time costs.

An application can use the ensureCapacity operation to increase the capacity of an ArrayList instance before adding a large number of elements. This reduces the amount of incremental redistribution.

Note that this implementation is not synchronous. If multiple threads access an ArrayList instance simultaneously, and at least one of them structurally modifies the list, it must maintain external synchronization. (Structural modification is any operation that adds or removes one or more elements, or explicitly resizes the underlying array; Simply setting the value of an element is not a structural change. This is typically done by synchronizing objects that naturally encapsulate the list. If there is no such object, you should use the Collections. SynchronizedList method will list the “packaging”. This is best done at creation time to prevent accidental unsynchronized access to the list:

List the List = Collections. SynchronizedList (new ArrayList (…). );

Iterators of this class and listIterator methods return iterators that fail quickly: After creating an iterator, except through the iterator itself remove or add method to modify the list from the structure, or in any way at any time to modify the list, the iterator can throw ConcurrentModificationException. Therefore, in the face of concurrent changes, iterators will soon fail completely, rather than risk arbitrary uncertain behavior at some unspecified time in the future.

Note that the fast failure behavior of iterators cannot be guaranteed because, in general, it is impossible to make any hard guarantees about the occurrence of unsynchronized concurrent changes. Fail fast iterator will do our best to throw ConcurrentModificationException. Therefore, it would be a mistake to write a program that relies on this exception to improve the accuracy of such iterators: the fast failure behavior of iterators should only be used to detect bugs.

This class is a member of the Java Collections Framework.

ArrayList is an implementation of a variable-size array of the List interface. ArrayList allows null elements; The capacity of an ArrayList can grow automatically; ArrayList is not synchronous; Iterators returned by ArrayList’s iterator and listIterator methods are fail-fast.

CAPACITY: CAPACITY; Actual size: size; The underlying data structure of an ArrayList is an array. The element type of an array is Object, which can store all types of data. All of our operations on instances of the ArrayList class are array-based at the bottom.

ArrayList source code analysis

1.1 ArrayList inheritance structure and hierarchy

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

ArrayList: Indicates that ArrayList supports generics.
AbstractList extends AbstractList: extends AbstractList. Why should AbstractList be inherited and AbstractList implemented first? Instead of having ArrayList implement List directly?

A: This is the idea that an interface is full of abstract methods, and an abstract class can have abstract methods and concrete implementation methods. It’s this idea that AbstractList can be used to implement some general methods in an interface, and concrete classes like ArrayList inherit this class. Get some common methods, and then in their own implementation of some unique methods, so that the code is more concise, on the inheritance structure of the bottom class of the common method are extracted, first implemented together, reduce repeated code. So when you see a class with an abstract class on top of it, that’s what it does.
AbstractList implements the List interface: ArrayList’s parent, AbstractList, implements the List interface, so why subclass ArrayList? Josh, the author of the Collection, said he thought it would be useful when he wrote the code, but it didn’t, but because it didn’t have any impact, he left it there until now.
Implements the RandomAccess interface: shows that ArrayList supports fast (usually fixed-time) RandomAccess. In an ArrayList, we can quickly get an element object by its ordinal number, which is called fast random access.
Cloneable interface implemented: With this interface implemented, the object.clone () method can be used.
Serializable: Implements java.io.Serializable: Implements java.io.Serializable: Implements java.io.Serializable: Implements java.io.Serializable: Implements java.io. Simply put, the ability to transfer from a class to a byte stream, and then from a byte stream to the original class.

1.2 Class attributes

// serialize the ID
private static final long serialVersionUID = 8683452581122892189L;

/** * Default initial capacity. Default initialization capacity */
private static final int DEFAULT_CAPACITY = 10;

/** * Shared Empty array instance used for empty instances. * Returns the empty array if the capacity of the ArrayList is 0. * /
private static final Object[] EMPTY_ELEMENTDATA = {};

/** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA To know how much to the inflate when * first element is added. When you create an ArrayList, the amount of data in it is zero. * It differs from EMPTY_ELEMENTDATA in that this array is returned by default, whereas EMPTY_ELEMENTDATA is returned when the user specifies a capacity of 0. * /
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be Expanded to DEFAULT_CAPACITY when the first element is added. * Saves the elements added to the ArrayList. * The capacity of an ArrayList is the length of the array. * If the value is DEFAULTCAPACITY_EMPTY_ELEMENTDATA, the array will expand its value DEFAULT_CAPACITY the first time an element is added to the ArrayList. * is marked transient and will not be serialized when the object is serialized. * /
transient Object[] elementData; // non-private to simplify nested class access

/** * The size of The ArrayList (The number of elements it contains). * The actual size of The ArrayList (The number of elements it contains) defaults to 0 *@serial* /
private int size;
  
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
/** * The maximum capacity assigned to arrays * why subtract 8? * Because some VMS keep some headers in the array, trying to allocate this maximum storage capacity can result in an OutOfMemoryError as the array capacity exceeds the VM limit. * /
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// Note: MAX.VALUE is 0x7ffFFFFf, which is 2147483647 in decimal format, i.e. the maximum length of array is 2147483639;

Copy the code

1.3 Constructors

ArrayList provides three constructors:

(1) ArrayList(int initialCapacity) : Construct an empty ArrayList specifying capacity. This is a parameterized constructor with an initial capacity.

Initialize the array with an initial capacity greater than 0, using the custom capacity size as the size to initialize elementData
With initial capacity equal to 0, the empty array is assigned to elementData
If the initial capacity is less than 0, an exception is thrown

   /** * Constructs an empty list with the specified initial capacity. * Constructs an empty list with the specified initial capacity@paramInitialCapacity The initial capacity of the list *@throwsIllegalArgumentException if the specified initial capacity is negative * Throw an exception */ if the specified initial capacity is negative
    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

ArrayList() : Construct an empty list with an initial capacity of 10. If we create an ArrayList object with no arguments, we use this no-argument constructor to create an ArrayList object.

DEFAULTCAPACITY_EMPTY_ELEMENTDATA is an empty Object[]. Initialize elementData, which is also an Object[] type. An empty Object[] gives the default capacity 10. But we don’t see an array with a capacity of 10, so when is it initialized to an array of 10? The answer is when an element is added (the add method). When the first add is made, elementData will become the default length: 10.

    /** * Constructs an empty list with an initial capacity of ten */ Constructs an empty list with an initial capacity of ten
    public ArrayList(a) {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

Copy the code

(3) ArrayList (Collection <? Extends E> c) : Constructs a list of elements for the specified collection in the order in which they are returned by the iterator for the collection. The second parameter constructor is constructed with a value assigned to its parent Collection object.

Convert the Collection object to an array, and then assign the address of the array to elementData.
If the actual size of the array is equal to 0 (there are no elements in C), assign the empty array EMPTY_ELEMENTDATA to elementData.
If size is greater than 0, the arrays. copy method is executed to copy the contents of the Collection object into elementData.

/** * Constructs a list containing the elements of the specified * collection, In the order they are returned by the collection's * iterator. The elements are sorted in the order they are returned by the iterator of the collection. *@paramC The collection whose elements are to be placed into this list *@throwsNullPointerException if the specified collection is null */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if((size = elementData.length) ! =0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        // Toarray () is implemented differently for each collection, so if it is not of type Object[]. Class, then it needs to be modified using methods from ArrayList.
        if(elementData.getClass() ! = Object[].class)//copyOf(array to copy, length of copy to return, class of copy to return)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA; }}Copy the code

The constructor of an ArrayList does one thing: it initializes the container in which the data is stored, which is essentially an array, called elementData.

1.4 Main Methods

1.4.1 the get () method

/** * Returns the element at the specified position in this list@paramIndex Index of the element to return The index of the element to return *@returnThe element at the specified position in this list the element at the specified position in this list *@throws IndexOutOfBoundsException {@inheritDoc} * /
    public E get(int index) {
        rangeCheck(index);// Out of bounds check
        return elementData(index);// Return the element with index
    }
    /** * Checks if the given index is in range. If not, throws an appropriate * runtime exception. This method does *not* check if the index is * negative: It is always used immediately prior to an array access, * which throws an ArrayIndexOutOfBoundsException if index is negative. Checks whether the specified index is in range. If not, throw a runtime exception. This method does not check if the index is negative. It is always used immediately before the array is accessed. If the index given is index>=size, an out-of-bounds exception */ is thrown
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

   /** * Constructs an IndexOutOfBoundsException detail message. * Of the many possible refactorings of the error handling code, * this "outlining" performs best with both server and client VMs. */
    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    // Positional Access Operations
	// Return the element with index
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

Copy the code

As you can see from the code, since ArrayList is an array at its base, its get method is very simple. It checks if the index is less than 0 or greater than or equal to the actual length of the array. The error message returns the index and the actual length of the array.

1.4.2 the set () method

Make sure that the set position is smaller than the current array length (size) and greater than 0, get the specified position (index) element, then put the specified position (index) element, then put the specified position (index) element, then return the original position (oldValue) element.

Replaces the element at the specified position in this list with * the specified element. * Replace the element in the specified position in the list with the specified element. *@paramIndex Index of the element to replace Index of the element to be replaced *@paramElement Element to be stored at the specified position@returnThe element previously at the specified position (to return the replaced element) *@throws IndexOutOfBoundsException {@inheritDoc} If index>=size is specified, an out-of-bounds exception */ is thrown
public E set(int index, E element) {
	// Check if the index is out of bounds. If the parameter specifies index>=size, an out-of-bounds exception is thrown
    rangeCheck(index);
	// Record the element to be replaced (old value)
    E oldValue = elementData(index);
	// Replace the element (new value)
    elementData[index] = element;
	// Returns the replaced element
    return oldValue;
}
Copy the code

1.4.3 the add () method

(1) add(int index, E element)

** * Inserts the specified element at the specified position in this * List. Shifts the element currently at that position (if any) and * any subsequent elements to the right (adds one to their indices). * Moves the element currently in that position (if any) and any subsequent elements to the right (adding an element to its index). *@param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc} * /
public void add(int index, E element) {
    // Check if the index array is out of bounds
    rangeCheckForAdd(index);
    // Check the list capacity, if not enough, increase the capacity by 1. Note: only add 1 to ensure that resources are not wasted
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // Copy the array. The purpose is to empty the index position and insert an element, and move the element after the index one place
	// Before inserting an element, move all elements after index one bit back
    // arrayCopy (original array, start position in source array, target array, start position in target data, number of array elements to copy)
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
  // Assign the specified index position to element
    elementData[index] = element;
  // Actual capacity +1
    size++;
}

 /** * A version of rangeCheck used by add and addAll. */
 private void rangeCheckForAdd(int index) {
  	if (index > size || index < 0)
       throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 }

Copy the code

*** Array copy method

System.arrayCopy(Object srcArray,int srcPos,Object destArray ,int destPos,int length)

Object srcArray Original array (array to copy)

Int srcPos The starting position of the array to copy (array starts at position 0)

Object destArray Target array

Int destPos Specifies the start position of the destination array

Int length Indicates the length of the original array

Example:

Int [] arr={1,2,3,4,5,6,7,8,9,0}; Int [] targetArr=new int[4]; Operation: after the second position of the original array four copy data to the target array System. ArrayCopy (targetArr arr, 1, 0, targetArr length);

Adds an element at the specified location, that is, inserts an element. Add (int index, E E) requires the element to be moved and then inserted. For example, add element e to index 2 as follows:

(2) Add (E E)

/** * end the specified element to the end of this list@paramE Element to be appended to the element added to this list *@return <tt>true</tt> (as specified by {@link Collection#add})
 */
public boolean add(E e) {
	// Check the list capacity, if not enough, increase the capacity by 1. Note: only add 1 to ensure that resources are not wasted
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // place the element e at size and size++
    elementData[size++] = e;
    return true;
}
// Check the size of the array. If it is not enough, expand it for internal use only
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
	// If elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA, set minCapacity to the maximum value between DEFAULT_CAPACITY and minCapacity. DEFAULT_CAPACITY has previously been defined as the default initialization capacity of 10.
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
// Check the size of the array. If it is not enough, expand it for internal use only
// minCapacity Specifies the minimum desired capacity
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
	// Minimum size > current size of array buffer
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);/ / capacity
}
Copy the code

The add method adds an element to the end of the list.

Size is the number of data in the array, because we need to add an element, so size+1, first check whether the array of size+1 can fit. The calculateCapacity method is used to calculate the capacity. Check whether the initialized elementData is an empty array. If it is an empty array size is 0, otherwise it is not 0.

If the elementData element is empty, it is the first element to be added. MinCapacity =size+1, which is equal to 1. The empty array cannot hold any length, so change minCapacity to 10, which is the default size. The minimum capacity required for the elementData array is now 10, so minCapacity in the ensureExplicitCapacity() method is 10. All I’m saying here is that the elementData array needs to be at least 10, and I haven’t changed the size of elementData yet.
If the elements in the elementData array are not empty, then the minimum capacity it needs at this point is the original array length plus 1. MinCapacity represents the actual number of elementData elements that have been added.
Always remember that minCapacity = size+1, in the ensureExplicitCapacity() method, the operand increments by 1 and then compares the minimum required space capacity to the actual current length of the array:
- If the element in elementData is empty, it now needs a capacity of 10, but elementData.length is 0, so it needs to be expanded.
- If the element in the elementData array is not empty, it needs to be expanded if it needs to add an element that is larger than the size of the original array, otherwise it does not need to be expanded.

The key way ArrayList can automatically expand the size is in the following grow() method:

    /** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum Capacity argument. * To ensure that the ArrayList can store at least minCapacity elements * For the first capacity expansion, the logic is newCapacity = oldCapacity + (oldCapacity >> 1). That is, on the basis of the original capacity increased by half. If the capacity is still smaller than minCapacity after the first expansion, expand the capacity to minCapacity. *@param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
		// Get the capacity of the current array
        int oldCapacity = elementData.length;
		/ / expansion. New capacity = Current capacity + Current capacity /2. Increase the current capacity by half (current capacity by 1.5 times).
        int newCapacity = oldCapacity + (oldCapacity >> 1);
		// If the capacity is still smaller than the desired minimum capacity
        if (newCapacity - minCapacity < 0)
			// Expand the capacity to the desired minimum capacity
            newCapacity = minCapacity;
//elementData is empty, length=0, oldCapacity=0, newCapacity=0, in this case the actual initialization elementData size is 10.
		// If the capacity after expansion exceeds the threshold, the system allocates large capacity
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        // The new size is determined, copy the array, change the size.
        //copyof(old array, new array length)
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
	// Perform bulk allocation
    private static int hugeCapacity(int minCapacity) {
		// If minCapacity<0, throw an exception
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
		// If the desired capacity is greater than MAX_ARRAY_SIZE, integer. MAX_VALUE is allocated, otherwise MAX_ARRAY_SIZE is allocated
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

Copy the code

If the array is empty, the capacity of the array becomes 10. If the array is not empty, the capacity of the array becomes 1.5 times as large. If the capacity is larger than the capacity allocated to the ArrayList, determine whether the required capacity is larger than the capacity allocated to the ArrayList. If yes, assign integer. MAX_VALUE:2147483647 to minCapacity; if no, use MAX_ARRAY_SIZE: 2147483639.

The call process is as follows:

The program calls Add, which might call Grow if it needs to expand, and grow might call hugeCapacity. As shown below (capacity expansion) :

List<Integer> lists =newArrayList < Integer > (); lists.add(8);
Copy the code

Initialize the empty argument constructor of ArrayList() with lists size 0, so when calling the list.add (8) method, the steps are as follows:

We can see that we start elementData = {}; The add method is called and continues until grow, where elementData becomes 10, after which it returns to the add function and places 8 in elementData[0]. Example 2 (without capacity expansion):

List<Integer> lists = new ArrayList<Integer>(6); lists.add(8);
Copy the code

InitialCapacity = 6, elementData = new Object[6], elementData is initialized as an Object array of size 6. When add(8) is called, The specific steps are as follows:ElementData is already 6 in size before the add method is called, and will be passed without expansion.

1.4.4 the remove () method

(1) Remove the element at the specified position according to the index remove

/** * Removes the element at the specified position in this list. * Shifts any subsequent elements to the left (Subtracts one from their * indices). * Delete the subtracts one from their * indices (subtracts one from their * indices)@paramIndex The index of the element to be removed *@returnThe element that was removed from the list *@throws IndexOutOfBoundsException {@inheritDoc} If index>=size is specified, an out-of-bounds exception */ is thrown
public E remove(int index) {
	// Check if the index is out of bounds. If the parameter specifies index>=size, an out-of-bounds exception is thrown
    rangeCheck(index);
	// Number of structural changes +1
    modCount++;
	// Record the element at the index
    E oldValue = elementData(index);
	// The number of elements to move to the left after the specified element is deleted
    int numMoved = size - index - 1;
	// If there is an element that needs to be moved to the left, move it (after moving, the deleted element has been overwritten)
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
 	// subtract one from size and set the element at index size-1 to null. In order for GC to work, null must be explicitly assigned to the last position
 	elementData[--size] = null; // clear to let GC do its work
	// Returns the deleted element
    return oldValue;
}	
Copy the code

Here we can see the steps for deleting elements by index:

Conduct border crossing checks
Log the number of changes (modCount can be used to detect a sign of rapid failure.)
Find the element to delete by index
Calculate the number of bits to move
Move the element (actually overwriting the element to be deleted)
Assign the position on -size to null to allow gc to collect it faster.
Returns the deleted element

(2) According to the object remove

    /** * Removes the first occurrence of the specified element from this list, * if it is present. If the list does not contain the element, it is * unchanged. More formally, removes the element with the lowest index * <tt>i</tt> such that * <tt>(o==null&nbsp; ? &nbsp; get(i)==null&nbsp; :&nbsp; o.equals(get(i)))</tt> * (if such an element exists). Returns <tt>true</tt> if this list * contained the specified Element (or equivalently, if this list * changed as a result of the call). * Removes the first occurrence of the specified element from the list, if it exists. If the list does not contain the element, it remains unchanged. More formally, remove the element with the lowest index... *@param o element to be removed from this list, if present
     * @return <tt>true</tt> if this list contained the specified element
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true; }}else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true; }}return false;
    }

    /* * Private remove method that skips bounds checking and does not * return the value removed. A private remove method that skips bounds checking and does not return deleted values. * /
    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        if (numMoved > 0)
	// arrayCopy (original array, start position in source array, target array, start position in target data, number of array elements to copy)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

Copy the code

Iterate through all the objects to get the index position of the object, and then call the fastRemove method to perform the remove operation. Locate the index of the element to remove, move the element after index one bit ahead (call the System.Arraycooy implementation), and then empty the last element. The main thing here is that an arrayList can store null values.

(3) removeRange(int fromIndex, int toIndex)

/**
 * Removes from this list all of the elements whose index is between
 * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
 * Shifts any succeeding elements to the left (reduces their index).
 * This call shortens the list by {@code (toIndex - fromIndex)} elements.
 * (If {@codeToIndex ==fromIndex}, this operation has no effect.) * Moves any subsequent elements to the left (reduces their index) * This call goes through {@codeThe (toindex-fromindex)} element shorten the list. * (if {@codeToIndex ==fromIndex}, this operation is invalid. *@throws IndexOutOfBoundsException if {@code fromIndex} or
 *         {@code toIndex} is out of range
 *         ({@code fromIndex < 0 ||
 *          fromIndex >= size() ||
 *          toIndex > size() ||
 *          toIndex < fromIndex})
 */
protected void removeRange(int fromIndex, int toIndex) {
    modCount++;
    int numMoved = size - toIndex;// The number of deleted indexes
    // arrayCopy (original array, start position in source array, target array, start position in target data, number of array elements to copy)
    System.arraycopy(elementData, toIndex, elementData, fromIndex,
                     numMoved);

    // clear to let GC do its work
    int newSize = size - (toIndex-fromIndex);// Length of the new array
    for (int i = newSize; i < size; i++) {
        elementData[i] = null;
    }
    size = newSize;
}
Copy the code

This method removes all elements between fromIndex and toIndex, moves the elements after toIndex (size-toindex) bits, sets the left empty elements to null for garbage collection to reclaim memory, and assigns the size of the new array to size. Jdk11 = jdk11

protected void removeRange(int fromIndex, int toIndex) {
    if (fromIndex > toIndex) {
        throw new IndexOutOfBoundsException(
                outOfBoundsMsg(fromIndex, toIndex));
    }
    modCount++;
    shiftTailOverGap(elementData, fromIndex, toIndex);
}

private void shiftTailOverGap(Object[] es, int lo, int hi) {
    System.arraycopy(es, hi, es, lo, size - hi);
    for (int to = size, i = (size -= hi - lo); i < to; i++)
        es[i] = null;
}
Copy the code

(4) removeAll(Collection C) and retainAll(Collection C)

public boolean removeAll(Collection
        c) {
	// Remove all elements from the specified collection
    return batchRemove(c, false.0, size);
}

public boolean retainAll(Collection
        c) {
	// Check whether two sets have an intersection
    return batchRemove(c, true.0, size);
}

boolean batchRemove(Collection<? > c,boolean complement, final int from, final int end) {
	Objects.requireNonNull(c);// Non-null check
	final Object[] es = elementData;/ / the original collection
	int r;
	// Optimize for initial run of survivors
	for (r = from;; r++) {// From = 0, end = size
		if (r == end)
			return false;
	// Check whether c contains the current element from the original set
		if(c.contains(es[r]) ! = complement)// If it does, the loop is broken
			break;
	}
	int w = r++;/ / w equal to zero
	try {
		for (Object e; r < end; r++)/ / r is equal to 1
		// Check whether c contains the current element from the original set
			if (c.contains(e = es[r]) == complement)
				// If yes, save it directly
				es[w++] = e;
	} catch (Throwable ex) {// If C. containes () throws an exception
		// Preserve behavioral compatibility with AbstractCollection,even if c.contains() throws.
		// Copy the remaining elements and assign the remaining elements to the original collection
		System.arraycopy(es, r, es, w, end - r);
		W is the length of the current collection
		w += end - r;
		throw ex;
	} finally {
		modCount += end - w;
	When removeAll() is removed, w is always 0, just as clear is always null. / / retainAll () : No intersection returns true, overlap, but not all pay returns true, the two collections are equal, returns false, so can't according to the return value to confirm whether there is overlap between two sets, but by the original collection of judging whether the size of the change, if there are elements in the original collection, represents a intersection, and yuan set has no elements, Indicates that the two sets do not intersect.
		shiftTailOverGap(es, w, end);
	}
	return true;
}

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    return indexOfRange(o, 0, size);
}

int indexOfRange(Object o, int start, int end) {
	// Start = 0 and end = size
    Object[] es = elementData;
    if (o == null) {
        for (int i = start; i < end; i++) {
            if (es[i] == null) {
                returni; }}}else {
        for (int i = start; i < end; i++) {
            if (o.equals(es[i])) {
                returni; }}}return -1;
}
// Remove the core operation of the element
private void shiftTailOverGap(Object[] es, int lo, int hi) {
	// arrayCopy (original array, start position in source array, target array, start position in target data, number of array elements to copy)
    System.arraycopy(es, hi, es, lo, size - hi);
    for (int to = size, i = (size -= hi - lo); i < to; i++)
        es[i] = null;
}
Copy the code

1, Boolean retainAll (Collection
c) Retain only those elements from this collection that are also included in the specified collection (optional operation). In other words, remove all elements in this collection that are not included in the specified collection. List. RetainAll (list2): false if list=list2; (2) List returns false when included in list2; (3) Other return values are true. Understanding: Return false if the size of the collection array A has not changed. False is also returned if sets A and B are identical sets. Returns true even if two collections do not intersect. Return True when set A changes size, False when set A does not change size. By judging the size of the set, we can determine whether the intersection exists. You cannot tell by the True and False returned by the method. If all the elements in the list are in the list2, the list will not be removed. If only one element is not in the list2, the list will be removed. That is, list returns true for removal, or false for removal.

1.4.5 indexOf () and lastIndexOf ()

 // Returns the index of the first occurrence of the specified element in this list, or -1 if the list does not contain the element.
public int indexOf(Object o) {
    if (o == null) { // The element is empty
        for (int i = 0; i < size; i++) // Walk through the array, find the first empty element, return the index
            if (elementData[i]==null)
                return i;
    } else { // The element to be searched is not empty
        for (int i = 0; i < size; i++) // Find the first element that is equal to the specified element and return the index
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
 // Returns the index of the last occurrence of the specified element in this list, or -1 if the list does not contain the element.
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
Copy the code

1.4.6 the clear ()

 /** * post all of the elements from this list. The list will remove all elements * be empty after this call returns. */
    public void clear(a) {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }
Copy the code

Second, the summary

1) arrayList can store NULL. 2) An arrayList is essentially an array of elementData. 3) ArrayLists differ from arrays in that they automatically expand in size. The key method is the grow() method. 4) The difference between removeAll(Collection C) and Clear () in arrayList is that removeAll removes a batch of specified elements, while clear removes all elements in arrayList. 5) arrayList is an array in nature, so it is fast in the query of data, but in the insert and delete aspects, the performance of a lot of data has to move to achieve the desired effect. 6) arrayList implements RandomAccess, so it is recommended to use a for loop when iterating through it.

Reprint instructions:

Copyright notice: This article is an original article BY CSDN blogger “Zhou Gong Deche”, in accordance with CC 4.0 BY-SA copyright agreement, please attach the source link of the original and this statement. The original link: blog.csdn.net/u010250240/…

ArrayList source code interpretation

ArrayList source code interpretation

ArrayList source code analysis

1.1 ArrayList inheritance structure and hierarchy

1.2 Class attributes

1.3 Constructors

1.4 Main Methods

1.4.1 the get () method

1.4.2 the set () method

1.4.3 the add () method

1.4.4 the remove () method

1.4.5 indexOf () and lastIndexOf ()

1.4.6 the clear ()

Second, the summary

Related Posts

Springboot2.x uses Redis as the cache

Java base collection HashMap

Since taught the company’s new little sister Tomcat deployment and optimization, little sister look at my eyes are different!