Source code analysis
Key parameters:
| parameter | The name of the | The default value |
|---|---|---|
| DEFAULT_CAPACITY | Capacity is initialized by default | 10 |
| EMPTY_ELEMENTDATA | Collection of default elements | {} |
| DEFAULTCAPACITY_EMPTY_ELEMENTDATA | Construct instance default element collection with no arguments | {} |
| elementData | An array of elements | {} |
| size | Records the number of elements stored in the ArrayList | 0 |
| modCount | Modify the number of times | 0 |
| MAX_ARRAY_SIZE | Maximum array length | Integer.MAX_VALUE – 8 |
Main structural parameter
- Public ArrayList(int initialCapacity) : constructs an empty list with a specified initialCapacity;
- Public ArrayList() : Constructs an empty list with an initial capacity of 10;
- public ArrayList(Collection
c) : Constructs a list of the elements of the specified collection.
Basic method
grow()
// Perform capacity expansion
// Expand the list to accommodate the added elements
// Overflow conscious code
// It also specifies when the capacity should be expanded
private void grow(int minCapacity) {
// The original capacity before the element is added
int oldCapacity = elementData.length;
// Dynamically expand capacity by 1.5 times
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the desired length is not enough after 1.5 times, the desired length can be directly expanded
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);
}
Copy the codetrimToSize()
// Shrink the capacity
// When we need to add a large number of elements to the ArrayList, it grows to a large array. When we don't need so many elements, we delete it. ArrayList does not automatically handle this problem; it provides a method called the trimToSize() method. We can call this method manually to trigger the scaling mechanism for ArrayList. This will free up excess space and improve space utilization.
public void trimToSize(a) {
modCount++;
if (size < elementData.length) {
If size is 0, the array size is set to the size of the element in the current array
elementData = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}Copy the codeindexOf(Object o) And lastIndexOf(Object o)
// Returns the index of the first occurrence of the specified element in this list
// ArrayList can store null values
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
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 codeget(int index)
// Get data for the specified index
public E get(int index) {
If the index parameter exceeds the maximum size of the list, an exception is reported
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the codeset(index, E element)
public E set(int index, E element) {
// Also check if the index is out of bounds
rangeCheck(index);
// Save the old value under the index of the array. Set returns the element that was previously in the index
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
Copy the codeadd()
// There are two ways to add: tail add and index add
// You'll notice that modCount only appears in thread-unsafe classes, such as: ArrayList, HashMap, etc. The main use of an iterator is to assign modCount to the object that calls the iterator at the beginning of the iterator. If, during the iterator traversal, If you find that the modCount of this object is different from the modCount stored in the iterator, throw an exception.
public boolean add(E e) {
ensureCapacityInternal(size + 1); / / modCount increase
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index); // Check if the index is out of bounds
ensureCapacityInternal(size + 1); / / modCount increase
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
Copy the codeRemove ()
// There are also two ways to remove index elements and obj elements
public E remove(int index) {
rangeCheck(index); // The boundary issue
modCount++; // modCount should be incremented by 1
E oldValue = elementData(index); // Save the old value
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;
}
// Remove the first element that matches
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;
}
// Remove steps are decoupled out
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 codeThe writeObject and readObject
// Serialization and deserialization of ArrayList objects
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out the element count and any hidden content
int expectedModCount = modCount;
s.defaultWriteObject();
// Write the size as the capacity compatible with the clone () behavior
s.writeInt(size);
// Write all the elements in the correct order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if(modCount ! = expectedModCount) {throw newConcurrentModificationException(); }}private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read the size and any hidden content
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// Like clone (), arrays are allocated by size, not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read all elements in the correct order.
for (int i=0; i<size; i++) { a[i] = s.readObject(); }}}Copy the code