1. The ArrayList overview
In daily development, we often use List, among which the most commonly used is ArrayList. The underlying implementation of ArrayList is an array with variable length. Because it uses array structure, the method of operating ArrayList according to index is very fast and the time complexity is 0(1), for example: get(int index),set(int index, E element); However, adding and removing elements is relatively slow. In addition, ArrayList is not synchronous, which means using ArrayList can be a security issue in the case of multiple threads. If you need in a multi-threaded use ArrayList, can use the Vector, or use the Collections utility class List List = Collections. SynchronizedList (new ArrayList (…). ) to make ArrayList thread-safe; You can also use the concurrent container CopyOnWriteArrayList.
2. Read source code
ArrayList inherits AbstractList class and implements List,RandomAccess, Cloneable, Serializable interfaces.
2.1 Member Variables
// The default capacity for initialization
private static final int DEFAULT_CAPACITY = 10;
/** * 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 = {};
/** * The actual storage structure * uses transient modified variables and will not be serialized */
transient Object[] elementData;
/** * The number of elements in ArrayList */
private int size;
// Maximum length
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Copy the code-
Why does an ArrayList define two empty arrays? According to the code above, the main member variables of an ArrayList include the initial size, the underlying array, and the number of elements. In addition, there are two empty array objects. Why are two empty array objects defined? To know when the first element is added to the list, as described in the source comment. As you can see from the following code, by default the DEFAULTCAPACITY_EMPTY_ELEMENTDATA object is used instead of specifying the initial capacity of the ArrayList. If you specify an initial capacity size of 0, the EMPTY_ELEMENTDATA object is used. At the same time, the array expansion will determine whether the current elementData is DEFAULTCAPACITY_EMPTY_ELEMENTDATA object, if it is set to the initial capacity 10.
-
ArrayList serialization problem? Another problem is that elementData uses a transient modifier, and we know that transient variables are not serialized and deserialized, but the elements of an ArrayList are stored in elementData, so how is it serialized and deserialized?
Class can enable its serialization functionality by implementing the Java.io.Serializable interface. To serialize an object, it must be associated with an object output/input stream through which the object state is saved and an object input stream through which the object state is restored. In the serialization and deserialization process need special handling class must use the following methods: accurate signature to implement special private void writeObject (Java. IO. ObjectOutputStream out) throws IOException. private void readObject(java.io.ObjectInputStream in) throws IOException, ClassNotFoundException;
These two methods are implemented in ArrayList, so serialization of elementData is possible, so why? Because if you serialize the elementData array directly without using transient, the length of the elementData array will actually be longer than the number of elements, which may result in empty values after serialization or deserialization. Therefore, ArrayList their implements writeObject (Java. IO. ObjectOutputStream out) and readObject (Java. IO. ObjectInputStream in) method, ensure the array length and the number of elements in the same after serialization.
2.2 Construction method
// Specify a constructor that initializes the capacity
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); }}//
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// Contains a constructor for a Collection
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 code2.3 Main Methods
2.3.1 Adding elements
// Add an element to the end of an array element
public boolean add(E e) {
// <1>, the capacity expansion operation
ensureCapacityInternal(size + 1); // Increments modCount!!
// Add elements to array
elementData[size++] = e;
return true;
}
// Add elements at the specified index position (insert elements)
public void add(int index, E element) {
// Verify that the index position is within the size return.
rangeCheckForAdd(index);
/ / capacity
ensureCapacityInternal(size + 1); // Increments modCount!!
// Move the element after the index one bit back
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// Add the element at the specified location
elementData[index] = element;
size++;
}
// Add a collection
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
/ / capacity
ensureCapacityInternal(size + numNew); // Increments modCount
// Copy the added array elements to elementData
System.arraycopy(a, 0, elementData, size, numNew);
// Change the number of elements
size += numNew;
returnnumNew ! =0;
}
// Adds the collection element at the specified index position
public boolean addAll(int index, Collection<? extends E> c) {
// Whether the index is returned by size
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
/ / capacity
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
// Move the element after the index
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
returnnumNew ! =0;
}
Copy the codeWith the above code, ArrayList can add a single element or a Collection element directly, as well as at a specified index location. The System. Arrycopy method is used to add an element at a specified position, which involves moving the element after the index position. The parameters of this method are described below. In addition, since the length of an array is fixed, and an ArrayList can always add elements, the process of adding elements will determine whether to expand. Array.copyof (T[] Original, int newLength) is used for capacity expansion, and the System. Arraycopy method is also used for its underlying layer. Capacity expansion reduces efficiency. Therefore, if you know the length of the ArrayList, you can directly specify the length during initialization to prevent capacity expansion from reducing efficiency.
System.arraycopyMethods:
/** * Copy one array to another array * SRC original array * srcPos initial position of element group * dest target array * destPos initial position of target array copy * length length of copy */
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
Copy the codeCapacity expansion is implemented as follows:
// Determine the capacity
private void ensureCapacityInternal(int minCapacity) {
// <1> Specifies the initial capacity
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//<2> Change times + 1
modCount++;
// <3>, determine whether to expand the capacity
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// Perform capacity expansion
private void grow(int minCapacity) {
// The original length of the array
int oldCapacity = elementData.length;
// New capacity = 1.5 times the original capacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
// <4> If the new capacity (1.5 times the original capacity) is less than the incoming capacity, expand the number of incoming capacity;
// Otherwise, increase the capacity by 1.5 times
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- <1>, mainly set the initial capacity, if yes
DEFAULTCAPACITY_EMPTY_ELEMENTDATA, then, setminCapacityInitialize capacity 10 and perform capacity expansion. Otherwise,minCapacityIs the number of elements plus 1. - < 2 >,
modCount++, that is, the number of modifications plus one. This variable will be used during the iteration of the iterator, that is, if this parameter changes during the iteration, an error may be reported. For details, please refer to the previous articleJava collection learning record – IteratorIn the next() method. - <3>, judge expansion conditions, when
minCapacity - elementData.length > 0If the initial capacity of ArrayList is 0, or if the initial capacity is not specified, the capacity will be expanded. In addition, ifelementData.lengthGreater than 0 until the array is full, which is 0size == elementData.length, the capacity will be expanded. - <4>, the incoming capacity
minCapacityWhen the initial capacity is not specified, the value will be 10, which must be directly expanded to 10. Other cases require comparisonsminCapacity(which may besize+1Or,size+num) and 1.5 times of the original capacity, the larger of the two after expansion.
2.3.2 Removing elements
Removes the element at the specified index position:
// Remove the element from the specified index and return the element
public E remove(int index) {
// Check whether the index is in the size return
rangeCheck(index);
// Modify the number of set changes
modCount++;
E oldValue = elementData(index);
// Move the element after the index one bit forward
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// Set the last bit to null, the number of elements -1;
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
Copy the codeRemove index position element, first verify index is valid, that is, within size range; Then, the set changes the number of times +1, at the same time, get the index position element value, used to return the result, and move the following elements forward one; Finally, set the position of the last element before the array to NULL for GC processing.
Removes the specified element:
// Remove the specified element
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 codeTo remove the specified element, first traverse the collection to find the index position of the element, then remove the element by index, the same method as above. In addition, ArrayList is allowed to contain null values during traversal, so you need to distinguish whether the values passed in are null or not. Otherwise, using equals on NULL will throw an exception.
Remove collection elements:
// Remove common elements from the collection
public boolean removeAll(Collection
c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
// Preserve the common elements in the collection
public boolean retainAll(Collection
c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
Copy the codeThe batchRemove method is used to remove public elements from a collection and to preserve public elements from a collection.
private boolean batchRemove(Collection<? > c,boolean complement) {
final Object[] elementData = this.elementData;
// <1> Define two variables
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
// <2> Determine whether to overwrite the included or excluded elements to the front of the array based on complement
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
<3> If an exception occurs, copy the element after r to the element after w
if(r ! = size) { System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; }// <4> Remove extra elements.
if(w ! = size) {// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true; }}return modified;
}
Copy the codeBased on the code above, the batchRemove method determines whether to save or delete the common element by passing a Boolean parameter complement. Specific ideas:
- At <1>, define two variables to be used in the <2> loop
- <2>, a variable r defined at <1> is used to traverse the set; Then, by comparing with the parameters, if the same elements need to be deleted, the different elements are placed in the front of the set, and another variable W is used to record their positions. Otherwise, if you want to keep the same element, you place the same element at the front of the array, as passed in
booleanparametercomplementThe comparison is done.
In addition, without the use of additional arrays, the use of multiple variables to operate on the array, in the algorithm is also very common, such as: delete the sorted array of duplicate elements, also use two variables to point to the index position, its implementation and the above method is similar. - <3>, under normal circumstances, r will be equal to size, and will be satisfied only when exceptions occur
r ! = sizeIn this case, we need to keep the elements after r, so we copy the elements after w directly. - <4> removes the element behind the w index, because the previous method just copies the element to the front of the array. There are elements behind w, so it needs to be deleted. At the same time, this case only needs to be handled if there is an element after w, so it needs to be handled in
w==sizeIf all elements in the original collection are retained, no processing is required, and this method also returns false.
Delete all elements:
public void clear(a) {
modCount++;
// clear to let GC do its work
// Walk through the collection, all set to null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
Copy the code2.3.2.1 Remove method in Java8
RemoveIf method:
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if(filter.test(element)) { removeSet.set(i); removeCount++; }}if(modCount ! = expectedModCount) {throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if(modCount ! = expectedModCount) {throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
Copy the codeThis method passes in a lambda expression, then, using a bitmap, indexes the qualifying elements to the bitmap, and then iterates through the collection again, reserving the elements that do not need to be deleted.
ReplaceAll modifies the elements in the collection:
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if(modCount ! = expectedModCount) {throw new ConcurrentModificationException();
}
modCount++;
}
Copy the codeThis method also passes in a lambda expression, and then iterates through the collection, performing the passed lambda function operation on each element.
2.3.2.2 Removing elements from the List loop
Another common problem with removal methods is that elements are removed from loops. We can look at the implementation: use the for loop:
public static void testRemove(a) {
// List element ["1","2","2","3"]
List<String> list = createArrayList();
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals("2")) {
list.remove(i);
}
}
System.out.println(Arrays.toString(list.toArray()));
}
Copy the codeIf there are two elements in a row that are identical to the element to be deleted, the following elements will be omitted, as in the example above:
[1.2.3]
Copy the codeUsing the Forearch loop:
public static void testRemove1(a) {
List<String> list = createArrayList();
for (String item : list) {
if (item.equals("2")) {
list.remove(item);
}
}
System.out.println(Arrays.toString(list.toArray()));
}
Copy the codeThe forEarch loop in Java actually uses the Iterator. In the Java collection learning record — Iterator, the Iterator will determine whether the number of modifications is the same as the expected number of modifications. The remove method above, on the other hand, modifies the number of changes to the collection. Therefore, the output is:
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)
at java.util.ArrayList$Itr.next(ArrayList.java:851)
at collections.iterator.Test.testRemove1(Test.java:20)
at collections.iterator.Test.main(Test.java:15)
Copy the codeCorrect method 1 — Use the remove method in iterator:
public static void testRemove2(a) {
List<String> list = createArrayList();
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
if (iterator.next().equals("2")) {
iterator.remove();
}
}
System.out.println(Arrays.toString(list.toArray()));
}
Copy the codeThe correct way to do this is to iterate through the collection using an iterator, and then use the delete method in the iterator, because in the last article on Iterator, we learned that iterator’s remove method, although modCount is also modified, ExpectedModeCount is set again, which can also be seen in the remove method of Itr, a subclass of ArrayList.
Method 2 — Use the new Java8 method removeIf:
public static void testRemove3(a) {
List<String> list = createArrayList();
list.removeIf(s -> {
return s.equals("2");
});
System.out.println(Arrays.toString(list.toArray()));
}
Copy the code2.3.3 Query methods
Gets the element at the specified index position:
// Gets the element of the specified index
public E get(int index) {
// Verify that the index position is valid,
rangeCheck(index);
// Returns the element at the index position in the array
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
Copy the codeTo determine whether an element exists:
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
// Gets the position where the element first appears
public int indexOf(Object o) {
// Walk through the collection to find its location, and return when found
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
// Get the index position of the last occurrence of an element, traversed from back to front
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
Copy the codeDetermine whether the set is empty, and get the number of elements
public boolean isEmpty(a) {
return size == 0;
}
public int size(a) {
return size;
}
Copy the code2.3.3 Modifying elements
Set (int index, E element); set(int index, E element);
// Modifies the element of the specified index and returns the old value
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
Copy the codeConclusion:
The underlying implementation of an ArrayList is an array, so it has the characteristics of an array. Operations related to indexes are relatively fast, such as GET (int index),set(int index, E Element), etc. However, since the length of the array is fixed, adding elements may involve the expansion operation of the array, which is relatively slow. In addition, inserting and deleting elements involves movement of elements, which is also relatively slow. When using a List, if the operations such as add and insert are frequent, it is recommended to use LinkedList. If you know the number of elements when using ArrayList, you can directly set the capacity of the elements during initialization to avoid efficiency reduction caused by expansion.