Wechat public account: Tangerine Java Technology pit article first gold mining platform, follow-up synchronization update public account, after attention reply “group” can join the Internet technology exchange & internal push group, and discuss interview problems with a group of big factory executives. Reply “666” to obtain all information packs available on the First-line Internet (including development software, development specifications, classic e-PDFs, and some premium learning courses).
preface
Arraylists are one of the more common data structures in the Java collections framework. Inherits from AbstractList, implementing the List interface. The bottom layer realizes the dynamic change of capacity size based on array. This is an important module, so let’s learn about ArrayLists today.
Data structure and function of ArrayList
The ArrayList data structure is an array that is used to load data.
Compared with LinkedList, the query efficiency is high, because the bottom layer is array, and the allocation is continuous memory space, CPU can cache the continuous memory space when reading, greatly reducing the performance overhead of reading; Adding and deleting is inefficient and thread unsafe compared to Vector.
Although ArrayList is thread unsafe, in our actual application, it is usually used for query, and there are few add and delete operations involved. If we are involved in frequent add and delete operations, we can choose LinkedList. If we want to ensure thread safety, You can use Vector or CopyOrWriteArray.
How to store any number of objects
The ArrayList constructor is a parameter-free and parameter-free constructor. In the parameter-based constructor, the ArrayList can be initialized using the constructor to specify the size of the underlying array. But do we initialize the size of the array when we use a parameter construct? Let’s look at the code first:
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 codeFrom the code, we can clearly conclude that the array size is not initialized. If you don’t believe me, here’s a test:
public static void main(String[] args){
// Here we use a parameter structure with size 10
ArrayList<String> arrayList = new ArrayList<>(10);
System.out.println("size:" + arrayList);
arrayList.set(1."A");
}
Copy the code
Are you confused by this? Don’t panic. Let’s take our time. Our parameter is initialCapacity, which is set based on elementData, not the array size directly (note, ensureCapacity(); The same goes for methods). We can also understand that this array can now theoretically hold a maximum of 10 pieces of data, but it is still empty.
In the no-argument constructor, we initialize an empty array with a capacity of 0 by default when we call add(); Method, default allocation of the initial capacity [DEFAULT_CAPACITY = 10]. The new process is described in detail below and will not be repeated here.
/** * Array default initial size */
private static final int DEFAULT_CAPACITY = 10;
/** * shared empty array instance for default size empty instance. * is distinguished from EMPTY_ELEMENTDATA to know when and how much to inflate the first element. * /
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/** * construct an initial empty list. * /
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeHowever, for both parameterless and parameterless constructions, arrays are limited in length. How can an ArrayList hold any number of objects of unlimited length? Don’t panic, this place is also used to expand the array.
Array expansion
At present, we have an array whose initial container is 10, and each position has been filled with data, but now we need to add another data. At this time, the current array can no longer meet our requirements, so we need to expand it.
Then we need to expand it by a factor of 1.5, which is [10 + 10/2];
Finally, move the data from the original array to the new array intact, and return the address of the new array, so that the data in the ArrayList is the new array.
Next, let’s look at the implementation in the source code
// Pre-capacity expansion judgment
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//minCapacity: the size of the container after inserting data or the default size
// If minCapacity is larger than the current array, the capacity needs to be expanded
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// Expansion process
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// Java 8 uses bit operation to improve efficiency
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Use the array copy method directly
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the codeAdd to ArrayList
The three new methods in the ArrayList are:
//1. Append the specified element to the end of the list
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//2. Insert the specified list of elements at the specified position.
public void add(int index, E element) {
// Determines whether the specified parameter is out of range
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
//3. Append all the elements in the specified collection to the list at the end.
// Specify iterators for collections in the order they return.
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 codeAs we know from the code, either way, we need to call ensureCapacityInternal(); Method to verify the size of the array, and if it’s insufficient, expand it, as we’ve seen before. We call arrayCopy () after validation when we add a new location; Method to replicate an array. Let’s take a look at the process of specifying position insertion.
Currently we have an array of length 10 with an empty space;
Select * from ‘a’ where ‘a’ = ‘5’; select * from ‘5’ where ‘a’ = ‘5’; select * from ‘5’ where ‘a’ = ‘5’ where ‘a’ = ‘5’;
In the previous step, we left [5] empty and inserted [a] into the space, thus completing the insertion of the specified position.
As shown in the above, the new ArrayList needs to copy the data. If the operation is for the List with large data volume and the expansion operation, the efficiency will be slow.
The deletion of the ArrayList
Without further ado, let’s look at the code:
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;
}
Copy the codeFrom the code, if it is to delete the last bit, then directly delete the operation is completed; If the intermediate data is deleted, the process is similar to the insert operation, the array is copied, and arrayCopy () is called. Methods. Let’s take a look at the process of specifying location deletion.
Currently we have a length of 10;
Now we need to delete the target location [5], we first copy an array, the data before the specified location is unchanged, the data after [5+1] is copied to the new array;
The new array is the array with the data at the specified position [5] removed.
Similarly, deleting an ArrayList is as inefficient as adding it. For arrays with large amounts of data, the number of places to copy and move is relatively large.
Is ArrayList good for queues
A typical queue is a first-in, first-out (FIFO) queue, in and out from the tail and out from the head.
For example, the internal implementation of ArrayBlockingQueue is to implement a circular fixed-length queue with a fixed-length array, using two offsets to mark the read and write positions of the array, and then fold back to the beginning of the array if the length is longer. But it has to be an array of fixed length.
Because in an ArrayList, the underlying array is an array, but the length of the array is uncertain. So we need to do a lot of additions and deletions, and even if we want to delete and add at the specified location, it’s going to have to go through the array copy, which is a little bit more performance intensive.
So, fixed-length arrays are good for queues, arrayLists are not good for queues.
The last
- Articles are original, original is not easy, thanks to the mining platform, feel fruitful, help three even ha, thank you
- Wechat search public number: Orange pine Java technology nest, make a friend, enter the Internet technology exchange group
- All the code, sequence diagram and architecture diagram involved in the article are shared and can be requested for free through the public number plus group
- Article if there is a mistake, welcome to comment messages pointed out, also welcome to reprint, the trouble to mark the source is good