I. Basic concepts

 

ArrayList is a container class that can add object elements and perform modification, query and deletion of elements. The bottom of ArrayList is implemented by arrays, so as arrays, the elements contained in container objects can be queried quickly and randomly according to the index, and the time complexity is O(1). However, unlike arrays, the length of arrays is constant after the creation of an array object and variable after the creation of an ArrayList object, so ArrayList is also called a dynamic array. How can the dynamic array data structure of ArrayList be implemented? Next, open the source code of ArrayList to see.

 

Source code analysis

 

2.1. Inheritance and Implementation of ArrayList Class

 

Figure 2.1 Inheritance and implementation of the ArrayList class (excluding classes inheriting ArrayList)

• From the inheritance interface, we can find that ArrayList inherits AbstractCollection Abstract class, implements List interface, and implements Random Access, Cloneable and Serializable tag interfaces. Therefore, ArrayList objects have the characteristics of fast random access to elements according to index, calling clone() method of Object, and serialization. What is the Java Markup Interface, in the last article

        "Java's Four Markup Interfaces Serializable, Cloneable, Random Access and Remote Interfaces" Summary

 

2.2. Attributes of ArrayList

 

• As you can see from the source code, ArrayList has the following main attributes

 private static final long serialVersionUID = 8683452581122892189L;//Be used for ArrayList Version of object serialization ID

 private static final int DEFAULT_CAPACITY = 10;//ArrayList Object's default capacity size

 private static final Object[] EMPTY_ELEMENTDATA = {};//Be used for Null Of ArrayList object
   
 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//Used to create a default capacity size ArrayList object

 transient Object[] elementData; //Used to create dynamic sizes ArrayList Object, the array referenced by this instance variable can be said to be ArrayList container
 
 private int size;//ArrayList Dimensions of objects

 

 

2.3. Three constructors of ArrayList class

 

A parametric constructor, a constructor passing in an int with specified capacity, and a constructor passing in a container object for initialization

 

    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);
        }
    }
//Appoint ArrayList Constructor of Initial Capacity

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
//A default capacity ArrayList Parametric constructor
   
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
          
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
//A constructor that takes a parameter as a container object, converts the container object into an array object, and then converts the container object into an array object. ArrayList Array references within objects elementData Initialize as this array object( Object[])

 

2.4. Specific Implementation Details of ArrayList Dynamic Array

 

After the ArrayList object is created, how can we change the capacity of this object to realize dynamic array? Let's look at some important ways to realize dynamic array.

 

• Group method. The new capacity of ArrayList is 1.5 times the original capacity. The source code is as follows.

  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//int Maximum integer minus 8
private void grow(int minCapacity) {
    
        int oldCapacity = elementData.length;//primary ArrayList Object capacity
        int newCapacity = oldCapacity + (oldCapacity >> 1);//New capacity turned into original capacity+Original capacity/2,That is to say, the new capacity is increased to the original 1..5 times
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
//If the new capacity is still less than the specified capacity, the value of the new capacity is updated to the specified capacity.
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
//If the new capacity is larger than int If the maximum value of an integer is minus 8, the call is made hugeCapacity(minCapacity)，The new capacity is Interger.MAX_VALUE,The biggest Int integer
        elementData = Arrays.copyOf(elementData, newCapacity);
//Create an array length of newCapacity，Containing all the original ArrayList within elementData New for all elements elementDate array
  

• The hugeCapacity method, called in the group method

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

 

• The trimToSize method. Change the length of the elementData object in the ArrayList object to size, and the size variable stores the number of elements contained in the ArrayList object. Using this method, the elementData array in the ArrayList object can be made as long as the number of elements to avoid unnecessary memory footprint.

• public void trimToSize() {
          modCount++;
          if (size < elementData.length) {
              elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);
          }
  //If size less than elementData If size=0，order elementData An empty array; size>0,send elementDate Array variables point to inclusion primitives elememtData All elements, length is the number of elements size New array
      } 

 

• The ensureExplicitCapacity method calls the group method to increase capacity when the parameter minCapacity is larger than the length of the array referenced by elementDate

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

 

• The ensureCapacity method, if an ArrayList object is constructed by calling a parametric constructor, and the elementDate array is not created at this time, can be invoked to ensure that the ArrayList object capacity is at least 10 (default value) and not less than the value specified by the minCapacity parameter.

    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0: DEFAULT_CAPACITY;
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

 

• The ensureCapacityInternal method is called to ensure that the number of elements + 1(size+1) is less than or equal to the length of the elementDate array when the add method is called. If size+1 is larger than element.length, the group method is called to expand the ArrayList object in the ensureExplicitCapacity method.

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

}

 

• The add(int index) method implements adding elements at the specified index with time complexity of O(n)

public void add(int index, E element) {
        rangeCheckForAdd(index);//First check whether the index is out of bounds

        ensureCapacityInternal(size + 1); //ensure ArrayList Capacity, i.e. elementData The length of the array is greater than that before adding elements size+1
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
//Will from index Move one bit backward at each location and the following elements, indexing+1. So the time complexity of calling this method is O(n)
        elementData[index] = element;
//Will elements element Add to the index as index Location
        size++;//Number of elements plus one
    }

 

• remove(int index) method, which realizes deleting elements at specified locations with time complexity of O(n)

 public E remove(int index) {
        rangeCheck(index);//Check if the index is out of bounds

        modCount++;
        E oldValue = elementData(index);

        int numMoved = size - index - 1;//Number of elements behind this element
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,  numMoved);
//Move the element behind this element forward by one bit, and subtract the index by one. index The element at the end (the element to be deleted) is overwritten by the element at the end. So the time complexity of this method is O(n)
        elementData[--size] = null;

//The array index is size Where there are no elements, make it empty, number of elements size-1
        return oldValue;
//Regarding deleted elements as the return value of the method
    }

(There are many other ways to implement dynamic arrays in ArrayList. These are the main ways to implement dynamic arrays in ArrayList. Other methods of the ArrayList class are not covered here.)

 

(Xiaoguan originality, if there are errors, I hope you guys criticize and correct)

(Reprinted please indicate the source)