1. Class definition
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable
Copy the codeYou can see that by definition
- ArrayList is a generic class
- ArrayList inherits the AbstractList abstract class
- ArrayList implements the List interface
- ArrayList implements the RandomAccess interface, which indicates that ArrayList supports RandomAccess. In fact, ArrayList is an array of type Object
- ArrayList implements the Cloneable interface, which means ArrayList supports cloning
- ArrayList implements the java.io.Serializable interface, indicating that ArrayList supports serialization
2. Field attributes
// Serialize the version number
private static final long serialVersionUID = 8683452581122892189L;
// The default capacity is 10
private static final int DEFAULT_CAPACITY = 10;
// Default empty array with capacity 0
private static final Object[] EMPTY_ELEMENTDATA = {};
// Default empty array when initialized, because it is possible to hold no elements
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// DEFAULT_CAPACITY (10) where the data is stored.
// TRANSIENT modifier indicates that serialization is ignored
transient Object[] elementData; // non-private to simplify nested class access
// The length of valid data is not necessarily equal to the length of elementData
private int size;
// Maximum capacity
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// The number of changes inherited from the parent class
protected transient int modCount = 0;
Copy the codeconstructor
// Specifies the capacity constructor
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// If the specified capacity is greater than 0, an array of the specified capacity is created
// Note that the array type is not generic, but Object
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// If the specified capacity is 0, the default EMPTY_ELEMENTDATA is used
this.elementData = EMPTY_ELEMENTDATA;
} else {
If the capacity is less than 0, an exception is thrown
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }}// Constructor with no arguments, initialized with DEFAULTCAPACITY_EMPTY_ELEMENTDATA by default
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// Pass in a collection as the argument's constructor
public ArrayList(Collection<? extends E> c) {
// Convert the collection contents to an array and assign values to elementData
elementData = c.toArray();
// Assign size
if((size = elementData.length) ! =0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
// If the collection passed in is not of type Object, the new array should be copied and assigned to elementData
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
// Assign EMPTY_ELEMENTDATA to elementData if length is 0
this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeYou can see that from above
- An ArrayList can be initialized by passing in a capacity of type int
- ArrayList has constructors that take no arguments by default
- You can pass in a Collection object to initialize an ArrayList
- No passing in capacity DEFAULTCAPACITY_EMPTY_ELEMENTDATA is used as the elementData value by default, and EMPTY_ELEMENTDATA is used as the elementData value for capacity 0
Method 4.
The size method
public int size(a) {
// Return size, indicating that size is the available element length
return size;
}
Copy the codeIsEmpty method
public boolean isEmpty(a) {
// If size equals 0, ArrayList is empty
return size == 0;
}
Copy the codeThe contains method
public boolean contains(Object o) {
// Call indexOf directly. If the value is greater than or equal to 0, it exists
return indexOf(o) >= 0;
}
Copy the codeMethod indexOf
public int indexOf(Object o) {
if (o == null) {
// If null, use == to determine equality
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
// If not empty, use equals to determine whether it is equal
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Copy the code- The lastIndexOf method works the same way as indexOf except that the for loop is incremented and decremented
Clone method
public Object clone(a) {
try {
ArrayList is cloned as a shallow copy. If it is a reference type, only references are copiedArrayList<? > v = (ArrayList<? >)super.clone();
// Assign the value of elementData
v.elementData = Arrays.copyOf(elementData, size);
// Set the modified count to 0
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw newInternalError(e); }}Copy the codeToArray method
public Object[] toArray() {
// Call Array's copyOf method to copy a new Array
return Arrays.copyOf(elementData, size);
}
// Pass in an array of targets
public <T> T[] toArray(T[] a) {
if (a.length < size)
// If the target array is smaller than size, create a new array of size length
// Assign the contents of element to the new array, return the new array
// array.copyof also calls System. Arraycopy
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// If the length of the target array is greater than or equal to size, the contents of elementData are directly assigned to the target array
System.arraycopy(elementData, 0, a, 0, size);
// If the target array is larger than size, set size to null
if (a.length > size)
a[size] = null;
return a;
}
Copy the codeThe get method
public E get(int index) {
// Check if the array subscript is out of bounds
rangeCheck(index);
// Return the value of the destination location
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
Copy the codeSet method
public E set(int index, E element) {
// Check if the array subscript is out of bounds
rangeCheck(index);
// Get the old value
E oldValue = elementData(index);
// Set the new value
elementData[index] = element;
// Return the old value
return oldValue;
}
Copy the codeThe add method
public boolean add(E e) {
// Check the capacity. If the capacity is insufficient, expand the capacity
ensureCapacityInternal(size + 1); // Increments modCount!!
// Assign and add one to the available element statistics
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
// check the validity of subscripts
rangeCheckForAdd(index);
// Check the capacity. If the capacity is insufficient, expand the capacity
ensureCapacityInternal(size + 1); // Increments modCount!!
// Use system. arrayCopy to move the element in the index position back one position to free up the index position
// Poor performance
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// Assign the position of index
elementData[index] = element;
// Add 1 to available element statistics
size++;
}
// Check the capacity. If the capacity is insufficient, expand the capacity
private void ensureCapacityInternal(int minCapacity) {
// If elementData is the default initialized capacity, the default capacity and the passed capacity are used to compare whether to expand
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// Check whether the capacity is expanded
ensureExplicitCapacity(minCapacity);
}
// Check whether the capacity is expanded
private void ensureExplicitCapacity(int minCapacity) {
// Change the number by 1
modCount++;
// If the required capacity is greater than the length of elementData, it needs to be expanded
if (minCapacity - elementData.length > 0)
/ / capacity
grow(minCapacity);
}
// Expansion function, this is the main point
// The capacity is expanded by 1.5 times by default
private void grow(int minCapacity) {
// Get the previous capacity
int oldCapacity = elementData.length;
// The new capacity is 1.5 times longer than the old capacity
//oldCapacity >> 1 equals oldCapacity/2
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the capacity is not enough, replace the new capacity with the incoming capacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// If the new capacity is larger than the maximum capacity that can be set, check the maximum capacity
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Arrays.copyof is used for capacity expansion
elementData = Arrays.copyOf(elementData, newCapacity);
}
// Maximum capacity check
private static int hugeCapacity(int minCapacity) {
// If the capacity exceeds integer. MAX_VALUE, an exception is thrown
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// If the value is greater than the default maximum, integer. MAX_VALUE is returned; otherwise, MAX_ARRAY_SIZE is returned
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
// Check subscript validity
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the codeThe remove method
public E remove(int index) {
// subscript check
rangeCheck(index);
// Modify statistics by 1
modCount++;
// Get the old value
E oldValue = elementData(index);
// To count the number of moves, delete the element after the deleted position is moved forward by one position, and set the last value to NULL
int numMoved = size - index - 1;
// If the number of moves is greater than 0, the last element is removed if it is equal to 0
if (numMoved > 0)
// Move the index+1 position and all subsequent elements forward one bit
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// Set the trailing value to 0 and subtract 1 from the number of available elements
elementData[--size] = null; // clear to let GC do its work
// Return the old value
return oldValue;
}
public boolean remove(Object o) {
if (o == null) {
// If the element is empty, use == to compare
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// Remove if found
fastRemove(index);
return true; }}else {
// The element is not empty. Equals is used to compare the elements
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
// Remove if found
fastRemove(index);
return true; }}// Return true if it exists, false if it does not
return false;
}
private void fastRemove(int index) {
// Modify statistics by 1
modCount++;
// To count the number of moves, delete the element after the deleted position is moved forward by one position, and set the last value to NULL
int numMoved = size - index - 1;
// If the number of moves is greater than 0, the last element is removed if it is equal to 0
if (numMoved > 0)
// Move the index+1 position and all subsequent elements forward one bit
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// Set the trailing value to 0 and subtract 1 from the number of available elements
elementData[--size] = null; // clear to let GC do its work
}
Copy the code- Note: The remove(Object 0) method removes only one element
Clear method
public void clear(a) {
// Modify statistics by 1
modCount++;
// Iterate over and set all elements to null
for (int i = 0; i < size; i++)
elementData[i] = null;
// Set the available elements to 0
size = 0;
}
Copy the codeAddAll method
public boolean addAll(Collection<? extends E> c) {
// Convert the Collection passed to an array
Object[] a = c.toArray();
// Get the converted length
int numNew = a.length;
// Check capacity and expand capacity
ensureCapacityInternal(size + numNew); // Increments modCount
// Append the transformed array contents to elementData using system. arrayCopy
System.arraycopy(a, 0, elementData, size, numNew);
// Recalculate the available element sizes
size += numNew;
// Return true if the converted length is not equal to 0, false otherwise
returnnumNew ! =0;
}
public boolean addAll(int index, Collection<? extends E> c) {
// check subscript validity
rangeCheckForAdd(index);
// Convert the Collection passed to an array
Object[] a = c.toArray();
// Get the converted length
int numNew = a.length;
// Check capacity and expand capacity
ensureCapacityInternal(size + numNew); // Increments modCount
// Count the number of moves
int numMoved = size - index;
if (numMoved > 0)
// Use system. arrayCopy to move the index position and subsequent elements back by numNew bits
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// Copy the contents of a to elementData, starting at index
System.arraycopy(a, 0, elementData, index, numNew);
// Recalculate the available element sizes
size += numNew;
// Return true if the converted length is not equal to 0, false otherwise
returnnumNew ! =0;
}
Copy the codeRemoveAll method
public boolean removeAll (Collection
c) {
// Check the argument. If the argument is empty, throw an exception
Objects.requireNonNull(c);
// Batch remove
return batchRemove(c, false);
}
private boolean batchRemove(Collection<? > c,boolean complement) {
/ / copy elementData
final Object[] elementData = this.elementData;
//r represents the traversal value, w represents the number of conditions
int r = 0, w = 0;
// Whether to modify
boolean modified = false;
try {
/ / traverse elementData
for (; r < size; r++)
// Complement false adds the element to elementData if c does not contain it
if (c.contains(elementData[r]) == complement)
// Add w + 1 to the start of elementData if the conditions are met
elementData[w++] = elementData[r];
} finally {
//r not equal to size means an exception was thrown at position r
C. contains(elementData[r]) == complement
if(r ! = size) {// copy the values after r to w
System.arraycopy(elementData, r,
elementData, w,
size - r);
// add r to size to w
w += size - r;
}
// If w is not equal to size, some of the conditions are met
// set the part after w to null
if(w ! = size) {// clear to let GC do its work
// set the part after w to null
for (int i = w; i < size; i++)
elementData[i] = null;
// Recalculate to modify the statistics
modCount += size - w;
// Recalculate the number of currently available elements
size = w;
// Set to be modified
modified = true; }}return modified;
}
Copy the codeSubList method
public List<E> subList(int fromIndex, int toIndex) {
// check the validity of subscripts
subListRangeCheck(fromIndex, toIndex, size);
// Returns a SubList, a private inner class of ArrayList
return new SubList(this.0, fromIndex, toIndex);
}
Copy the codeThe forEach method
@Override
public void forEach(Consumer<? super E> action) {
// Check if action is empty and throw an exception if it is empty
Objects.requireNonNull(action);
// Copy modCount with final
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
// The for loop calls the accept of the action
ExpectedModCount == expectedModCount Ensures that the ArrayList in the for loop is not modified
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
// If the ArrayList in forEach is modified, throw an exception
if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}Copy the codeRemoveIf method
@Override
public boolean removeIf(Predicate<? super E> filter) {
// Check whether filter is empty
Objects.requireNonNull(filter);
// Initializes the number of removals to 0
int removeCount = 0;
// Use BitSet to save the tabs to be removed
final BitSet removeSet = new BitSet(size);
// Make a copy of modCount and modify it with final to ensure that the ArrayList is not modified externally
final int expectedModCount = modCount;
// Make a copy of size
final int size = this.size;
//for loop traversal
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
// Gets the element of the current traversal position
final E element = (E) elementData[i];
// Determine whether the element meets the deletion criteria
if (filter.test(element)) {
// Record the subscript to removeSet
removeSet.set(i);
// The number of deletions increases by 1removeCount++; }}// Throw an exception if it is modified midway
if(modCount ! = expectedModCount) {throw new ConcurrentModificationException();
}
// Determine if there are elements that meet the deletion criteria
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
// Count the number of new available elements
final int newSize = size - removeCount;
// The use of BitSet is not clear, in this case it is supposed to save the subscript
// The for loop probably copies the undeleted items to the front
// Set everything after newSize to null
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
// Leave the tail element empty. The number of valid elements is only newSize
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
// Count the new valid elements
this.size = newSize;
// Throw an exception if it is modified midway
if(modCount ! = expectedModCount) {throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
Copy the codeReplaceAll method
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
// Check whether operator is null and throw an exception if null
Objects.requireNonNull(operator);
// Make a copy of modCount and modify it with final to ensure that the ArrayList is not modified externally
final int expectedModCount = modCount;
// Make a copy of size
final int size = this.size;
//for loop traversal
for (int i=0; modCount == expectedModCount && i < size; i++) {
// Call operator.apply to operate on each element
elementData[i] = operator.apply((E) elementData[i]);
}
// Throw an exception if modified
if(modCount ! = expectedModCount) {throw new ConcurrentModificationException();
}
// Modify statistics by 1
modCount++;
}
Copy the codeSort method
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
// Make a copy of modCount and modify it with final to ensure that the ArrayList is not modified externally
final int expectedModCount = modCount;
// arrays.sort is called to sort
Arrays.sort((E[]) elementData, 0, size, c);
// Throw an exception if modified
if(modCount ! = expectedModCount) {throw new ConcurrentModificationException();
}
modCount++;
}
Copy the codeThe iterator method
public Iterator<E> iterator(a) {
return new Itr();
}
Copy the code- Itr is an inner class of ArrayList
- Itr class definition
private class Itr implements Iterator<E>
Copy the codeMethod listIterator
public ListIterator<E> listIterator(a) {
return new ListItr(0);
}
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
Copy the code- ListItr is an inner class of ArrayList
- ListItr class definition
private class ListItr extends Itr implements ListIterator<E>
Copy the code