Java ArrayList source code analysis (helps understand data structures)

Source code analysis of arraylist

1. Introduction to arrays

Arrays are very basic structures in data structures. Many programming languages have built-in arrays, which are similar to linearity in data structures.

When an array is created in java, a contiguous memory is partitioned out of memory, and then data is stored sequentially in this contiguous memory when data is entered. When you need to read the data in an array, you need to provide the index in the array, and then the array will be in accordance with the index.

The stored data is taken out and returned to the reader. Not all data in Java can be stored in arrays, only the same type of data can be stored in arrays together.




Because arrays are stored sequentially and the memory for storing data is continuous, the characteristics of arrays are that addressing and reading data is easier and inserting and deleting data is more difficult.


Parametric construction method

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
       //Create an array of specified length
this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) {
       //Empty array
this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);} //If it is neither less than zero, nor less than zero, an exception will be thrown by an error. }


Spatial parameter construction method

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; //Assignment of a member variable
  private static final Object[] DEFAULTCAPACITY EMPTY ELEMENTDATA={}; //The array created by the empty parameter construction method is empty.


The following one is not very useful, you can understand it.

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray(); //The Collection collection is also turned into an array and passed to the current array elementData.
     //Copy arrays if they are greater than 0
if ((size = elementData.length) != 0) { //Determine the length of the current elementData array, if not equal to 0 if (elementData.getClass() != Object[].class) //Determine whether the type is an Object array type, if not elementData = Arrays.copyOf(elementData, size, Object[].class); //Copy an array, then lengthen it, pass in the Object[].class array, and generate an elementData array.
     //If it's not greater than 0, copy an empty one. }
else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; //Set to an empty array } }



Adding elements

public boolean add(E e) {
    //Detecting whether expansion is needed lower¹ensureCapacityInternal(minCapacity: size
+ 1); // size Is the number of data currently stored
    //Array assignment
elementData[size++] = e; return true; }


Entry method for capacity expansion, calculation capacity

Guarantee Capacity Internal (int min Capacity) {//min Capacity Minimum on private void, when passed after + 1
Lower ensure ExplicitCapacity (lower calculate capacity (elementData, minCapacity); // calculate capacity, pass in an array elementData, and then pass in a minimum capacity minCapacity


Computation of Minimum Capacity

private static int upper²calculateCapacity(Object[] elementData, int minCapacity){
//If elementData It's empty.
//Returns a default or minCapacity,The last is to return to the largest of them.
return Math. max(DEFAULT_CAPACIT minCapacity); 
//If it's not empty, go back. size+1 Value 
return minCapacity;



private void Above³ensureExplicitCapacity(int minCapacityp{
//As soon as a change occurs, +1 modCount
//Does the minimum capacity satisfy the expansion condition (is the current array memory worth capacity?) - Length of object array
if(minCapacity-elementData. length〉0)//elementData.lenth=10 (default capacity is 10)

ModCount++: This field indicates the number of times the list structure has been modified. When you add or remove a collection, modCount+1 is made, which is a variable that records the number of changes in the collection.

When iterator Iterator is used to traverse a collection, modCount is used to judge that the data in the collection has not changed, otherwise an exception will be thrown.


Array expansion method

private void upper¹grow(int minCapacity){
   //Calculate the current array capacity, that is, the old capacity
   int oldCapacity=elementData. length;
   //New array capacity = old capacity + old capacity / 2 (1.5 times old capacity)

  int newCapacity=oldCapacity+(oldCapacity >>1); >>1 Except two

     // oldcapacity=10
    // oldcapacity >>1
    // 0000 1010 >> 1
    // 0000 0101 = 5

    //Judging New Array Capacity-Previous minimum capacity

   if (newCapacity - MAX_ARRAY_SIZE>0) //MAX_ARRAY_SIZE: The value is particularly large. If the new array is larger than it, it crosses the bounds or returns directly to the maximum length.       newCapacity = hugeCapacity(minCapacity);
   elementData=Arrays. copyof(elementData, newCapacity);



    public void add(int index, E element) {
     //Judging whether subscripts are out of bounds Next 1rangeCheckForAdd(index);      //Detecting whether expansion is needed ensureCapacityInternal(size
+ 1);
     //Move all elements after index one bit backward
System.arraycopy(elementData, index, elementData, index + 1, size - index);
take index New values on location coverage
elementData[index] = element; size++; }
private void Last 1rangeCheckForAdd(int index){
if(index>size || index<0)
throw new IndexOutofBoundsException(outofBoundsMsg(index));


System.arraycopy(elementData, index, elementData, index + 1,size - index); examples

int[] elementData = new int[10];
 for(int i=0;i<5;i++){ //Subscripts of arrays 0, 1, 2, 3, 4
elementData[i]=i+1;  //Array values 1,2,3,4,5
System. out. println("=="+Arrays. toString(elementData)); 
int size=5; 
int index=1; //Insert array subscript position
 System. arraycopy(elementData, index, elementData, destPos: index+1, length: size-index);   The original array, inserts the specified location, and specifies the array, the specified location is the current location.+1,To 5-1=4 Location >>Calculate backwards from the insertion position
System. out. println("--"+Arrays. toString(elementData));

Print results

 ==  [1,2,3,4,5,0,0,0,0,0]
 One  [1,2,2,3,4,5,0,0,0,0]  2: The number to insert




Deletion method

Designated Location Delete

public E remove(int index) {
Detecting whether the current subscript is out of bounds Next 1 range Check (index); modCount++; E oldValue = elementData(index); Move the index+1 and subsequent elements one bit forward to override the deleted values int numMoved = size - index - 1; if (numMoved > 0) Next 2 System. arraycopy (elementData, index + 1, elementData, index, numMoved);
Clear out the element in the last position
elementData[--size] = null; return oldValue; }


private void Last 1rangeCheck(int index){
if(index >=size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));



Upper 2 System.arraycopy(elementData, index+1, elementData, index, numMoved); example int[] elementData = new int[10];

For (int I = 0; I < 10; I +) {// array subscripts 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
elementData[i]=i+1; // Array values 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
int size = elementData.lengh; // There are several numbers in the array, and the length is elementData.lengh = 10
int index = 2;
int numMoved = size - index - 1; System. out. println("==" + Arrays. toString(elementData)); System. arraycopy(elementData, srcPos: index+1, elementData, index, numMoved); original array, the specified position is the next position of the subscript to be deleted, and the specified array, the subscript of the deleted position, 10-2-1 = 7 > > > from the specified deleted subscript position, move forward one bit.
System. out. println("--" + Arrays. toString(elementData)); Print results == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 3: Numbers to be deleted I [1, 2, 4, 5, 6, 7, 8, 9, 10, 10]



Designated element deletion

public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    Next 1fastRemove(index);
                    return true;} //Traverse from 0, size is the length of the array, find it and delete it directly
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    return true;
     If there is no matching element, return false return false; }

Quick deletion, no reason to detect index subscripts: because before the need to specify the subscript deletion, now directly specify the deletion of an element, if the element does not exist, for statement traversal will not find this element, all, as long as one of the two if statements can be satisfied, then this element must be in my reasonable range. Inside, so you don't need to check if there are subscripts.



Quick deletion without index subscript detection

private void upper1fastRemove(int index) {
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,
        elementData[--size] = null; // clear to let GC do its work

Tags: Java less Programming

Posted on Thu, 12 Sep 2019 07:43:21 -0700 by koen