All the code in this article comes from jdk1 eight
Introduction to ArrayList
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList inherits AbstractList and implements list, randomaccess, Cloneable, Java io. Serializable interface
java.lang.Object java.util.AbstractCollection<E> java.util.AbstractList<E> java.util.ArrayList<E>
List is a dynamic array and allows manipulation of all elements, including null.
Each ArrayList instance has a capacity. This capacity is the number of elements that can be stored in the list array. It is always greater than or equal to the number of elements. When an element is added to an ArrayList, its capacity automatically increases. Before adding a large number of elements through the ensureCapacity method, the required capacity is predicted, so you can manually set the capacity of the ArrayList instance, which will reduce the number of reassignments.
The ArrayList implementation is out of sync. If one or more threads modify the ArrayList structure explicitly, and at least one or more threads modify the ArrayList structure at the same time; Setting only the value of an element is not a structural modification.
Common functions
Interview questions
1. How to expand the capacity?
2. Thread safe? How to ensure thread safety
3. How to initialize?
4. Time complexity of finding, adding and deleting elements?
5. Comparison between ArrayList and LinkedList
Source code analysis
/**
* Default initialization capacity
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* For shared empty array instances without instances
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance for empty instances of default size
* Different from EMPTY_ELEMENTDATA, when the first element is added, you can know how to expand
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* ArrayList Underlying data structure
* Any empty ArrayList element type is DefaultAttribute_ EMPTY_ ELEMENTDATA
* When the first element is added, it will be extended to DEFAULT_CAPACITY
*
*/
transient Object[] elementData; //Simplify non nested access to private classes
Note: transient keyword means that when Java's default serialization mechanism is adopted, the attribute modified by this keyword will not be serialized, indicating that this attribute does not adopt the default serialization method because it implements serialization and deserialization (writeObject and readObject).
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
1. The number of records in the list in serialization and serialization in order
2. If modcount occurs during serialization= Expectedmodcount will also throw a ConcurrentModificationException
/** * The number of elements contained is different from the capacity */ private int size; /** * The maximum array size is integer MAX_ VALUE - 8 */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
Initialization function
/**
* Build an empty list of the specified capacity
*/
public ArrayList(int initialCapacity) {
//Create an array of input sizes
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
//The initial capacity is 0. Initialize an empty array
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
//When the input initialization capacity does not meet the requirements, an IllegalArgumentException is thrown
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Build an empty list with a capacity of 10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Builds a list of all the elements of the specified collection in the order returned by the collection iterator
*/
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//Convert the elements in the original collection upward to Object type
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//When the collection element is 0, initialize an empty array
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**
* Reduce the capacity of ArrayList to the number of elements to minimize storage
*/
public void trimToSize() {
modCount++;//Calculate structural change
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
Find element
Suppose a group of people are queuing up, and each person represents a number in order. The first person is handling business, representing number 0, and the people behind him line up number 1, 2, 3 and 4 in turn. When the staff calls number 3, this person knows that he can stand up, which is equivalent to get(index) operation.
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
First, judge whether the index to be searched is greater than or equal to the size of the array (save data from 0). If the location element is not returned, otherwise, throw the index out of bounds exception
//Use indexOf(o) to determine whether there is a corresponding element
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
public int indexOf(Object o) {
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;
}
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;
}1. First, judge whether the input element is null to avoid null pointer exception (ArrayList can store null elements)
2. indexOf method traverses from beginning to end, and lastIndexOf method traverses from end to end
3. If found, the corresponding position subscript will be returned, which is an integer greater than or equal to 0. If the corresponding element is not found, it will return - 1
The following figure is an example:
Add element
Suppose a group of people are in the queue and a person suddenly comes. Normally, it is at the end of the queue, which is equivalent to add (E); However, this person may choose to jump the queue in case of emergency. If he finds a place to plug in, the people behind him need to step back to generate space, which is equivalent to add(int index, E element)
//Add element at the end of the list
public boolean add(E e) {
ensureCapacityInternal(size + 1);
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);
}
1. First call ensurecapacityinternal (size+1). If elementData is empty, set minCapacity to the maximum of 10 and size+1
2. In case of structural change, modCount will increase by 1
3. If the capacity is still less than the number of elements at this time, it indicates that the array is full, and you need to expand the capacity grow(), which is described below
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
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);
}
1. Gets the current array length oldCapacity
2. The new length is oldCapacity + (oldCapacity > > 1), that is, move the oldCapacity to the right by one bit and then add 1. The new capacity is 1.5 times + 1 of the old capacity
3. If newcapacity < minCapacity, the new capacity is set to minCapacity
4. If the new capacity is larger than the maximum allowed array capacity, the new capacity is set to the maximum allowed by the virtual machine
5. Put elementData into the new capacity array
//Add an element anywhere in the list
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
1. Not only check whether the input index is greater than the array size, but also judge whether it is less than 0
2. Structural changes occurred, in which modCount increased by 1
3. Move some elements backward to make room for the elements to be added
4. Add an element to the subscript
5. Add 1 to the number of elements in the list
The following is an example:
//All elements of the specified collection are added to the list collection. If added, it returns true, otherwise it returns false
public boolean addAll(Collection<? extends E> c) {//E stands for parent class,? Represents a subclass
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew);
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
//If an empty set is added, false is returned
return numNew != 0;
}System.arraycopy(src, srcPos, dest, destpoS,length);The meanings of each parameter are as follows:
Object # src: where to copy -- source array
int # srcPos: which subscript does the source array copy from
Object dest: where to copy to -- destination array
int # destPos: paste to the starting subscript position
int length: the number of elements to be copied
Delete element
//Deletes the element at the specified location
public E remove(int index) {
rangeCheck(index);//1
modCount++;//2
E oldValue = elementData(index);//3
int numMoved = size - index - 1;//4
if (numMoved > 0)//5
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; //6
return oldValue;//7
}
1. Judge whether the input index is less than the number of arrays, otherwise the exception throwing ends
2. In case of structural change, modCount needs to be increased by 1
3. The old value needs to be returned. Record the old value
4. Calculate the number of elements to be moved. For example, 5-2-1 = 2 in the figure below
5. Move the array to the left, that is, delete the element to be deleted
6. Finally, if the location is set to null, the next gc will reclaim the memory space occupied by these elements
7. Return old value
The following figure is an example:
//Deletes 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;
}
1. First, judge whether it is null to avoid null pointer exception, then traverse from beginning to end to find the corresponding element, find and delete, and return true, otherwise return false.
2. fastRemove(int index) is similar to remove(int index) above, but lacks boundary detection because it indicates that the corresponding element has been found within the boundary.
3. Key modCount + +;, The following details will be used in the extended analysis
Convert list object to array object
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
toArray() acts as a bridge between the transformation of array objects and collection objects, and will return a newly allocated array containing all the elements in the list.
Use suggestions
Compared with LinkedList
Time complexity analysis
1. ArrayList is based on the index structure. Inserting or deleting an element in the middle will cause some elements in the list to move. It is suitable for search operation, but not for intermediate insertion and deletion operation; LinkedList is based on the linked list structure. The cost of inserting or deleting elements in the middle is fixed, so it is suitable for frequent insertion and deletion operations.
2. Adding elements in ArrayList will cause the capacity of the array to be reallocated when the threshold is reached.
3. The space waste of ArrayList is mainly reflected in the reserved capacity space at the end of the list; The space cost of LinkedList is reflected in that each element of LinkedList needs to consume considerable space, including pointer
Compared with Array
1. ArrayList encapsulates an array of Object type, which is no different from the array in nature. Some methods are implemented by calling the array method.
2. ArrayList can be regarded as an Array that will automatically expand the capacity, but once the capacity of the Array is allocated, it cannot be changed dynamically.
3. Array can store both basic type elements and object type elements; ArrayList can only store object type elements
Detail extension
Fail fast is a fast failure mechanism and an error detection mechanism for Java collections
The iterators returned by the iterator and listIterator methods of this class are fail fast: if the structure of the list is modified at any time after the iterator is created, such as through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Therefore, in the case of concurrent modification, the iterator will quickly stop the operation, rather than the risk of uncertain behavior at an uncertain time in the future. Moreover, even if it is not in a multithreaded environment, if a single thread violates the rules, it will also throw an exception. Alibaba development manual stipulates as follows:
Why is the fail fast mechanism caused by element deletion in the foreach loop? Because the bottom layer of collection traversal in the foreach loop is through the iterator.
Run directly through the iterator, and of course throw the same exception result.
From the stack information, we can get that the exception occurs on the 14th line of the call chain, string next = iterator next(); The iterator () is called. Checkforcomodification () method, and the exception is thrown in this method. See the reason for throwing the exception.
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
Description: modCount has occurred= expectedModCount is the exception thrown. Next, let's analyze the variables modCount and expectedModCount
Insert figure expectedMod
-
modCount is a member variable in AbstractList, which is inherited by ArrayList. It indicates the number of times that the set has actually been modified. It is used to detect whether structural changes such as add and remove have occurred when traversing the set iterator.
-
expectedModCount is a member variable in the internal class Itr in ArrayList, which indicates the number of times the iterator expects the set to be modified. This value will change only when the iterator operates on the set.
-
Itr is an implementation of Iterator, ArrayList The Iterator obtained by the Iterator method is an instance of Itr.
private class Itr implements Iterator<E> {
int expectedModCount = modCount;
}
Their relationship is as follows:
class ArrayList{
private int modCount;
public void add();
public void remove();
private class Itr implements Iterator<E> {
int expectedModCount = modCount;
}
public Iterator<E> iterator() {
return new Itr();
}
}
What causes modCount= expectedModCount. Through the previous analysis of the source code, it can be seen that the modCount in fastRemove(int index) increases by 1, but at this time, the expectedModCount does not increase by 1, which leads to the inequality of the two numbers.
In short, the collection traversal is carried out through the iterator, but does the add/remove of elements use their own methods in the class? Therefore, it is confused. As a result, when the iterator traverses, when an element is added or deleted through its own methods, it will throw an exception.
After knowing that, we can choose the correct method to delete some elements during traversal
1. The normal for loop is used, and the iterator is not used at this time
2. remove() method of iterator iterator
reference resources:
Java Standard Ed. 8 https://docs.oracle.com/javase/8/docs/api
Holis https://mp.weixin.qq.com/s/e9ITxUmsMFhfjeHhOgTtfA