Introduction to the
ArrayList is a variable-length array-based collection class. ArrayList allows null and duplicate elements. When you add more elements to an ArrayList than the underlying array, it automatically expands to a larger array.
In addition, ArrayList can guarantee random lookup operations under O(1) complexity because it is based on arrays. Otherwise, ArrayList is a non-thread-safe class. In a concurrent environment, multiple threads operating on ArrayList at the same time can cause unpredictable errors.
ArrayList is the most common collection class. Let’s look at some common methods:
List<String> dataList = new ArrayList<>();/ / create the ArrayList
dataList.add("test");// Add data
dataList.add(1."test1");// Specify a location to add data
dataList.get(0);// Get data at the specified location
dataList.remove(0);// Remove data at the specified location
dataList.clear();// Clear the data
Copy the codeA constructor
ArrayList has two constructors, one that takes no arguments and the other that requires an initial capacity value. The most commonly used constructor is the no-argument constructor. The code is as follows:
private static final int DEFAULT_CAPACITY = 10; // The initial capacity is 10
private static final Object[] EMPTY_ELEMENTDATA = {};// An empty object
// An empty object. If created using the default constructor, the default object content defaults to this value
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // Where the current data object is stored. The current object does not participate in serialization
private int size; // The current array length
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;
}
Copy the codeThe above code is relatively simple, and what both constructors do is not that complicated; both aim to initialize the underlying array elementData. The difference is that the no-argument constructor initializes an empty array of elementData, and when elements are inserted, expansion reinitializes the array with the default values. The parameterized constructor initializes elementData as an array of parameter values (>= 0).
add()
For array (linear table) structures, insert operations fall into two categories. One is to insert at the end of the element sequence, and the other is to insert elsewhere in the element sequence.
- Tail insert element
/** Inserts */ at the end of the element sequence
public boolean add(E e) {
// 1. Check whether the system needs to be expanded
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. Insert the new element at the end of the sequence
elementData[size++] = e;
return true;
}
Copy the codeFor inserting at the end of an element sequence, the situation is relatively simple, requiring only two steps:
- Checks whether the array has enough space to insert
- Inserts the new element to the end of the sequence
The diagram below:
- Specify where to insert elements
/** Inserts */ at index in the element sequence
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
// 1. Check whether the system needs to be expanded
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. Move index and all elements after it one bit back
// arrayCopy (the number of elements to be copied from, where to copy, the number of elements to paste from, the number of elements to copy)
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 3. Insert the new element at index
elementData[index] = element;
size++;
}
Copy the codeIf the insertion is at the specified (assuming reasonable) position in the sequence of elements, the situation is slightly more complicated and requires three steps:
- Checks if the array has enough space
- Move index and all elements after it one bit back
- Insert the new element at index
The diagram below:
As you can see from the figure above, inserting a new element into the specified position in the sequence requires moving that position and all subsequent elements back one bit to make room for the new element. The time complexity of this operation is O(N), and moving elements frequently can cause efficiency problems, especially if there are a large number of elements in the collection. In everyday development, we should avoid calling the second insert method in a large collection unless we need to.
Expansion mechanism
Let’s take a look at the scaling mechanism of ArrayList. Variable length data structures need to be expanded when there is no free space in the structure. In an ArrayList, when space runs out, it expands by 1.5 times the size of the original array. The relevant source code is as follows:
/** Calculates the minimum capacity */
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);
}
/** Core method of expansion */
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
NewCapacity = oldCapacity + oldCapacity / 2 = oldCapacity * 1.5
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// Perform capacity expansion
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// If the minimum capacity exceeds MAX_ARRAY_SIZE, expand the array capacity to integer.max_value
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
Copy the codeThe above is the logic of expansion, the logic is very simple, here do not repeat.
get()
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
Copy the codeThe logic of get is simple: check to see if the boundary is crossed and get the element according to index.
remove()
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
// Returns the value of the deleted element
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
// Move the index + 1 and subsequent elements forward one bit to overwrite the deleted value
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// Empty the last element and decrease size by 1
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
/** removes the specified element. If the element is repeated, only the element with the lowest subscript */ is deleted
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true; }}else {
// Walk through the array to find the location of the element to be deleted
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true; }}return false;
}
/** Delete quickly, without boundary checking, and without returning the value of the deleted element */
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 codeThe above delete method is not complicated, here is the first delete method as an example, delete an element steps are as follows:
- Gets the value of the element at the specified position index
- Move the index + 1 and subsequent elements forward one bit
- Empty the last element and decrease size by 1
- Returns the deleted value. The deletion is complete
The diagram below:
The above analysis is not very complicated.
Now, consider this scenario. After we add a lot of elements to the ArrayList and delete a lot of elements, we have a lot of free space in the underlying array. Because ArrayList has no automatic scaling mechanism, a large amount of free space in the underlying array cannot be freed, resulting in waste. ArrayList also provides a way to handle this, as follows:
/** Reduces the array size to the number of elements */
public void trimToSize(a) {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); }}Copy the codeUsing the above method, we can manually trigger the scaling mechanism for ArrayList. This will free up excess space and improve space utilization.
clear()
public void clear(a) {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
Copy the codeThe logic of clear is simply to iterate through and set all elements to null.
My lot
Github.com/jeanboydev/…
My official account
You are welcome to “scan” the following TWO-DIMENSIONAL code, pay attention to my public account, you can accept the latest article push, there are rich lucky draw and welfare waiting for you! 😍
If you have any questions or questions, you can click here to submit an issue or email me at [email protected].
And welcome you
