ArrayList is a collection. ArrayList is a collection of objects that you can add, delete, change, and iterate through several ways of playing. Let’s see how an ArrayList can add, delete, modify, and iterate.
Before we look at these operations, we need to understand what a few parameters of an ArrayList mean
/ / array
transient Object[] elementData;
// Array default size
private static final int DEFAULT_CAPACITY = 10;
// Set size
private int size;
// The maximum space that the Jvm can allocate to an array
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// Number of versions
protected transient int modCount = 0;
Copy the code- elementsData
This is an array of type Object that is maintained internally by an ArrayList. Second, the type is Object, so we can only pass in objects, we can’t pass in things like ints, because if you pass in ints, that’s all going to be type wrapped.
- DEFAULT_CAPACITY
This refers to the default size of the elementsData array
- size
I’m talking about the size of the set, not the size of the array, so you can’t confuse that
- MAX_ARRAY_SIZE
This is the maximum amount of space that the Jvm can allocate to an array, and if it exceeds that, an error will be reported
- modCount
< AbstractList > > < AbstractList > < AbstractList > > < AbstractList > > < AbstractList > > < AbstractList > > < AbstractList > > < AbstractList >
- structure
The first is to create an ArrayList, which provides three constructs: To determine what size is expected, either set the array to a fixed length, an array of length 0, or an error (this is an int, so Integer.MAX_VALUE is not greater than Integer.)
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 codeCreate an array object with length 0
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeThe third: According to the Collection Object passed in, toArray directly creates an array Object. Then, some judgments are made to determine whether the Collection passed in has a value. If there is a value, the judgment is made to determine whether it is of Object type. If the Collection is passed with no value, an empty array of objects is created
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if((size = elementData.length) ! =0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if(elementData.getClass() ! = Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); }else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA; }}Copy the code- add
ArrayList adding elements is one of the highlights, it’s an interesting scaling mechanism, so let’s look at these two ways to add a single element, and enrecapacityInternal is our scaling, so let me show you that for a second, the first method, It’s just the size of the array, and then it’s going to be ++, size++ means first, then ++, so our subscript starts at 0. The second method, adding to a location, does a judgment, which is easy to understand, then expands, then copies the array, moves it back one bit, and then assigns the current index position, roughly as follows
/ / the first
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true; } the secondpublic void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
Copy the codeEnsureCapacityInternal is a method that does scaling, so when we first add data, elementData is empty, so our array is 10; The value minCapacity represents the size we expect
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
Copy the codeVersion count +1, and then determine if the expected value is greater than the current array length, if it is, then it really needs to be expanded
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
Copy the codeHere’s the actual code for the expansion, so I’ll comment it out directly in the code; Expand our current array size 1.5 times (can remember a very classic point here, the array is smaller, the smaller the expansion after the results, the greater the array, the greater the expansion after the results, you, you are fine, isn’t it save resources, to the space when the data is little less, does not occupy a space, data when give you enlarge more at a time, also can avoid multiple trigger expansion)
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//oldCapacity >> 1 oldCapacity*0.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
// Whether the current expanded length is greater than our expected value, if not, then the expected value is used as the new length value
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// Determine if the maximum amount of space allocated by the JVM is exceeded, and if so, use integer.max_value as the new length value
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// Expand capacity by replication
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code- remove
Change the version of the array by +1 if the array length is affected.
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
// Get the element I want to delete and return it later
E oldValue = (E) elementData[index];
// Calculate how many elements I need to move forward from index
int numMoved = size - index - 1;
if (numMoved > 0)
// I want to move the index position +1 and all subsequent elements forward one bit
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// Empty the element I want to remove to help the GC with the collection, and then reduce the size of the collection by 1
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
Copy the codeWe can add null to our collection, so we’ll delete the first null. If we don’t delete null, we’ll go to Equals and delete the first one (so, The ArrayList will only remove the objects one by one each time it executes them, so don’t make the mistake of deleting all the matching objects in the list.
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 code 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 code- get
- set
These two are either going to get the elements in the array or modify the elements in the array
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
Copy the code 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 code- traverse
Traverse we can use fori, foreach iterator, here since the ArrayList is the source, said the ArrayList provide iterator, the adapter is to implement the iterator interface, then the ArrayList is no exception He has a few core parameters
protected int limit = ArrayList.this.size;// Size of the current collection
// Position of the next element
int cursor; // index of next element to return
// The position of the element in the last iteration, if the last iteration was deleted, then our lastRet is -1
int lastRet = -1; // index of last element returned; -1 if no such
// The expected version number during the iteration, initialized as the number of changes to our version
int expectedModCount = modCount;
Copy the codeThere are also several core methods to determine if the current element position is larger than the set size, and each time next is cursor +1
public boolean hasNext(a) {
return cursor < limit;
}
Copy the codeWe compare whether the version number we expect is the same as the version number of the actual array. If not, we throw an exception
@SuppressWarnings("unchecked")
public E next(a) {
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
int i = cursor;
if (i >= limit)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// Each time next, set cursor+1
cursor = i + 1;
// Return our current next value and assign it to lastRet
return (E) elementData[lastRet = i];
}
Copy the codeDelete when compared with the above the version number, and our version number in each time you add, delete, change, so we in the traversal, is cannot do increase the delete operation to the list, or it will throw an exception, because will certainly is not the same as the version number, and with the deletion of the iterator is different, After performing the remove method, he will copy the latest version of our current array to the expectedModCount to ensure the consistency of the two versions. The above need to be associated to a point, no matter how you iterate, you can not directly add and delete the set while iterate. For example, foreach’s underlying traversal calls next and does not change the version number, so if you go directly to list.remove, the version number will be different
public void remove(a) {
if (lastRet < 0)
throw new IllegalStateException();
if(modCount ! = expectedModCount)throw new ConcurrentModificationException();
try {
// Perform the delete operation
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
// Synchronize the current version number
expectedModCount = modCount;
// The current length is -1
limit--;
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}Copy the code- conclusion
ArrayList is thread-unsafe. We see no locking operations there. If you want to lock, you can use the Collections synchronizedList. The System. Arraycopy is used to copy the array each time it is added or deleted. The search and update are directly assigned to or obtained from the array, so it is inefficient to add or delete the array each time it is copied. Including its data expansion is also performed copy operation; ArrayList’s expansion mechanism is pretty cool, can be learned; The upper and lower limits of an ArrayList, positioned at 0-INTEger. MAX_VALUE, will not cause developers to endlessly add