1. ArrayList definition
ArrayList is an array queue, equivalent to a dynamic array. Compared to arrays in Java, its capacity can grow dynamically. It inherits from AbstractList and implements the List, RandomAccess, Cloneable, and Java.io.Serializable interfaces.
ArrayList inherits AbstractList and implements List. It is an array queue, providing related add, delete, modify, traversal and other functions. ArrayList implements the RandmoAccess interface, which provides random access. RandmoAccess is implemented by lists in Java to provide fast access to lists. In an ArrayList, we can quickly get an element object by its sequence number; This is called fast random access. Later, we’ll compare the efficiency of “fast random access” to “access by Iterator” for lists.
ArrayList implements the Cloneable interface, which overwrites the clone() function and can be cloned.
ArrayList implements the Java.io.Serializable interface, which means that ArrayList supports serialization and can be serialized to transport.
Unlike Vector, operations in an ArrayList are not thread-safe! Therefore, ArrayList is recommended only for single-threaded applications, whereas Vector or CopyOnWriteArrayList can be used for multi-threaded applications.
2, ArrayList source analysis
There are three ways to initialize the ArrayList. This is the 1.8.0 source code, which is different from the previous source code, where the initial size is 10 by default, and the 1.8 source code, which is the default size
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Copy the code/** * Specifies an initial capacity constructor ** @param ArrayList initial capacity * @throws IllegalArgumentExceptionifThe specified initial capacity * is negative */ public ArrayList(int initialCapacity) {// If the specified initial capacity is >0, the specified initial capacity will be specifiedif(initialCapacity > 0) { this.elementData = new Object[initialCapacity]; // If the specified value is 0, assign an empty array}else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); }} /** * In this method, the default value is an empty array of DEFAULTCAPACITY_EMPTY_ELEMENTDATA. This array is distinguished from EMPTY_ELEMENTDATA and is used to determine how much */ public to add when the first element is addedArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * construct a list containing the specified elements, * * @param c The Collection whose elements are to be placed into this list * @throws NullPointerExceptionif the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if((size = elementData.length) ! = 0) {// Copy into the current array if the collection is not emptyif(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else{// Replace this. ElementData = EMPTY_ELEMENTDATA with the default empty array if the data passed in is empty; }}Copy the code##3, add, delete, modify and check
The add method
Public Boolean add(E E) {ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e;return true;
}
Copy the codeThe ADD method is divided into two steps,
EnsureCapacityInternal (size + 1)) + assign (elementData[size++] = e)
As you can see from the code, when adding data, we first determine whether the underlying array DEFAULTCAPACITY_EMPTY_ELEMENTDATA is assigned in the constructor ArrayList(). Select * from EMPTY_ELEMENTDATA where EMPTY_ELEMENTDATA = 10; select * from EMPTY_ELEMENTDATA where EMPTY_ELEMENTDATA = 10; select * from EMPTY_ELEMENTDATA where EMPTY_ELEMENTDATA = 10; 1. No space will be directly opened up during initialization. 2. Efficiency has a certain improvement, the design is more clever
Private void ensureCapacityInternal(int minCapacity) {private void ensureCapacityInternal(int minCapacity) {private void ensureCapacityInternal(int minCapacity) {private void ensureCapacityInternal(int minCapacity) {private void ensureCapacityInternal(int minCapacity) { Otherwise, the default capacity is usedif(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } // Specify capacity. EnsureExplicitCapacity (minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // If the requested minimum size is larger than the array length, an expansion is performed to store all the dataif(minCapacity - elementData.length > 0) grow(minCapacity); } // Add capacity, Private void grow(int mincapacity) {// overflow-conscious code int oldCapacity = elementData.length; Int newCapacity = oldCapacity + (oldCapacity >> 1); 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); }Copy the code####add’s other methods can be clearly seen from the source code, which is very similar to add (E E), except when copying data
public void add(int index, E element) {
if(index > size || index < 0) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); ensureCapacityInternal(size + 1); // Increments modCount!! // The difference between add (E E) and add (E E) is only one line of code. After the expansion, the old data will be moved back one bit from the specified position (index). Arraycopy (elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } public Boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; EnsureCapacityInternal (size + numNew); System. arrayCopy (a, 0, elementData, size, numNew); size += numNew;returnnumNew ! = 0; }Copy the codeRemove method
Remove (int index) Remove (Object O) ¶ Remove (int index) remove(Object O) ¶ Remove (int index) remove(Object O)
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
E oldValue = (E) 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;
}
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;
}
Copy the codeGet (int index)
The bottom layer of an ArrayList is an array, so the search is very simple, finding the data directly by the array index
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
Copy the codeSet (int index, E element)
The change is also very simple, changing the data directly according to the array index
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
Copy the codeAdd, delete, modify and check the summary
From the above source code can be clearly seen, ArrayList add, delete, and check operation is essentially the underlying array operation, when added, need to expand the array +copy operation, delete also need to copy the array, so ArrayList increase and delete efficiency will be very low, but relatively, Benefited from the bottom of the array as a result, in the search and change operation, can according to subscript directly, only the complexity of O (1), so the demand for find more frequently, you can use the ArrayList, greatly increase the operational efficiency, but at the time of creating more frequently, will need to consider other data structures; For example, if you already know the size of the current data, you can use the ArrayList(int initialCapacity) constructor to specify the initialCapacity of the data. This will prevent the performance of the data from being added frequently. At the same time, space waste caused by 1.5 times expansion mechanism can be avoided