An ArrayList is an implementation of a variable-length array of the List interface that provides the ability to add, modify, delete, iterate, and so on. This article through the source code to analyze the implementation of ArrayList, precautions, use scenarios, etc. (JDK version 1.8).
ArrayList has the following characteristics:
ArrayListBased on the array, can be automatically expanded; However, capacity expansion is time-consuming, so initialization is performedArrayListIt is best to predict the initial capacity;ArrayListAllow insert innullElements;- Because of the implementation
SerializableInterface, rewrittenwriteObject和readObjectMethod, soArrayListSupport serialization and deserialization; ArrayListNot synchronous;ArrayListtheiterator和listIteratorThe iterator returned by the method isfail-fast.
define
First, let’s look at the definition of ArrayList:
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable
Copy the codeYou can see that ArrayList inherits or implements the following classes or interfaces:
AbstractList: inheritedAbstractList.AbstractListprovidesListInterface backbone implementation to minimize implementationListRequired work.List: to achieve theListInterface. All optional list operations are provided.RandomAccess: indicates thatArrayListRandom access is supported.Cloneable: indicates that it can be cloned and overwrittencloneMethods.java.io.Serializable: indicates that the class supports serialization.
Here is the class structure hierarchy of ArrayList:
attribute
The properties of an ArrayList are:
// serialize the ID
private static final long serialVersionUID = 8683452581122892189L;
// The capacity is initialized by default
private static final int DEFAULT_CAPACITY = 10;
// ArrayList returns an empty array if its capacity is 0
private static final Object[] EMPTY_ELEMENTDATA = {};
// The empty array is returned if the default constructor (no arguments constructor) is called
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// An array that stores the current element
transient Object[] elementData;
// The size of the ArrayList (number of elements contained)
private int size;
// The maximum length allocated to the array
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Copy the codeIn addition, there is a modCount attribute inherited from AbstarctList, which represents the number of changes to the ArrayList collection. In traversing the collection, if modCount are changed, will be thrown ConcurrentModificationExceptioin anomalies.
A constructor
In ArrayList, three constructors are provided:
Default constructor
The default constructor that takes no arguments builds an empty list with an initial capacity of 10.
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeSpecify the capacity
This constructor builds an empty ArrayList specifying initialCapacity. If negative initialization capacity is specified, IllegalArgumentException is thrown.
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 codeConstruct an array with the given collection
This method constructs a list of the elements for the specified collection in the order in which the iterator for the collection returns them.
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if((size = elementData.length) ! =0) {
// Determine whether elementData is of type Object[]
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
// Use an empty array instead
this.elementData = EMPTY_ELEMENTDATA; }}Copy the codeYou first convert the elementData passed in to an array, and then copy the elements into the elementData array using the arrays.copyof method.
Basic method
The main methods of ArrayList are as follows:
Get (int index) method
The get method is used to return elements in the list whose index is index.
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
Copy the codeMethod first check index, if the index over the length of the array, will throw IndexOutOfBoundsException anomalies.
Then use the elementData method to get the element:
E elementData(int index) {
return (E) elementData[index];
}
Copy the codeSince the underlying implementation of ArrayList is an array, fetching elements by array subscript, its time complexity is O(1).
The add (E, E) method
The add method is used to add the specified element E to the end of the list.
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
Copy the codeAs you can see, the first is the ensureCapacityInternal(size + 1) method, which checks the array capacity and expands it if it’s not enough 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) {
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 codeThe expansion method grow ensures that at least minCapacity elements can be stored. The implementation is as follows:
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 codeAfter capacity expansion, the capacity can be calculated as follows:
- Used for the first capacity expansion
newCapacity = oldCapacity + (oldCapacity >> 1);Formula, increase the capacity by half; - If the capacity is still less than
minCapacity, expand the capacity tominCapacity; - If the capacity is greater than
MAX_ARRAY_SIZE, expand the capacity toInteger.MAX_VALUE.
Finally, use the arrays.copyof method to copy the elements into the new array.
Add (index, element) method
The add method is used to insert elements at the specified position in the list.
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++;
}
Copy the codeThis method is first to check the position of the specified index, if cross, will be thrown IndexOutOfBoundsException anomalies. Then use the EnrecapacityInternal method to determine the capacity and expand it.
Then, use the system.arrayCopy () method to move the element one bit back after the index position and assign the index position to Element.
Remove (index) method
The remove method is used to remove elements in a list at the index position.
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 codeFirst, use the rangeCheck method to check if the index is out of bounds, and then modify modCount, which increases the number of changes by one. Use the elementData method to get the element at the index position for later return.
Using size-index-1 to calculate the number of bits moved to the left, and using the system.arrayCopy () method to move the element one bit to the left indicates that the element has been deleted. Finally, set the element in position –size to null to prevent the object from drifting and causing the JVM to reclaim it.
The Iterator Iterator
Iterators provide a way to access elements in a collection. The iterator() method in the Array class is used to return an iterator from the container object that points to the beginning of the list.
public Iterator<E> iterator(a) {
return new Itr();
}
Copy the codeThe Itr class is implemented as follows:
private class Itr implements Iterator<E> {
int cursor; // The index of the next element to return
int lastRet = -1; // The index of the last returned element, or -1 if not
int expectedModCount = modCount;
Itr() {}
public boolean hasNext(a) {
returncursor ! = size; }@SuppressWarnings("unchecked")
public E next(a) {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove(a) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}final void checkForComodification(a) {
if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }...}Copy the codeThe main methods of the Itr class are as follows:
next(): Gets the next element in the sequence;hasNext(): Checks if there is another element in the sequence;remove(): Removes the last element returned by the iterator.