“This is the 10th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Introduction to the

ArrayList is a commonly used data structure in Java collection framework. It inherits AbstractList and implements List interface. The bottom layer implements dynamic change of capacity based on array, allowing NULL members. Also implemented RandomAccess, Cloneable, Serializable interface, all ArrayList is to support fast access, copy, serialization.

Member variables

The underlying ArrayList is based on arrays to achieve dynamic capacity change.

/** * The size of the ArrayList (the number of elements it contains). */ private int size; // Transient Object[] elementData;Copy the code

Note: Size represents the actual number of elements in the array, elementData.length represents how many elements can be contained.

The default initial capacity is 10,

/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
Copy the code

ModCount, defined in AbstractList, records the number of operations performed on a List

protected transient int modCount = 0;
Copy the code

The following two variables are used in constructors

/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 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

What’s the difference between two empty arrays? We distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when first element is added. In simple terms, the first time you add an element, you know that the elementData is initialized from an empty constructor or from a parameter constructor. To determine how to expand capacity.

The constructor

No parameter constructor

/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the code

Note: Construct a List with an initial capacity of 10. The constructor assigns an empty array to elementData that expands to 10 the first time an element is added

Construct an ArrayList whose initialCapacity is initialCapacity

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 code

Use Collection to construct the ArrayList function

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

Convert the collection to an array and assign to elementData

Analysis of main operation methods

The Add operation

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) {overflow-conscious code oldCapacity = elementdata.length; int newCapacity = oldCapacity + (oldCapacity >> 1); // if (newCapacity < 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); } 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++; } public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew ! = 0; } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew ! = 0; }Copy the code

The Remove operation

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;
}
	
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;
}

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 operation

public E get(int index) {
	rangeCheck(index);
	return elementData(index);
}
Copy the code

The Iterator Iterator

In a collection, you cannot remove the collection while iterating through the for loop because remove would change the size of the collection, resulting in inaccurate results or an out-of-bounds array

public Iterator<E> iterator() { return new Itr(); } private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; // prevent creating a synthetic constructor Itr() {} public boolean hasNext() { return cursor ! = size; } @SuppressWarnings("unchecked") public E next() { 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() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override public void forEachRemaining(Consumer<? super E> action) { Objects.requireNonNull(action); final int size = ArrayList.this.size; int i = cursor; if (i < size) { final Object[] es = elementData; if (i >= es.length) throw new ConcurrentModificationException(); for (; i < size && modCount == expectedModCount; i++) action.accept(elementAt(es, i)); // update once at end to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); } } final void checkForComodification() { if (modCount ! = expectedModCount) throw new ConcurrentModificationException(); }}Copy the code

Member variables:

  • Cursor: Represents the index of the next element to access
  • LastRet: represents the subscript of the last element to access
  • ExpectedModCount: Indicates the expected number of changes to the ArrayList. The initial value is modCount

Function:

HasNext: If the subscript of the next element is equal to the set size, it is the end

Next: First check whether the expectedModCount is equal to the modCount, then check whether the cursor exceeds the set length, then assign the cursor to lastRet and return the element with subscript lastRet, and finally, the cursor increases by 1.

Remove: First check whether lastRet is less than 0 (the value has not been obtained), then check whether the expectedModCount is equal to the modCount, and then directly call the delete method of ArrayList with pointer to the last operation object.

Initialization state

Call the next method

Call the remove method

conclusion

  • The underlying ArrayList implements dynamically variable capacity based on arrays.
  • The capacity expansion mechanism is to expand the capacity by 1.5 times of the original capacity. If 1.5 times is too small, then we assign the required capacity to newCapacity. If 1.5 times is too large or the required capacity is too large, then newCapacity = (minCapacity > MAX_ARRAY_SIZE)? Integer.MAX_VALUE: MAX_ARRAY_SIZE to expand capacity.
  • After capacity expansion, the element accuracy is ensured by copying the array, so minimize capacity expansion.
  • Maximum storage capacity of an ArrayList: integer.max_value.
  • Size is the number of elements stored in the collection.
  • Elementdata. length is the length of the array, indicating the maximum number of elements that can be stored.
  • If you want to iterate and remove at the same time, you must use iterator. “Remove” must be followed by “Next” and “remove” can only be used once after “next”.