1. Data structure of ArrayList
The underlying data structure of ArrayList is an array. The type of array elements is Object type. All operations on ArrayList are based on arrays.
2. Thread safety of ArrayList
The operation of adding elements to ArrayList is carried out in two steps, that is, the first step is to store the elements to be added at the position of object[size]; the second step is to increase the value of size by 1. Since this process is not guaranteed to be atomic in a multi-threaded environment, ArrayList is thread-unsafe in a multi-threaded environment.
Specific examples: In the case of single-threaded operation, if Size = 0, after adding an element, the element will be at position 0, and Size=1; and if it is multi-threaded, for example, there are two threads, thread A First store the element at position 0. But at this time, the CPU schedules thread A to pause, and thread B gets a chance to run. Thread B also adds elements to this ArrayList, because Size is still equal to 0 at this time (note that we assume that adding an element requires two steps, and thread A only completed step 1), so thread B also adds elements to Stored at location 0. Then both thread A and thread B continue to run, both increasing the value of Size. Well, now let’s take a look at the case of ArrayList. There is actually only one element, stored at position 0, but Size is equal to 2. This is “thread unsafe”.
If you have to use ArrayList in a multi-threaded environment, you need to ensure its thread safety. There are usually two solutions: first, use the synchronized keyword; second, you can use the static method synchronizedList() in the Collections class ; Just call ArrayList.
3. Inheritance relationship of ArrayList
ArrayList inherits the AbstractList abstract parent class and implements the List interface (which specifies the operation specifications of List), RandomAccess (random access), Cloneable (copyable), and Serializable (serializable).
4. Main member variables of ArrayList
private static final int DEFAULT_CAPACITY = 10;
When the array length of ArrayList is not explicitly pointed out in the constructor of ArrayList, the default object array capacity size of 10 is used internally in the class.
private static final Object[] EMPTY_ELEMENTDATA = {<!-- -->};
When the constructor of ArrayList indicates that the array length of ArrayList is 0, the empty object array EMPTY_ELEMENTDATA is assigned to the elemetData array inside the class.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {<!-- -->};
When the ArrayList constructor does not explicitly indicate the array length of ArrayList, the default object array is used internally within the class.
DEFAULTCAPACITY_EMPTY_ELEMENTDATA. transient Object[]elemetData;
The underlying data structure of ArrayList is just an array of objects, used to store actual elements, and is marked as transient, which means that this field will not be serialized during serialization.
private int size;
The actual number of elements stored in the ArrayList is 0 elements by default.
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;
The maximum array capacity of the object array in ArrayList is Integer.MAX_VALUE – 8.
public class ArrayListextends AbstractList implements List , RandomAccess, Cloneable, java.io.Serializable { // version number private static final long serialVersionUID = 8683452581122892189L; //Default capacity private static final int DEFAULT_CAPACITY = 10; //empty object array private static final Object[] EMPTY_ELEMENTDATA = {<!-- -->}; //Default empty object array private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {<!-- -->}; // array of elements transient Object[] elementData; // Actual element size, default is 0 private int size; //Maximum array capacity private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; }
5. ArrayList construction method
No-argument constructor
For the parameterless constructor, set the value of the member variable elementData to
DEFAULTCAPACITY_EMPTY_ELEMENTDATA.
public ArrayList() {<!-- -->
// No parameter constructor, set the element array to empty
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
int type parameter constructor
The parameter is the length of the desired ArrayList array, initialCapacity. First, we need to determine the relationship between the parameter initialCapacity and 0:
If initialCapacity is greater than 0, create an object array of size initialCapacity and assign it to elementData.
If initialCapacity is equal to 0, assign EMPTY_ELEMENTDATA to elementData.
If initialCapacity is less than 0, an exception is thrown (illegal capacity).
public ArrayList(int initialCapacity) {<!-- -->
if (initialCapacity > 0) {<!-- --> // Initial capacity is greater than 0
this.elementData = new Object[initialCapacity]; //Initialize element array
} else if (initialCapacity == 0) {<!-- --> // Initial capacity is 0
this.elementData = EMPTY_ELEMENTDATA; // is an empty object array
} else {<!-- --> // The initial capacity is less than 0 and an exception is thrown.
throw new IllegalArgumentException("Illegal Capacity: " +
initialCapacity);
}
}
Collection type constructor
The first step is to convert the collection in the parameter into an array and assign it to elementData;
The second step is whether the parameter set is empty. By comparing size with the array length in the first step.
The third step, if the parameter set is empty, set the element array to be empty, that is, assign EMPTY_ELEMENTDATA to elementData;
Step 4: If the parameter set is not empty, then determine whether the parameter set is successfully converted into an array of Object type. If the conversion to an array of Object type is successful, copy the array and convert it into an array of Object type.
public ArrayList(Collection<? extends E> c) {<!-- --> // Collection parameter constructor
elementData = c.toArray(); // Convert to array
if ((size = elementData.length) != 0) {<!-- --> // The parameter is a non-empty collection
if (elementData.getClass() != Object[].class) // Whether it was successfully converted into an Object type array
elementData = Arrays.copyOf(elementData, size, Object[].class); // If it is not an Object array, copy it
} else {<!-- --> // If the collection size is empty, set the element array to empty
this.elementData = EMPTY_ELEMENTDATA;
}
}
6. Add() method of ArrayList
Three main things are done in the add() method: first, ensure that the elements you want to add to the collection can be added to the collection, that is, ensure the capacity of the ArrayList (to determine whether expansion is needed); then add the elements to the elementData array Specify the position; finally add 1 to the actual number of elements in the collection.
public boolean add(E e) {<!-- --> // Add element
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size + + ] = e;
return true;
}
7. ArrayList expansion mechanism
The expansion of ArrayList mainly occurs when adding elements to the ArrayList collection. From the analysis of the add() method, we can know that before adding, we must ensure that the capacity of the collection can accommodate the added elements. It mainly went through the following stages:
First, call the ensureCapacityInternal(size + 1) method in the add() method to determine the minimum collection capacity minCapacity value of the collection to ensure the success of adding elements. The parameter is size + 1, which means the actual number of elements in the collection if elements are successfully added to the collection. In other words, in order to ensure the success of adding elements to the collection, the minimum capacity of the collection, minCapacity, should be size + 1. In the ensureCapacityInternal method, first determine whether elementData is the default empty array. If so, minCapacity is the larger of minCapacity and the default capacity of the collection.
Second, call the ensureExplicitCapacity(minCapacity) method to determine whether the collection needs to expand the existing element array in order to ensure the success of adding elements. First, add one to the structural modification counter; then determine the size of minCapacity and the length of the current element array. If minCapacity is larger than the length of the current element array, it needs to be expanded and enter the third stage.
Third, if you need to expand the existing element array, call the grow(minCapacity) method. The parameter minCapacity represents the minimum capacity of the collection to ensure the success of adding elements. When expanding, first increase the length of the original element array by 1.5 times (oldCapacity + (oldCapacity >> 1)), and then compare the expanded capacity with minCapacity: ① If the new capacity is less than minCapacity, set the new capacity to minCapacity; ② If the new capacity is greater than minCapacity, specify the new capacity. Finally, the old array is copied to the expanded new array.
private void ensureCapacityInternal(int minCapacity) {<!-- -->
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {<!-- --> // Determine whether the element array is an empty array
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // Take the larger value
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {<!-- -->
// Structural modification plus 1
modCount + + ;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {<!-- -->
int oldCapacity = elementData.length; // old capacity
int newCapacity = oldCapacity + (oldCapacity >> 1); // The new capacity is 1.5 times the old capacity
if (newCapacity - minCapacity < 0) // The new capacity is less than the capacity specified by the parameter, modify the new capacity
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0) // New capacity is greater than maximum capacity
newCapacity = hugeCapacity(minCapacity); // Specify new capacity
//Copy expansion
elementData = Arrays.copyOf(elementData, newCapacity);
}
8. ArrayList’s set(int index,E element) method
The set(int index, E element) method is used to specify the value of the element at the subscript index. In the source code implementation of ArrayList, the method first determines whether the passed element array subscript parameter is legal, then takes out the original value, sets it as a new value, and returns the old value as the return value.
public E set(int index, E element) {<!-- -->
// Check whether the index is legal
rangeCheck(index);
// old value
E oldValue = elementData(index);
//Assign new value
elementData[index] = element;
//return old value
return oldValue;
}
9. ArrayList’s indexOf(Object o) method
The function of the indexOf(Object o) method is to search for an element equal to the specified element from scratch. If found, it returns the subscript of the found element in the element array. If it is not found, it returns -1. Similar to this method is the lastIndexOf(Object o) method, which is used to find elements equal to the specified element starting from the end.
Looking at the source code of this method, we can see that this method is divided into two cases and discussed separately from the perspective of whether the element to be found is empty. This also means that the parameter of this method can be a null element, and it also means that the ArrayList collection can store null elements. The logic implemented by the method is also relatively simple. It directly loops through the element array and uses the equals method to determine whether the objects are the same. If they are the same, the subscript will be returned. If they are not found, -1 will be returned. This also explains why the situation should be divided into two situations to discuss whether the object to be found is empty. Otherwise, calling the equals method on an empty object will generate a null pointer exception.
// Search from the beginning to see if the specified element exists in the array
public int indexOf(Object o) {<!-- -->
if (o == null) {<!-- --> // The element found is empty
for (int i = 0; i < size; i + + ) // Traverse the array, find the first empty element, and return the subscript
if (elementData[i]==null)
return i;
} else {<!-- --> // The element found is not empty
for (int i = 0; i < size; i + + ) // Traverse the array, find the first element equal to the specified element, and return the subscript
if (o.equals(elementData[i]))
return i;
}
// Not found, return empty
return -1;
}
10. ArrayList’s get(int index) method
The get(int index) method returns the value of the element at the specified index. The get function checks whether the index value is legal (only checks whether it is greater than size, but does not check whether it is less than 0). If the result is legal, call the elementData(int index) method to obtain the value. In the elementData(int index) method, the element with the specified subscript in the element array is returned and down-casted.
public E get(int index) {<!-- -->
// Check whether the index is legal
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {<!-- -->
return (E) elementData[index];
}
11. Remove(int index) method of ArrayList
The remove(int index) method is used to delete the element with the specified index. In the source code of this method, all elements from the next digit of the specified subscript to the end of the array are moved forward by one unit, and the last element of the array is set to null. This will make it easier for the entire array to be GCed when it is no longer used. , can be used as a little trick. The number of elements that need to be moved is: size-index-1.
public E remove(int index) {<!-- -->
// Check whether the index is legal
rangeCheck(index);
modCount + + ;
E oldValue = elementData(index);
//The number of elements to be moved
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
// Assignment is empty, which is beneficial to GC
elementData[--size] = null;
//return old value
return oldValue;
}
12. Advantages and Disadvantages of ArrayList
Advantages of ArrayList The bottom layer of ArrayList is implemented as an array, which is a random access mode. In addition, it implements the RandomAccess interface, so the search, that is, the get, is very fast. ArrayList is very convenient when adding an element sequentially. It just adds an element to the array. Traversing elements based on subscripts is highly efficient. Accessing elements based on subscripts is highly efficient. It can automatically expand the capacity, and the default is 1.5 times the original capacity each time. Disadvantages of ArrayList Inserting and deleting elements is not efficient. Finding elements based on element subscripts requires traversing the entire element array, which is not efficient. Not thread safe.