I am Chen PI, an ITer of Internet Coding. I search “Chen PI’s JavaLib” on wechat and read the latest articles as soon as possible, reply to [information], and then I can get the technical materials, electronic books, interview materials of first-line big factories and excellent resume templates carefully arranged by me.
1 introduction
ArrayList is one of the most frequently used data structures in collections frameworks in development, and it’s also a must-ask in interviews. So it is necessary to master, skilled use. Therefore, we will analyze the underlying principle from the source analysis and interview analysis of common test points.
2 ArrayList profile
ArrayList is a member of the Java Collections framework. The underlying implementation is array-based, and the collection capacity is dynamically variable. It inherits from the AbstractList abstract class and implements the List interface. At the same time, the implementation of RandomAccess, Cloneable and Serializable three markup interface, shows that ArrayList is fast RandomAccess, can be cloned copy, Serializable.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess.Cloneable.java.io.Serializable {}Copy the code
ArrayList source code analysis
3.1 variable
The underlying ArrayList implementation is array-based, and the collection capacity can change dynamically. Class defines an Object type array to store elements. Because it is an Object type array, it can only store reference data types. If it stores basic data types (such as int, double, etc.), the bottom layer will automatically wrap the basic data types into classes.
ArrayList also defines a variable that records the number of elements in the array and a static variable that represents the default initialized capacity.
/** * ArrayList is an array of elements, the length of the array is the capacity of the collection * the private keyword is not used for internal classes to access the array * the transient keyword means that the array is not part of the serialization */
transient Object[] elementData;
/** * Records the number of elements actually stored in the ArrayList collection */
private int size;
/** * Default initialization capacity */
private static final int DEFAULT_CAPACITY = 10;
Copy the codeArrayList defines two static empty array objects that are used to assign to the elementData array object as an empty array object representing an empty list when the collection is initialized and no elements are added. So why define two empty array objects? We’ll talk more about that later.
/** * A shared static empty array object used in the empty list collection */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** * A shared static empty array object used in the empty list collection initialized by default size */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
Copy the codeAbstractList, the parent of ArrayList, defines the modCount variable, which counts the number of times the collection has been modified by operations. It is used in iterators because the collection structure is not allowed to be modified while iterating through the collection elements (such as adding elements, Delete elements), which prevents collections from being modified during iteration by comparing modCount values.
protected transient int modCount = 0;
Copy the code3.2 Constructors
ArrayList has three constructors: a no-parameter constructor, a parameterized constructor that specifies the size of the Collection, and a constructor that uses the specified Collection to construct the Collection.
The no-argument constructor initializes an empty list of capacity 10, but does not create an array of capacity 10. Instead, the empty array object DEFAULTCAPACITY_EMPTY_ELEMENTDATA is assigned to the elementData variable, creating an array of capacity 10 only when the element is first added.
/** * construct an empty list */ of capacity 10
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeA parameter constructor that specifies the initialized capacity. When the initialized capacity is greater than 0, an array of the specified size is created directly. If the initialized capacity is 0, the EMPTY_ELEMENTDATA empty array object is assigned to the elementData variable.
/** * constructs an empty list */ that specifies the size of the initial 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); }}Copy the codeAn ArrayList object is constructed using the specified Collection Collection. If the Collection is not empty, its elements are copied and assigned to elementData. If the Collection is empty, an empty list is created. Equivalent to new ArrayList(0).
/** * constructs a list containing the specified Collection elements in the order determined by the order in which the Collection iterator returns the elements
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 code3.3 Common Methods
- public boolean add(E e)
Adding an element at the end of the list will first increase the number of record operations on the collection by 1, and then judge whether the collection capacity is sufficient. If not, the collection capacity will be expanded.
/** * Adds an element */ to the end of the list
public boolean add(E e) {
// Change the operation times and whether to expand the capacity
ensureCapacityInternal(size + 1);
// Add the new element to the end of the array
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// If the list is constructed with a default initialization capacity of 10, initialize the list with the default initialization capacity of 10 and the maximum subscript +1 of the current element to be added
Void list = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; void list = DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// If yes, use the default initial capacity 10 to expand the capacity
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
// The number of changes is increased by 1
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
/ / capacity
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// Increase the capacity by 1.5 times
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// The maximum capacity is integer.max_value
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Copy the array
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code- public void add(int index, E element)
When an element is added to the subscript position specified in the list, it will check whether the subscript is within the range and increase the number of operations on the set by 1. Then it will judge whether the set capacity is enough. If not, it will expand the set capacity.
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// Copy all elements after the subscript position one bit back
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the code- public E set(int index, E element)
Modifying a list of elements at the specified subscript position first checks if the subscript is in range, then replaces the element at the specified subscript, returning the old element.
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc} * /
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the code- public boolean addAll(Collection<? extends E> c)
Add all elements of the specified Collection to the end of the list, or check to see if expansion is required and then copy the Collection to the end of the list.
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;
returnnumNew ! =0;
}
Copy the code- public int size()
Returns the number of elements in the collection
public int size(a) {
return size;
}
Copy the code- public boolean isEmpty()
Determines whether the set is empty, that is, whether the set has elements
/**
* Returns <tt>true</tt> if this list contains no elements.
*
* @return <tt>true</tt> if this list contains no elements
*/
public boolean isEmpty(a) {
return size == 0;
}
Copy the code- public boolean contains(Object o)
Check whether the collection contains an element by comparing the presence of an element with equals.
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;
}
Copy the code- public E get(int index)
Returns the element at the specified subscript position, fast access.
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
Copy the code- public Iterator iterator()
Gets an iterator for list that iterates through the elements in the collection.
public Iterator<E> iterator(a) {
return new Itr();
}
Copy the code4 often meet test analysis
4.1 Is ArrayList thread safe?
We know from analyzing the source code of ArrayList that none of its operations are locked, making it thread-unsafe in a multithreaded scenario. In the case of non-multi-threaded usage, we still use it very frequently, because it is mainly used to store data, more queries, less add and delete operations.
You can use LinkedList if you want to add and delete a lot of things. LinkedList adds and deletes things quickly. (We’ll cover LinkedList next time).
If thread safety is required, we can recommend using Vector collections. Analysis of the source code of Vector will find that many methods add the synchronized keyword, that is, only one thread can operate at a time, so the efficiency is low, but Vector is thread safe. However, the Collections utility class in the JDK provided a method, synchronizedList, that could turn a thread-unsafe ArrayList collection into a thread-safe collection object, so Vector became less commonly used.
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("Java");
arrayList.add("C++");
// encapsulate a thread-safe collection
List<String> list = Collections.synchronizedList(arrayList);
}
Copy the code4.2 Advantages and disadvantages of ArrayList
- Advantages: Fast query speed, because the bottom layer is based on array implementation, array in memory is a piece of related content space, so according to the address and index can be fast random access to the set of elements.
- Disadvantages: Slow addition and deletion. Every addition and deletion of elements may involve the change of array length and element copy movement, especially when there are many array elements, it is time-consuming. Threads are not safe.
4.3 ArrayList is an array implementation, so why not use arrays directly?
Although the bottom layer of ArrayList is implemented through arrays, but it has an internal array encapsulation, can support automatic dynamic expansion, while using arrays directly, if you want to achieve dynamic expansion effect, you need to deal with the expansion mechanism, which is prone to error. Moreover, ArrayList encapsulates many methods (such as adding elements at specified locations, deleting elements with specified subscripts, traversing collections, etc.) to make it easier for developers to manipulate collections and reduce development costs.
4.4 What has changed since JDK 1.7?
Before JDK 1.7, ArrayList initializers called this(10) to actually initialize an array. In JDK 1.7 and later, static empty arrays were assigned to elementData without actually initializing capacity 10. The capacity changes to 10 the first time you add an element.
In addition, the previous capacity expansion is 1.5 times +1 of the original capacity, and after the expansion is 1.5 times of bit operation, the expansion speed is faster.
/ / 1.7 before
int newCapacity = (oldCapacity * 3) /2 + 1;
/ / after 1.7
int newCapacity = oldCapacity + (oldCapacity >> 1);
Copy the code4.5 After initializing the ArrayList, what happens if YOU call the set method directly?
After initializing the ArrayList(Collection<? Extends E> c)), both the default and the specified size initializations have an underlying size value of 0, but the set(int index, E element) method first checks to see if the subscript is greater than or equal to size. If yes, an error is reported. Therefore, the set method cannot be called immediately after the initialization of the ArrayList object, and an error will be reported.
// After initialization, the value of size is still 0
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 E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the code
4.6 Why is it Slow to Add and Delete ArrayList?
Through source code analysis, adding and deleting elements to the ArrayList collection will involve array expansion and data copy, and will slow down if the array has a large number of elements. However, if you insert and delete at the end of the array, if you do not exceed the original length of the array, there is no expansion of the array and data copy, so the execution speed is still very fast.
Therefore, we need to select the appropriate data structure according to the actual scenario. In the business scenario, whether there are more additions and deletions, or more queries, we can choose LinkedList, and in the case of more queries, we can choose ArrayList.
4.7 Can I Add and Delete Elements using Iterator?
Through source code analysis, the Iterator method that gets the collection actually returns the implementation class Itr of the Iterator interface. And Itr is an inner class in the ArrayList class.
public Iterator<E> iterator(a) {
return new Itr();
}
Copy the codeThe inner Itr class defines three variables. The cursor variable indicates the next index of the element to return. The lastRet variable indicates the index of the element that needs to be returned. -1 means no return. The expectedModCount variable is the value of the modCount variable in the ArrayList collection when it is assigned to the New Itr ().
In the method next(), which gets the next element, the method checkForComodification() checks whether the current value of expectedModCount is equal to the current value of the ArrayList object modCount, An error is reported if they are not equal, which is why adding or deleting objects to an ArrayList is not allowed when iterators are used.
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;
public boolean hasNext(a) {
returncursor ! = size; }@SuppressWarnings("unchecked")
public E next(a) {
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(a) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw newConcurrentModificationException(); }}final void checkForComodification(a) {
if(modCount ! = expectedModCount)throw newConcurrentModificationException(); }}Copy the code
4.8 Arrays.asList Usage of ArrayList creation
ArrayList objects generated by the array.asList () method will generate an error when calling add, remove, etc.
public static void main(String[] args) {
List<String> list = Arrays.asList("Java"."C++"."Python");
list.add("C#"); // This line will report an error
}
Copy the codeArrayList generated by array.asList () is not java.util.ArrayList as mentioned in this article.ArrayList inherits AbstractList from ArrayList. However, it does not override the add and remove methods of AbstractList, so it will call methods of the same name of its parent class AbstractList directly when calling these methods. However, AbstractList has no specific implementation operations for these methods. Instead, it simply threw an exception.
public class Arrays {
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
/ * * *@serial include
*/
private static class ArrayList<E> extends AbstractList<E>
implements RandomAccess.java.io.Serializable {
private static final long serialVersionUID = -2764017481108945198L;
private final E[] a;
ArrayList(E[] array) {
a = Objects.requireNonNull(array);
}
// Omit some code
}
// Omit some code
}
Copy the codeAbstractList class methods are defined as follows:
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
/ * * * {@inheritDoc}
*
* <p>This implementation always throws an
* {@code UnsupportedOperationException}.
*
* @throws UnsupportedOperationException {@inheritDoc}
* @throws IndexOutOfBoundsException {@inheritDoc} * /
public E remove(int index) {
throw new UnsupportedOperationException();
}
Copy the code4.9 Can an ArrayList store NULL values? Can elements be repeated?
An ArrayList is an array implementation at the bottom, and when adding elements. Instead of validating elements, they are assigned directly to the array, so an ArrayList can store null values, and the stored elements can be repeated.
/** * Adds an element */ to the end of the list
public boolean add(E e) {
// Change the operation times and whether to expand the capacity
ensureCapacityInternal(size + 1);
// Add the new element to the end of the array
elementData[size++] = e;
return true;
}
Copy the code4.10 How Can I Delete a Specified Element while iterating through an ArrayList element?
One might use the following method to iterate over an ArrayList element while deleting the specified element:
You will find that perform error, ConcurrentModificationException concurrent modification abnormalities, we mentioned above using iterators Iterator traversal collection, will not add or delete operations on the set (causes modCount value change), The underlying enhancement for loop is also implemented using iterators, so errors are reported. You should use the remove method of the Iterator class.
5 concludes
The ArrayList collection class is an example of the ArrayList collection class. You can read the source code and write a few demos to get a better understanding of it. You can also comment on any ArrayList interview questions you’ve encountered in the comments below, and I’ll answer them or discuss them together.
Next time, I will continue to explain the collection class LinkedList, which is similar to ArrayList. Welcome to follow, like, and bookmark the next article!