01 principle

ArrayList uses arrays, which have the same advantages and disadvantages as arrays, and supports dynamic scaling (1.5 times the original). So it’s perfect for scenarios where you need to use indexes for fast access. Also, due to its automatic capacity expansion, we need to be aware of the need to specify the size when initializing the collection.

# # 02 characteristics

  • With contiguous memory space, supporting random access:

  • Modify operation performance is good:

  • Poor insert operation performance (memory replication is required if the insert position is not at the end) :

  • Poor delete performance (memory replication is required if the delete position is not at the end). In practice, in order to improve the delete performance, it is sometimes necessary to mark the data for digital deletion first (resulting in excessive memory fragmentation), and then to actually delete the data when the memory is insufficient, and perform memory replication, such as the mark-collation algorithm in GC. The specific process is as follows (you can also perform memory replication first and then delete the last bit of data) :

## 03 Specific code

Finally from the source code specific analysis, ArrayList add (add), random access (get), delete (remove), insert (add), expand operations (grow).

Add **** :

public boolean add(E e) { ensureCapacityInternal(size + 1); Grow elementData[size++] =e; // Assign a value to array [size]. The current data length is +1return true; }Copy the code

Random access (GET) :

public E get(int index) { rangeCheck(index); // Check whether the subscript value of the array exceeds the amount of data the list actually containsreturnelementData(index); // random access array}Copy the code

Delete (remove) :

public E remove(int index) { rangeCheck(index); ModCount++; E oldValue =elementData(index); Int numMoved = size-index - 1; I f (numMoved > 0) // ArrayCopy (elementData,index+1, elementData,index, numMoved); elementData[--size] =null; // Delete a value, so the last bit of the original array is nullreturn oldValue;   
 }
Copy the code

Insert (add)

public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! grow System.arraycopy(elementData, index,elementData, index + 1, size- index); // Copy array elementData[index] =element; // insert data size++; }Copy the code

Expansion (grow) :

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity =oldCapacity + (oldCapacity >> 1); // The new capacity is 1.5 times the original capacityif (newCapacity - minCapacity < 0)            
        newCapacity = minCapacity;        
 if(newCapacity - MAX_ARRAY_SIZE >0) newCapacity =hugeCapacity(minCapacity); // minCapacity is usually close tosize, so this is a win: elementData =Arrays.copyOf(elementData, newCapacity); // Copy the original data to the expanded array}Copy the code