Array copy
ArrayList underlying copy array method:
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
Copies the array in the specified source array from the specified location to the specified location of the target array
add method
JDK 1.8 and later, in When new ArrayList < > (), no space is allocated. An empty array is used
public ArrayList() {
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
When we use the add method for the first time, we initialize the array. The size of the array is 10
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}The ensureCapacityInternal method is used to ensure that new elements can be put into our array.
How does ensureCapacityInternal ensure that the capacity of the ArrayList internal array is sufficient?
/**
calculateCapacity: Returns the length of the array after adding an element
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // First add
return Math.max(DEFAULT_CAPACITY, minCapacity); // Return 10
}
return minCapacity;
}The ensureExplicitCapacity method ensures sufficient capacity
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// Judge whether the capacity is sufficient
if (minCapacity - elementData.length > 0)
grow(minCapacity); // Array expansion method
}Growth method: expand the capacity of the array to 1.5 times of the original, and copy the data in the original array to the new array
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);
}add method summary:
When the add method is called for the first time, the array in ArrayList is initialized with an initialization size of 10, and then the elements are added to the array.
When calling the add method later, first judge whether to expand the capacity?
If capacity expansion is not required, add the element directly to the end
If the capacity needs to be expanded, first expand the capacity to 1.5 times the original, then copy the data in the original array to the new array, and finally add the original to the end of the array
Note:
The dynamic array maintained at the bottom of ArrayList is
transient Object[] elementData;
The size of the data actually stored in ArrayList is size, not Length of elementData array
private int size;
By adding an element to the end, we mean adding the original element to the end elementData[size] = e
get method
Gets the element at the specified location
public E get(int index) {
rangeCheck(index); // Check the subscript of the obtained element. If it is greater than size, an exception will be thrown
return elementData(index);
}
/**
Returns the element with index in the elementData array
*/
E elementData(int index) {
return (E) elementData[index];
}Set method
Used to replace the element at the specified position and return the element at the original position
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}remove (int index) method
Used to delete the element with the specified subscript and return the deleted element
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index); // Get delete element
int numMoved = size - index - 1; // Calculate the number of elements moved forward
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved); // The element after the index subscript moves forward one bit
elementData[--size] = null; // Clears the last element in the array
return oldValue;
}remove(Object o) method
The function is to delete the specified object from the list collection. If the deletion succeeds, true will be returned, and if the deletion fails, false will be returned.
/**
Traverse the array to find the subscript of the element to be deleted,
Delete by subscript (call the System.arraycopy method to move the array forward)
*/
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;
}contains(Object o) method
It is used to judge whether the element is in the List collection. If it is, the subscript of the first element found in the collection is returned. If it is not, it returns - 1
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
indexOf Method: the bottom layer also uses the for loop to traverse one by one, and returns the index of the first element found
*/
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;
}toArray() method
The function is to convert the collection into an array. It is found through the source code that it is also used at the bottom System.arraycopy method
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}Addall (collection <? Extensions E > C) method
The function is to add another set to the set and return whether the addition is successful
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray(); // 1. Convert a set to an array
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Ensure that the elements in the lower set can be loaded in the array
System.arraycopy(a, 0, elementData, size, numNew); // Copy the elements in the collection to the array
size += numNew; // Actual storage size of ArrayList
return numNew != 0;
}Foreach (consumer <? Super E > action) method
Used to traverse the elements in the List collection. The passed in parameter is Implementation class of the Consumer interface.
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) { // Traversing elements in a collection
action.accept(elementData[i]); // Call the accept method to process each element
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}Example: print elements in a collection
ArrayList<String> list = new ArrayList<>();
list.add("a1");
list.add("a2");
list.add("a3");
list.add("a4");
list.forEach(new Consumer<String>() {
@Override
public void accept(String s) {
System.out.println(s);
}
});Sort (comparator <? Super E > C) method
Used to sort the elements in the collection. The parameter is the Comparator comparator interface.
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}give an example:
ArrayList<String> list = new ArrayList<>();
list.add("a31");
list.add("a33");
list.add("a1");
list.add("a17");
list.sort(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.compareTo(o2);
}
});
list.forEach((s) -> {
System.out.println(s);
});