Write in front:
Hello, everyone! Learn more about ArrayList today, and learn more about ArrayList!
Mind mapping:
ArrayList underlying data structure
ArrayList is a dynamic array, a resizable array implementation of the List interface. In addition to implementing the List interface, the class also provides methods to manipulate the size of the array used internally to store the List. Its main underlying implementation is the array Object[] elementData.
As we all know, traversal query speed – array is contiguous space in memory, can be based on the address + index method to quickly obtain the corresponding location of the element. But it is slow to add and delete — every time you delete an element, you need to change the array length, copy and move the element.
ArrayList is one of the more commonly used data structures in Java collections frameworks. AbstractList implements the List interface. The bottom layer implements dynamic change of capacity size based on array. Allow NULL. The RandomAccess, Cloneable and Serializable interfaces are also implemented, so ArrayList supports fast access, replication, and serialization.
LinkedList is similar to ArrayList, but the underlying LinkedList is a LinkedList, whose array traversal is slow, but quickly added and deleted.
Summary:
The bottom layer of ArrayList is the storage of array implementation. The query efficiency is high, but the efficiency of adding and deleting is low.
ArrayList constructor
Here’s a look at the constructor in the API
2.1. No-parameter construction method
Let’s look at the no-argument constructor in the source code:
An empty array with a default size of 10 is used. The array length is not set in the constructor and will be expanded later when the add method is called.
Inside is an assignment operation, the right is an empty capacity array, the left is the storage of data container, the following is reference source analysis;
// Default empty capacity array, length 0
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// Sets the actual container for storing data
transient Object[] elementData;
Copy the code2.2, the parameter is the constructor that specifies the initial capacity
Look at the int constructor in the source code:
With an argument greater than 0, elementData is initialized to an array of initialCapacity size; Argument equals 0, elementData is initialized to an empty array; If the argument is less than 0, an exception is thrown.
2.3. Constructor of type Collection
Take a look at the constructor source:
Convert a Collection of arguments to an ArrayList(essentially replacing the elements of the Collection with arrays); A null-pointer exception is thrown if the collection passed in is null. C. Array() might not return an Object[] array correctly, so use the array.copyof () method. If the collection is converted to an array with an array length of zero, you initialize elementData directly with your own empty member variable.
Conclusion:
The above constructor is relatively simple to understand. The purpose of both the no-argument constructor and the initializer is to initialize the underlying array elementData(this.elementData=XXX);
The no-argument constructor initializes an empty array of elementData. When an element is inserted, expansion reinitializes the array with the default value. The parameter constructor initializes elementData as an array of parameter values (>=0);
If you specify an initialization value (initialize capacity or collection) when constructing an ArrayList instance, an Object array of the specified size is created and a reference to that array Object is assigned to elementData; If no initialization value is specified, the default capacity size 10 is used as the initial capacity of the elementData array when the element values are first added, and an Object[10] array is created using the arrays.conpyof () method.
In general, we use the default constructor. As mentioned above, the add method is called and expanded when using a no-parameter construct. Let’s look at the add method and the details of the expanded method.
3. Add the add() method for analysis
Take a look at the add() method for ArrayList:
3.1, add the specified element to the end of the list
public boolean add(E e)
Copy the codeLet’s start with source code analysis
Let’s start with the first method add(E E). The process is as follows:
// Pass the added data to e
public boolean add(E e) {
// Call the method to verify the internal capacity
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
Copy the codeWe saw that the add method evaluates the size before adding an element, so let’s look at the details of the ensureCapacityInternal method
private void ensureCapacityInternal(int minCapacity) {
// Check whether the array containing data is equal to the empty array
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Use the minimum capacity and the default capacity to make a larger value (for the first capacity expansion)
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// Pass the capacity calculated in if to the next method to continue validation
ensureExplicitCapacity(minCapacity);
}
Copy the codeWhen the first element is added, minCapacity is (size+1=0+1=)1, and after math.max (), minCapacity is 10. EnsureExplicitCapacity is then called to update the value of modCount and determine whether expansion is required. Now look at the SureexplicitCapacity method
private void ensureExplicitCapacity(int minCapacity) {
// The actual number of times to modify the set ++ (used in the process of expansion, mainly used in the iterator)
modCount++;
// Determine the minimum capacity - array length is greater than 0
if (minCapacity - elementData.length > 0)
// Pass the first calculated capacity to the core expansion method
grow(minCapacity);
}
Copy the codeThen there is the core grow() method:
private void grow(int minCapacity) {
// Record the actual length of the array, which is 0 since no elements are stored
int oldCapacity = elementData.length;
// 1.5 times the original capacity of the core expansion algorithm
int newCapacity = oldCapacity + (oldCapacity >> 1);
// Determine whether the new capacity - minimum capacity is less than 0, if it is the first time the add method is called
if (newCapacity - minCapacity < 0)
// Assign the minimum capacity to the new capacity
newCapacity = minCapacity;
// Determine the new capacity - the maximum array size >0, if the condition is met, calculate a large capacity
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Call the array utility class method to create a new array and assign the address of the new array to
elementData elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the codeExecution process:
3.2, add the specified element at the specified location
public void add(int index, E element)
Copy the codeLet’s start with source code analysis
// Insert the element sequence at index
public void add(int index, E element) {
rangeCheckForAdd(index);
//1, check whether the capacity needs to be expanded
ensureCapacityInternal(size + 1); // Increments modCount!!
//2, move index and all subsequent elements one bit back
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 3. Insert the new element at index
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
// index>size; index < 0
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Copy the codeLet’s see how it’s used:
import java.util.ArrayList;
/ * * *@authorPublic account: Programmer's Time *@createThe 2020-11-03 17:05 *@description* /
public class Test03 {
public static void main(String[] args) {
ArrayList<String> list=new ArrayList<>();
list.add("Sea Flame");
// Add data at index 1
list.add(1."Dark yellow fever"); System.out.println(list); }}Copy the codeRunning results:
3.3, add all elements to the end of the list in the specified element order
public boolean addAll(Collection<? extends E> c);
Copy the codeThe description of this method is to append all elements of the specified collection to the end of the list in the order returned by the Iterator of the specified collection.
In simple terms, it is to add all the elements of one set to another set.
Running results:
3.4, inserts all elements from the specified collection into this list, starting at the specified location
public boolean addAll(int index, Collection<? extends E> c);
Copy the codeThis method adds elements from one collection to another. The difference is that this method adds elements to the end of the target collection by default, while this method contains the index, that is, the insertion begins at the specified position.
Running results:
4. Analysis by other methods
ArrayList includes many methods, so let’s review them briefly.
// Remove the element at the specified position
public E remove(int index);
// Remove the first occurrence of the specified element in this list (if present)
boolean remove(Object o);
// Modify the collection element
public E set(int index, Object o);
// Find the collection element
public E get(int index);
// Clear all data in the collection
public void clear(a);
// Determine whether the collection contains the specified element
public boolean contains(Object o);
// Check whether the set is empty
public boolean isEmpty(a)
Copy the code5, Often meet test questions (essence)
5.1. How is ArrayList expanded?
For this, please refer to the expansion steps in Section 3.1 to see its core expansion method:
Conclusion:
- The expanded array is 1.5 times the size of the original array;
- If the value
newCapacityThan the incoming valueminCapacitySmaller, pass inminCapacityIf,newCapacityIf the capacity is larger than the set maximum, the maximum integer value is used.
5.2. Performance Degradation caused by Frequent Expansion of ArrayList. What can I do?
Let’s say we need to add 10W data to the array. Let’s look at the time change before and after:
The result is:
The underlying ArrayList is an array implementation, so each time you add data, you keep expanding it. This takes up memory, and performance is low, so it takes a long time.
We can solve the performance problem with the constructor of ArrayList that specifies the initialization capacity.
5.3. How does ArrayList add and delete elements, and why is it slow?
As we said earlier, it can be added either by index or directly. Before doing this, we need to check the length ensureCapacityInternal. If the length is insufficient, we need to expand the capacity.
The previous expansion is 1.5 times the original expansion, using the bit operation, the right move one.
If the magnitude of the following data is too large, adding an element in one million pieces of data requires copying and moving the following elements, so it is very inefficient.
5.4. Is ArrayList thread safe?
The ArrayList thread is not secure. A thread-safe array container is Vector, which works by adding synchronized to all methods.
Let’s test this by preparing a thread task class:
Then define the test class to test the task class:
Let’s look at the results:
You can see that an exception error is reported, and some threads are still null, indicating that the ArrayList thread is not safe.
Of course, ArrayList can be replaced with a thread-safe collection Vector
Or we can simply add the synchronized keyword to turn unsafe threads into secure ones:
This is also thread-safe.
Why ArrayList threads are not safe?
Thread unsafe:
Thread safety refers to the locking mechanism used in multi-thread access. When one thread accesses a certain data of the class, it is protected and cannot be accessed by other threads until the thread finishes reading the data. There will be no data inconsistencies or data contamination.
Thread insecurity means that data access protection is not provided. Multiple threads may change data successively, resulting in dirty data.
The List interface has two implementations, an ArrayList and a Vector. From the source point of view, because Vector methods before adding synchronized keyword.
When an ArrayList adds an element, there are two steps: 1. Store the element in the Items[Size] location; 2. 2. Increase the Size value.
In the single-threaded case, if Size= 0, add an element that is in position 0 and Size=1;
If you have multiple threads, let’s say you have two threads, thread A puts the element at position 0 first. However, the CPU scheduling thread A pauses and thread B gets A chance to run. Thread B also adds elements to the ArrayList, since Size is still equal to 0 (note that we assume that adding an element takes two steps and thread A only completes step 1), so thread B also stores elements at position 0. Then thread A and thread B both continue to run, increasing Size.
Ok, so let’s look at an ArrayList, where there’s really only one element, stored at position 0, and Size is equal to 2. This is called “thread unsafe”.
5.5 ArrayList and LinkedList
- Underlying data structure:
ArrayListThe bottom layer usesAn array of;LinkedListThe bottom layer usesTwo-way linked list; - Insert and delete element operations:
ArrayListArray storage is used, so the insertion and deletion of elements depends on the location of the element.LinkedListThe use of linked list storage, the deletion of elements is not affected by the location of elements; If you want to insert and delete at position I(add(int index, E element))The time complexity is approximately O(n) because you need to move before you insert. - Random access:
ArrayListforRandom element accessIs significantly more efficient thanLinkedListHigh. Random access is the retrieval of an element by its index (that is, the set and GET (int index) methods). - Thread insecurity:
ArrayListandLinkedListThey’re all out of sync, which means they’re bothThread insecurity. - Interface implementation:
ArrayListTo achieve theRandomAccessCan support random element access, whileLinkedListTo achieve theDequeYou can use it as a queue - Memory usage:
ArrayListIts advantage lies in the continuity of memory. The internal cache structure of the CPU caches continuous memory fragments, which greatly reduces the memory performance overhead and improves efficiency.LinkedListThe space occupied by each element is reflected in the need to consume space memory, to store the precursor and successor data.
Using an ArrayList provides better performance when the operation is to add data to the end of a column rather than in the front or middle, and the elements need to be accessed randomly. It is better to use LinkedList when the action is to add or remove data in front or in the middle of a column of data and to access its elements in order.
More dry goods, quality articles, welcome to pay attention to my original technology public number, wechat search “programmer’s time”!