Source code analysis of ArrayList

In peacetime Java, Lists are needed to store data , And most of the time you can use ArrayList, such as Mybatis Query data list , The return lists are all ArrayList, A lot of data is also stored ArrayList.

jdk edition ： 1.8

ArrayList Is based on Variable size arrays Realization , And allow to add null value , According to the subscript, you can query the data quickly . Once the array is initialized, the size is determined , If you need to add data , You need to copy the data , These operations are time consuming .

Preface

ArrayList Query the data and directly obtain the data according to the subscript , The addition and deletion of data involves the replication of arrays , There are two main methods ：

• System.arraycopy
• Arrays.copyOf

System.arraycopy

arraycopy(Object src, int srcPos,Object dest, int destPos,int length) The array of src, From the starting position srcPos To the final data . Copy to dest Array , The starting position is destPos, The length is length

Will array src from srcPos Starting length is length The data of is assigned to the array dest Start with destPos

Arrays.copyOf

Arrays.copyOf Is also called System.arraycopy Method ：

 public static int[] copyOf(int[] original, int newLength) {
    int[] copy = new int[newLength];
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

First create a new array copy, take original Copy all arrays to copy Array .

The main instance variables ：

//  The underlying array 
transient Object[] elementData;
//  Number and size of arrays 
private int size;
//  Default empty array 
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

• ArrayList Is an implementation based on array , elementData Is the underlying array .
• size Is the number of record arrays .

Create a new one ArrayList example ：

List<Integer> list = new ArrayList<>();

First, call the parameterless constructor , Assign a direct value to An empty array DEFAULTCAPACITY_EMPTY_ELEMENTDATA.

Add data

There are two ways to add data ：

• add(E e) Add directly to the end of the array .
• add(int index, E element) Add data according to subscript .

add(E e)

Add data at the end of the list ：

/**
 * Appends the specified element to the end of this list.
 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal Determine whether the capacity after adding data is sufficient , If not enough , Expansion operation .

private void ensureCapacityInternal(int minCapacity) {
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
      return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
  modCount++;

  // overflow-conscious code
  if (minCapacity - elementData.length > 0)
      grow(minCapacity);
}

ensureCapacityInternal First call calculateCapacity, Then call ensureExplicitCapacity.

calculateCapacity The current array is null when , Just go back to 10 and minCapacity The maximum of , Otherwise return to minCapacity. This method returns the size of the array .

ensureExplicitCapacity Judge minCapacity Greater than elementData.length Capacity expansion , The focus here will be grow Method ：

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //  The new length is the same as the original length  1.5 times 
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        //  The new length is smaller than the required length , Assign to the new length 
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    //  Copy the array to the new length array 
    elementData = Arrays.copyOf(elementData, newCapacity);
}

group I did two things ：

• The length is enlarged to the original 1.5 times
• Copy the array to the new length array

After judging whether to expand the capacity , Directly in size Assign the element to be added on the position , then size Since the increase again .

elementData[size++] = e;

add The method has two main steps ：

• Judge whether to expand capacity , The length of the newly added data array is greater than the length of the existing array , Conduct 1.5 Expansion of .
• In the array size Subscript assignment data .

add(int index, E element)

This add data is to add data at the specified subscript .

public void add(int index, E element) {
    //  Whether the subscript is out of bounds 
    rangeCheckForAdd(index);
    //  Judge whether to expand capacity 
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //  Copy i To size Data to i+1  To size +1
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

add(int index, E element) stay index Subscript add data ,

• First judgement index Whether in 0 ~size Between .
• Judge whether to expand capacity , Need to expand , Conduct 1.5 Double expansion .
• Data migration , hold index All future data will be moved back by one bit .
• assignment index Subscript data .

get data

The only way to get data is through the array subscript get(int index)：

public E get(int index) {
  // Check whether the array range is exceeded  
  rangeCheck(index);
  
  return elementData(index);
}

@SuppressWarnings("unchecked")
E elementData(int index) {
    //  Get data by subscript  
    return (E) elementData[index];
}

It is easy to get data here ：

• Check whether the subscript exceeds the range of the array .
• Access data through subscripts .

Delete data

remove(Object o)

Delete the first matching element in the list ：

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;
}

Judge whether the data to be deleted is null:

• It's empty , Judge elementData[index] Is it empty .
• Not empty , Element of judgement equals match elementData[index].

The above judgment is true when , call fastRemove Method ：

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
}

Move array data ,index+1 And the subsequent data moves forward by one digit , Last size-1 The assignment is null.

remove(int index)

according to index Subscript delete data .

public E remove(int index) {
    //  Is it across the border?  
    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;
}