1.ArrayList underlying data structure
The data structure of ArrayList is completed in the form of array to contain data. A series of collections such as ArrayList, LinkedList, Map and set in Java are used to hold data. The first thing you need to consider is what data structure this collection uses to contain data. Secondly, consider whether the concurrency is safe and how the performance is.
1.1 an array
2.ArrayList source code parsing
2.1 Using the ArrayList method
// Define an ArrayList
ArrayList<String> arrayList = new ArrayList<>();
ArrayList<String> arrayList1 = new ArrayList<>(20);
// ArrayList methods to add elements
arrayList.add("CHINA");
arrayList.add("BEIJING");
arrayList.add("CHONGQING");
// ArrayList gets elements by subscript
arrayList.get(1);
// ArrayList methods to delete elements by subscript
arrayList.remove(1);
Copy the code2.2 some thoughts before source code
The first thing you need to think about is a couple of points and it’s probably better to look inside the source code with your questions
1. Since the data structure of an ArrayList is an array, we must define the size of the array when we create an ArrayList. Why is the size of the array not defined? You can also create a specified array size like arrayList1 above, so you can forget about the definition constructor for now
2. The default ArrayList capacity. When you keep adding elements, you don’t have the possibility that the ArrayList will not fit (under limited conditions). What are the trigger conditions for each expansion?
2.3 Source Code Parsing
Things like LinkedList and ArrayList are implementing List interfaces where you pull out the common methods and you program to the interface and I’m not going to draw the implementation diagram here
ArrayList<String> arrayList = new ArrayList<>();
ArrayList<String> arrayList1 = new ArrayList<>(20);
Copy the codeArrayList has several important parameters:
// The default length of the initialization ArrayList
private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData;
private int size;
Copy the codeLook at the constructors first
/ / no arguments
public ArrayList(a) {
// Define an empty array
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// The user will enter the specified initialization length
public ArrayList(int initialCapacity) {
// Check whether the input array length is valid
/** initializes the container if it is greater than 0; initializes the empty array if it is less than 0; throws an exception */
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 code2.4 Arraylist-add source code analysis
Analysis with the constructor of empty parameters
When you’re using an array as a container in terms of performance it’s best to specify the size of the container because when you’re doing scaling it’s best to know how big your data is and make a moderate judgment
/ / generics
public boolean add(E e) {
For details on initializing the array length, see steps 1 to 3 below
ensureCapacityInternal(size + 1); // Increments modCount!!
// Assembles arrays from numbers when the container is initialized
elementData[size++] = e;
// Return true after all operations succeed
return true;
}
// The size of the first step is now 0, so minCapacity is 1
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// Step 2 elementData is empty minCapacity=1
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// Check whether elementData is empty
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// Return the maximum values of DEFAULT_CAPACITY and minCapacity if null
// DEFAULT_CAPACITY=10 by default
// So return 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// Return minCapacity if not empty
return minCapacity;
}
/ / the third step
// Now minCapacity is 10
private void ensureExplicitCapacity(int minCapacity) {
// modCount defaults to 0
modCount++;
// overflow-conscious code
// Here is the decision to expand the mechanism
// When size+1 is greater than the size of the array, expansion is triggered
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 1.5x expansion mechanism
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);
}
Copy the codeWhen size+1 is greater than the length of the array, expansion is triggered
2.5 Arraylist-get source code Analysis
// The underlying data structure of an ArrayList is an array, so the get method gets the data from the array subscript
public E get(int index) {
// Verify the validity of the index you entered just as you did with the null series
// If you enter indexx>=size, an out-of-bounds subscript exception will be raised
rangeCheck(index);
// Returns the data contents of the array with index
return elementData(index);
}
Copy the code2.6ArrayList-remove(index) source code Analysis
// Remove the specified element by subscript
public E remove(int index) {
// Verify the validity of the index you entered just as you did with the null series
// If you enter index>=size, an out-of-bounds exception will be raised
rangeCheck(index);
modCount++;
// Get the element you want to delete
E oldValue = elementData(index);
// Calculate the length of the array to copy
int numMoved = size - index - 1;
if (numMoved > 0)
//Object SRC: original array
// int srcPos: starts at the start of the metadata
//Object dest: Target array
//int destPos: the start position of the destination array
//int length: the length of the array to copy
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
// The remove method returns the element you removed
return oldValue;
}
Copy the code2.7ArrayList-remove(Object O) source code analysis
// Delete data based on the data content
public boolean remove(Object o) {
// Delete data to null
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true; }}else {
[a,c,d,a]) is the first element to be deleted
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
// this is the same as remove (index)
fastRemove(index);
return true; }}return false;
}
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 code