ArrayList is an array-based and resizable implementation class of the List interface that implements all the optional operations of the List specification. This class allows storing elements of all types, including NULL. Size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The Add operation runs within the apportioned constant time, that is, it takes O(n) time to add n elements. Iterators of this class and listIterator methods return iterators that fail fast: If the list structure is modified in any way at any time after the iterator is created, except through the iterator’s own remove or add methods, the iterator will throw an exception.
An overview of the
The following diagram shows the inheritance of ArrayList:
Important inheritance
java.util.ListImplement the List method, follow the List specificationjava.lang.CloneableMarks instances of the class to allow cloningjava.util.RandomAccessFlags interfaces to indicate that the class supports fast (usually constant-time) random access
Member variables
There are some member variables and constants in a class:
// Defines the default initialization capacity
private static final int DEFAULT_CAPACITY = 10;
// Records the number of elements an ArrayList contains
private int size;
// An array of elements. Size is the length of the array
transient Object[] elementData;
// Defines the maximum capacity that the array above can define, but is limited by the VM, so this value is for reference only
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// Construct a shared array for lists of capacity 0
private static final Object[] EMPTY_ELEMENTDATA = {};
// The shared array used when the list is initialized by default
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Copy the codeThere is also an attribute modCount, inherited from AbstractList, that keeps track of how many times the list has been structurally modified, meaning changes that change the size of the list or otherwise disrupt the list so that iterating over the list may produce incorrect results. This field, which is modified when a list is added or deleted, is used in iterator to provide the iterator with fast failure behavior.
The constructor
ArrayList provides three constructors: a no-parameter constructor and one that takes a Collection type parameter follow the specifications of the Collection interface. Another important constructor is to create an empty list specifying an initial capacity.
// Construct an empty list with an initial capacity of 10
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeA no-parameter constructor only internal array initialization, pointing to an empty array constants when add elements to the list for the first time, will determine whether the empty array object, will give the list of initial capacity as the default value is 10, detail in below & expansion mechanism] [add elements (# add elements & expansion mechanism).
// Constructs a list of the specified collection elements in the order returned by the collection iterator
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if((size = elementData.length) ! =0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeThe elements of the specified collection are first converted to a new array and assigned to elementData. Then judge according to the length of the array: if the length is 0, point the array directly to the shared empty array object; If the length is not zero and the array type is not Object[] (according to the documentation, collection.toarray () may incorrectly return a result that is not Object[]), copy the array elements into the correct array type.
// Construct an empty list with the specified initial capacity
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 codeThis constructor accepts initialCapacity initiallist capacity:
- If the argument is greater than 0, the array is initialized with that capacity;
- Argument equal to 0 initializes the array of elements with the shared empty array object;
- Argument less than 0 is invalid and an exception is thrown.
Add elements & expansion mechanism
There are four ways to add elements to an ArrayList: insert elements at the end of the list, insert elements at the specified position, and insert collections at the end of the list, and insert collections at the specified position.
boolean add(E e)
// Appends the specified element to the end of the list
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
Copy the codeThis method is implemented from the List and Collection interfaces and follows their specifications. If the List refuses to add this element, an exception needs to be thrown, otherwise the call will return true on success. This ensures that the List will always contain this element after the call returns.
The third line is to ensure that the list capacity is available before inserting elements, including the expansion mechanism of ArrayList and modification of modCount. We then store the element directly into the elementData array, increasing the size by one; Return true and the call succeeds. The logic of this method is fairly simple, but the key is in the ensureCapacityInternal() method. Here’s the code:
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the codeThis method is called with the minimum capacity required to add a new element, which is then used to calculate the actual capacity required, compatible with the ArrayList created using the default constructor. If it is an empty array constructed with no parameters, the maximum capacity between the default capacity 10 and the minimum capacity is selected as the final capacity. If it is not, the minimum capacity required is minCapacity.
Once the required capacity is known, the expansion operation will be carried out. First, the member variable modCount is incremented to record the number of changes, indicating that the list size has been changed. It then decides to call the actual expansion method when the required capacity is greater than the current length of elementData. The source code comment states that the purpose is to prevent overflow, an intent that needs to be understood further into the grow() method below.
// Increase the capacity to ensure that it can hold at least the number of elements specified by the minimum capacity parameter
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 codeIn the expansion logic, take the current array length, and increase it to 1.5 times the previous size for the new list capacity, and then determine some special cases:
- If the new expanded capacity is smaller than the minimum required, the minimum capacity is used directly;
- If the new expanded capacity is larger than the specified maximum capacity, the maximum capacity is used directly
hugeCapacity(minCapacity);
The hugeCapacity(minCapacity) method returns integer.max_value as the capacity if it is larger than the specified value, but this is also limited by the SIZE specified by the VM at run time, so this value is inaccurate. Once the capacity is determined, the elements are copied directly into the new array, and the expansion is complete.
The other three methods that add elements all call ensureCapacityInternal() to make sure the list capacity is available, so focus on the rest of the code logic.
void add(int index, E element)
// Inserts the specified element at the specified position in this list. Moves the element (if any) currently in that position and any subsequent elements to the right
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
// Scope checking methods for add and addAll
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
Copy the codeThe first step in specifying the insertion position is to verify the validity of the position (array index). If the index is less than 0 or greater than the current number of elements, it is considered invalid and an array out-of-bounds exception is thrown. The next step is to verify that capacity is available.
The important logic is that the insertion position and subsequent elements are moved back to make free space for the elements to be added, using system.arrayCopy () to copy the insertion position and subsequent elements back. Add the element to the index, increasing size by one.
boolean addAll(Collection<? extends E> c)
// Appends all elements of the specified collection to the end of this list in the order returned by the iterators of the specified collection
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
returnnumNew ! =0;
}
Copy the codeThe logic in this method is simple: convert the specified collection to an array and copy it to the original array.
boolean addAll(int index, Collection<? extends E> c)
// Inserts all elements from the specified collection into this list, starting at the specified location. Moves the elements currently in that position (if any) and any subsequent elements to the right (increasing their indexes). The new element will follow the specified collection
The order returned by the iterators of // appears in the list
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
returnnumNew ! =0;
}
Copy the codeThe logic of this method can be thought of as add(int index, E element) and addAll(Collection
c) extends E> c) extends E> c) extends E> c) extends E> c) extends E> c
- When the insertion position is in the middle of the list, the index and subsequent elements need to be moved back, and then the new collection array is copied into the list.
- When the insertion position is at the end of the list, there is no need to move the element, just copy the new collection array to the end of the list array.
List access operation
E get(int index)
// Returns the element at the specified position in this list
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
// Check if the index is in a valid range, only before the list access operation
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
Copy the codeThe index access method is relatively simple, just check to ensure that the index is valid after you can directly access the list array.
E set(int index, E element)
// Replace the element at the specified position in this list with the specified element, and return the old element
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
Copy the codeE remove(int index)
// Remove the element at the specified position in this list. Move any subsequent elements to the left and return the old element
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 codeDeleting an element reduces the size of the list and modifies the structure of the list, so modCount needs to be increased. NumMoved calculates the number of elements that need to be moved, still moving the elements after index by copying them. Finally, null is referred to the last position of the list array so that garbage collection can clean up the unreferenced objects.
boolean remove(Object o)
// Remove the first occurrence of the specified element (if present) from this list. If the list does not contain the element, it remains unchanged
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;
}
// A private delete method that skips index checks and returns no value is called only from above
private void fastRemove(int index) {
modCount++;
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
}
Copy the codeBy specifying element deletion, you need to determine whether the element exists in the list. The specification uses o==null? Get (I)==null: O.quals (GET (I)) is used to confirm that the elements are the same, so it is divided into null and non-null elements for loop comparison. If the same elements exist in the list, the fastRemove method will be executed to delete them.
Other operating
// 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) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
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;
}
Return true if the list contains the specified element. Specifically, if and only if this list contains at least one element e makes
// (o==null ? E ==null: o.dice (e)) returns true
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
Copy the codeThe first two methods of the above code are to find the index by the element, the comparison element is still the document specification o==null? Get (I)==null: get(I)==null: get(I)==null: get(I)==null: get(I)==null: get(I)==null: get(I)= get(I))
The Contains method cleverly uses indexOf to implement. If the element first appears with an index greater than 0, it exists in the list.
// Removes all elements contained in the specified collection from this list
public boolean removeAll(Collection
c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
// Removes all elements from the list that are not included in the specified collection
public boolean retainAll(Collection
c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
private boolean batchRemove(Collection<? > c,boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if(r ! = size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; }if(w ! = size) {// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true; }}return modified;
}
Copy the codeThe above two methods contain the same logic for deleting elements in bulk, but the target elements are different, so the batchRemove logic is differentiated by the Complement identifier:
- The statement
R, wStores the current list array read and write subscripts, and then intryThe code block iterates through the list, moving the elements that need to be left to the front, passingcontains()Decide if you need to stay. - to
finallyIn the code block, whenr ! = size(that is, the above traversal does not end normally, which may be wrong), copy the remaining traversal elements forward to the end of the retained elements, which are regarded as the elements to be retained, and then move W to the end of the retained elements. - Once you’ve identified all the elements you want to keep, all that’s left is to delete the ones you don’t want to keep, which is everything from W to the end of the list. So we iterate over the rest of the index and set it to NULL and modify it
modCountandsizeThe value of the.
Lists are converted to arrays
// Returns an array containing all the elements in this list in the appropriate order (from the first element to the last).
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
// Returns an array containing all elements in this list in the appropriate order (from the first element to the last), allowing the specified array to receive.
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
Copy the codeMethod one returns the list element as an array, which is a “safe” new array that the list itself has no references to, and is therefore free to modify. Array.copyof () also uses the system.arrayCopy () method that appears multiple times in ArrayList.
Method two differs from method one in that it allows you to receive list elements using an existing array object. By looking at the source code, you can see the implementation logic:
- First, when the specified array size is smaller than the list length, and therefore cannot hold all the list elements, a new array is allocated using the specified array runtime type and the list size, and the elements are copied back.
- When an array can hold all the elements of the list, all the elements of the list are copied directly into the specified array.
- As a final step, determine if the array is larger than the number of list elements, that is, if there is still space in the array, assign null to the position after the end of the list element in the array. (This helps determine the length of the list only if it is clear that the list does not contain any empty elements.)
This article mainly introduces the construction logic of ArrayList class and the main method source code, only to the perspective of personal learning and understanding to do a brief analysis of this class. Due to limited space, the rest of the content, including iterators, will be a separate article, stay tuned.
Java container source code learning analysis – ArrayList source code learning (a)