Take a look at the source code for ArrayList today
- directory
- introduce
- Inheritance structure
- attribute
- A constructor
- The add method
- The remove method
- Change the method
- Access to elements
- The size () method
- IsEmpty method
- Clear method
- Circular array
1. Introduction
Generally speaking, the beginning of the article should be introduced to say a brief introduction. I’m not going to do it here because if you don’t know what an ArrayList is you don’t have to look at it. I’m going to talk about some common methods
2. Inheritance structure
ArrayList (ArrayList)
The ArrayList inheritance structure is as follows:
-
Serializable interface
-
Cloneable Cloneable Cloneable Cloneable Cloneable Cloneable Cloneable Cloneable Cloneable Cloneable
-
List mainly defines some method implementations
-
RandomAccess is also a tag class, and implementing RandomAccess means that the class supports fast RandomAccess.
3. The attribute
The main attribute methods in ArrayList are:
Initialize the capacity. The default value is 10
private static final int DEFAULT_CAPACITY = 10;
Copy the codeAn empty array
private static final Object[] EMPTY_ELEMENTDATA = {};
Copy the codeIt is also an empty array, and its main function is to know how much the array is inflated when adding elements.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Copy the codeThe size of the ArrayList
private int size;
Copy the codeNote that the ArrrayList has a modCount member variable that keeps track of the number of changes. It is used to check if the list has structural changes (the number of elements in the list has changed) when iterating through the iterator. It is used in multi-threaded environments in case a thread is iterating through the list. Another thread modifies the structure of the list. To have a good understanding of this exception: ConcurrentModificationException. By the way, ArrayList is non-thread-safe.
4. Construction method
Let’s look at the constructor of ArrayList.
You can see that the no-parameter construct directly creates an array specifying DEFAULTCAPACITY_EMPTY_ELEMENTDATA, which is empty by default.
So ArrayList creates an array with an initial capacity of 0 by default when executing this code.
ArrayList list = new ArrayList();
Copy the codeParametric construction method:
Pass in the size of the created array. If it is greater than 0, an array of the size of the passed argument is created. If it is equal to 0, an empty array is specified. If it’s less than zero, it throws an exception.
Looking at the source code, we can see that all the constructor for the passed Collection does is copy the array, copying the existing Collection into the new Collection.
5. The add method
ArrayList is implemented using arrays, so let’s see how the Add method is implemented
The following is the source code of the Add method.
You can see that the ArrayList checks the size of the collection before adding elements
In the ensureExplicitCapacity method, we first increment the number of changes modCount, which is used by the iterator of ArrayList, to provide fast failure behavior when concurrent operations are modified (modCount is guaranteed to remain constant during the iteration, Otherwise throw ConcurrentModificationException, you can view the source code line 865), and then judge whether minCapacity is greater than the current ArrayList internal array length, is greater than the word call grow method for internal array elementData expansion, The code for the grow method is as follows:
6. The remove method
You can delete an ArrayList by index or by content.
Delete elements based on the index
We can see that first of all let’s see if it’s empty. If they are not empty, we loop through the elements, check with equals to see if the elements are the same, and if they are, we call fastRemove to delete the elements. It then copies itself through System.arrayCopy.
7. Modify the method
8. Get elements
Since an ArrayList is an array itself, getting elements is relatively easy.
9. The size () method
9. IsEmpty method
Return size==0.
10. Clear method
11. Loop arrays
The for loop
The for loop is probably the most common traversal method in Java.
The iterator iterator
Let’s look at the implementation:
/** * An optimized version of AbstractList.Itr */
private class Itr implements Iterator<E> {
// cursor, the index of the next element to be returned
int cursor;
// Return the index of the last element; If it does not return -1.
int lastRet = -1;
int expectedModCount = modCount;
Itr() {}
// Pass cursor! = size determines if there is another element
public boolean hasNext(a) {
returncursor ! = size; }@SuppressWarnings("unchecked")
public E next(a) {
// The iterator will throw an exception if it iterates on elements while adding and removing them
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// Move the cursor back one bit
cursor = i + 1;
// return the element at index I and assign lastRet to I
return (E) elementData[lastRet = i];
}
public void remove(a) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
// Call the remove method of ArrayList to remove elements
ArrayList.this.remove(lastRet);
// The cursor points to the location of the deleted element, which was lastRet+1
cursor = lastRet;
//lastRet restores the default value -1
lastRet = -1;
// The value of expectedModCount is synchronized with the modCount, which is incremented by 1 because of the add and remove operations
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while(i ! = size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); }// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
ModCount++ = modCount++ = modCount++ = modCount++ = modCount++ = modCount++ = modCount++ Modifying set() is not available
final void checkForComodification(a) {
if(modCount ! = expectedModCount)// This means that an iterator cannot add or remove elements while iterating through them, otherwise an exception will be thrown
throw newConcurrentModificationException(); }}Copy the codeFrom the code above, if you delete or add a new element during traversal, you will throw an exception, but if you modify it, you will not. Look at the example below.
Little brother not just, if there is a mistake please point out. Like please pay attention, slowly update JDK source read notes
