Example explanation of Java ArrayList implementation

  • 2020-05-12 02:41:32
  • OfStack

ArrayList overview:

ArrayList is an array based implementation, is a dynamic array, its capacity can automatically grow, similar to the C language dynamic request memory, dynamic growth memory.

ArrayList is not thread safe and can only be used in single-threaded environment. In multi-threaded environment, Collections.synchronizedList (List l) function can be used to return 1 thread safe ArrayList class, or concurrent can be used to send the CopyOnWriteArrayList class under the package.

ArrayList implements the Serializable interface, so it supports serialization, it can be transmitted through serialization, it implements the RandomAccess interface, it supports fast random access, it actually means fast access through subscript Numbers, it implements the Cloneable interface, it can be cloned.

Each ArrayList instance has one capacity, which is the size of the array used to store the list elements. It's always at least equal to the size of the list. As you add elements to ArrayList, its capacity automatically grows. Automatic growth results in a re-copy of the data to the new array, so if you can predict the amount of data, you can specify its capacity when constructing ArrayList. An application can also use the ensureCapacity operation to increase the capacity of an ArrayList instance before adding a large number of elements, which reduces the number of incremental redistribution.

Note that this implementation is not synchronous. If multiple threads access an ArrayList instance at the same time, and at least one of them structurally modifies the list, it must keep external synchronization.

Here is a record and summary of java arraylist


public class arraylist<E> {
  /**
   *  Holds the elements of the collection  
   * 
   */
  private transient Object[] elementData;
  /**  Element size  */
  private int size;

I defined a generic class, an array of object and a private variable to record the number of elements in the collection. There is an extra private variable in the text, but I don't know why it is used. The author didn't explain or mention it


/**
   *  Class at the specified size 
   * @param initialCapacity
   */
  public arraylist(int initialCapacity){
    super();
    if(initialCapacity<=0){
      // Throw exceptions 
      throw new IllegalArgumentException(" The initialization parameter cannot be less than 0");
    }else{
      // Initialize array 
      this.elementData=new Object[initialCapacity];
    }
  }
  /**
   *  Default initialization 
   */
  public arraylist(){
    this(10);
  }
  /**
   *  According to the 1 Class class initialization 
   * @param c 1 One must inherit Collection The class of the interface 
   */
  public arraylist(Collection<? extends E> c){
    // Initialize the 
    elementData=c.toArray();
    size=elementData.length;
    // Convert if it's not an array of any type Objec type 
    if (elementData.getClass() != Object[].class){
      elementData=Arrays.copyOf(elementData,size, Object[].class);
    }
  }

Three initialization methods, the array is initialized according to the default size, the given size is initialized and passed 1 class that inherits the Collection collection interface is initialized by transformation assignment


/**
   *  Expansion set 
   * @param minCapacity
   */
  public void ensureCapacity(int minCapacity){
    /**  The size of the current array  */
    int oldCapacity = elementData.length; 
    if (minCapacity > oldCapacity) {
      /**
       * oldData  Although not used, this is about memory management reasons and Arrays.copyOf() The method is not thread safe 
       * oldData in if References within the lifecycle of elementData This variable, so it won't be GC Recycling off 
       *  when Arrays.copyOf() Methods in turn elementData Copied to the newCapacity You can prevent new memory or other threads from allocating memory elementData Memory overrun modification 
       *  When the end is gone if . oldData The cycle ends and is recycled 
       */
      Object oldData[] = elementData; 
      int newCapacity = (oldCapacity * 3)/2 + 1; // increase 50%+1
        if (newCapacity < minCapacity) 
          newCapacity = minCapacity; 
     // use Arrays.copyOf Copy and generate the elements of the collection 1 Two new arrays 
     elementData = Arrays.copyOf(elementData, newCapacity); 
    } 
  }

This is a core method, the expansion of the set, in fact, the expansion of the array, the size of the minCapacity set, to determine whether the expansion should be carried out, using the Arrays.copyOf () method to expand the capacity,

This method copies the contents of the first parameter into a new array, the size of which is the second parameter, and returns a new array. The variable oldData has been commented in detail above


 /**
   *  Check that the index is out of bounds 
   * @param index
   */
  private void RangeCheck(int index){
    if(index > size || index < 0){
      throw new IndexOutOfBoundsException(" The subscript beyond ,Index: " + index + ", Size: " +size);
    }
  }

Whether the retrieval of 1 subscript results in 1 /**


*  Add elements 
   *  Adds the specified element to the end of the collection 
   * @param e  Added elements 
   * @return
   */
  public boolean add(E e){
    ensureCapacity(size+1);
    elementData[size]=e;
    size++;
    return true;
  }

Add the element, expand the capacity first, assign the value, and then add 1 to the element. Notice that size+1 field size does not add 1. What is done here is arithmetic operation, so the self-increment is needed later


/**
   *  Add elements 
   *  Adds an element to the specified location 
   * @param index  The index index specified 
   * @param element  The element 
   * @return
   */
  public boolean add(int index, E element){
    RangeCheck(index);
    ensureCapacity(size+1);
    //  will  elementData In the from Index The position starts and the length is size-index The elements,  
    //  Copy to from subscript as index+1 The position starts new elementData In the array.  
    //  Moves the element currently in that position and all subsequent elements to the right 1 A location. 
    System.arraycopy(elementData, index, elementData, index+1, size-index);
    elementData[index]=element;
    size++;// The element to add 1
    return true;
  }

The difference here is System.arraycopy (elementData, index, elementData, index+1, size-index);

This is an internal method of c, which is explained in the original text in detail, not to mention here. This is also the core of the whole ArrayList, as well as the internal implementation principle of Arrays.copyOf ()


/**
   *  Add all elements 
   *  According to the specified collection The iterator returns the order of the elements that will be collection To the end of this list.  
   * @param c
   * @return
   */
  public boolean addAll(Collection < ? extends E>c){
    Object[] newElement=c.toArray();
    int elementLength=newElement.length;
    ensureCapacity(size+elementLength);
    // from newElement 0 Starting with the subscript, elementLength An element, elementData size The subscript  
    System.arraycopy(newElement, 0, elementData, size, elementLength);
    size+=elementLength;
    return elementLength!=0;
  }

Basically, the other methods just do different things according to different situations, such as passing in data objects through the interface and then getting the length to expand, and then copying the data into a new array using System,arraycopy


/**
   *  Specify the location and add all elements 
   * @param index  The subscript of the insertion position 
   * @param c  The set of inserted elements 
   * @return
   */
  public boolean addAll(int index, Collection<? extends E> c){
    if(index > size || index < 0){
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " +size);
    }
    Object[] newElement=c.toArray();
    int elementLength=newElement.length;
    ensureCapacity(size+elementLength);
    int numMoved=size-index;
    // Determines if the insertion position is in the middle of the array 
    if(numMoved>0){
      // the index All elements behind the insertion position are moved back 
      //elementData index The subscript starts numMoved Elements are inserted into elementData  the index+elementLength location 
      System.arraycopy(elementData, index, elementData, index+elementLength, numMoved);
    }
    // the newElement In the from 0 The start of the elementLength Elements are added to elementData index Starting position 
    System.arraycopy(newElement, 0, elementData, index, elementLength); 
    size += elementLength; 
    return elementLength != 0;
  }
  
  /**
   *  Specifies the subscript assignment 
   * @param index
   * @param element
   * @return
   */
  public E set(int index,E element){
    RangeCheck(index);
    E oldElement=(E)elementData[index];
    elementData[index]=element;
    return oldElement;
  }
  
  /**
   *  Depending on the index 
   * @param index
   * @return
   */
  public E get(int index){
    RangeCheck(index);
    return (E)elementData[index];
  }
  
  /**
   *  Remove the element according to the subscript 
   * @param index 
   */
  public E remove(int index){
    RangeCheck(index);
    E oldElement=(E)elementData[index];
    /**  The number of elements after the removed subscript  */
    int numMoved=size-index-1;
    // If I'm inside the array, I'm going to move it 
    if(numMoved>0)
      System.arraycopy(elementData, index+1, elementData, index, numMoved);
    // remove 
    elementData[--size]=null;
    return oldElement;
  }
  
  /**
   *  Remove by element 
   * @param obj
   * @return
   */
  public boolean remove(Object obj){
    //Arraylist Allows to store null, So you have to make judgments as well 
    if(obj==null){
      for(int index=0;index<size;index++){
        if(elementData[index]==null){
           remove(index);
           return true;
        }
      }
    }else{
      for(int index=0;index<size;index++){
        if(obj.equals(elementData[index])){
           remove(index);
           return true;
        }
      }
    }
    return false;
  }
  
  /**
   *  Removes an element in the specified range according to the subscript 
   * @param fromIndex  start 
   * @param toIndex  The end of the 
   */
  protected void removeRange(int fromIndex, int toIndex){
    RangeCheck(fromIndex);
    RangeCheck(toIndex);
    // The number of elements to move 
    int numMoved = size - toIndex; 
    // the toIndex The next element moves to fromIndex
    System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved);
    // The number of elements to remove 
    int newSize=size-(toIndex-fromIndex);
    while(size!=newSize){
      elementData[--size]=null;
    } 
  }
  
  /**
   *  Adjust the size of the array to its actual size 
   */
  public void trimToSize(){
    int leng=elementData.length;
    if(size<leng){
      Object[] old=elementData;
      elementData=Arrays.copyOf(elementData, size);
    }
  }
  /**
   *  Converts a collection element into an array 
   * @return
   */
  public Object[] toArray(){
    return Arrays.copyOf(elementData, size);
  }
  
  public <T>T[] toArray(T[] a){
    if(a.length<size){
      return (T[]) Arrays.copyOf(elementData,size, a.getClass());
    }
    // Copy the collection element to a In the array 
    System.arraycopy(elementData, 0, a, 0, size);
     if (a.length > size){
       for(int index=size;index<a.length;index++){
         a[index] = null;
       }
     }
     return a; 
  }

Basically, we operate on the array and use the c method to assign value to move, etc., we can see the original text in detail, except for the private variable in the original text, there are not many problems, the code can run perfectly, the need to pay attention to and difficulties will be System,arraycopy and Arrayist.copy () these two methods
And the use of the variable oldData in the expansion method, which is really good. I don't know why I used it at the beginning, but I will explain it at the end of the text.


Related articles: