Simple understanding of ArrayList source code

ArrayList
1. Create ArrayList list1 = new ArrayList();
An empty array is created by default

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }

2. Execute list1.add(1);

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Ensure the array capacity. If it is an empty array, set the default length or set it to the length of the data. If the non empty array is not long enough, it will be expanded.
        elementData[size++] = e; //New objects to assign
        return true;
}
 private static final int DEFAULT_CAPACITY = 10; //Default length is 10

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

    ensureExplicitCapacity(minCapacity);//To allocate array length
 }  

  private void ensureExplicitCapacity(int minCapacity) {
    modCount++;  
    if (minCapacity - elementData.length > 0) //If the required length is greater than the length of the current array, expand the capacity
        grow(minCapacity);
    }

private void grow(int minCapacity) { 
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  //First expand to half of the current array
    if (newCapacity - minCapacity < 0) //If it is less than the required array length, the length of the new array is equal to the required length
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);//Create a new array to copy the values of the old array to the new array.
}

3. Execute list1.addAll(list2);

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();  //First, convert the type into an array, and then the other steps are basically the same as add()
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

4. Add an element at the position specified in list1.add (index, element), and the length of the set will be added

public void add(int index, E element) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //Next, copy the specified position of the array, and copy the data from the index position in elementData to the current data
       index+1 The location starts to be copied one by one. And finally will element Assign to index Location
    System.arraycopy(elementData, index, elementData, index + 1,
            size - index);    
    elementData[index] = element;
    size++;
}

5. list1.set(2,10); this method is to assign a value to the data in the position with index 2 and return the replaced data.

     public E set(int index, E element) {
        if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

    E oldValue = (E) elementData[index];
    elementData[index] = element;
    return oldValue;
}

6. list1.remove((Integer) 11);

//It's nothing more than to traverse and then delete the data
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;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
//Or copy the data in the array from index+1 to index at index.
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved); 
    elementData[--size] = null; //Clear the last data
}

7.list1.indexOf(1) / / traverse to find the element and return the index

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i] == null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;

8.list1.contains(-1)

public boolean contains(Object o) {
    return indexOf(o) >= 0;  //If it is not - 1, the certificate finds the data and returns true
}

9. The difference between list1.remove (0) and the method of directly removing objects is that you don't need to find the index of the data first.

public E remove(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

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

    int numMoved = size - index - 1;
    if (numMoved > 0)
//Delete the element of an index, still use the method of array copy
        System.arraycopy(elementData, index + 1, elementData, index,
                numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

10.list1.get(0)

public E get(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//Take the data in the array directly
    return (E) elementData[index];

11.list1.toArray(); in fact, it is an array copy

  public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
  public static <T> T[] copyOf(T[] original, int newLength) {
    return (T[]) copyOf(original, newLength, original.getClass());
}

   public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}
  1. Execute the code Iterator iterator = list1.iterator();

        while (iterator.hasNext()){
        Log.e("TAG", "iterator==="+iterator.next().toString());
        iterator.remove();
    }
    //Source code is found in ArrayList. Iteraror is an object that encapsulates the index.
    private class Itr implements Iterator<E> {
    
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;
    
    public boolean hasNext() {
        return cursor < limit;   //Determine whether the current index is less than the set length
    }
    
    @SuppressWarnings("unchecked")
    public E next() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        int i = cursor;
        if (i >= limit)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];//Take the data from the array here and assign a value to lastRet
    }
    
    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    
        try {
            ArrayList.this.remove(lastRet);  //According to the assigned lastRet in next(), call the remove() method in ArrayList to delete according to the index. So if you call remove(), you must call next()
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
            limit--;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    
    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        Objects.requireNonNull(consumer);
        final int size = ArrayList.this.size;
        int i = cursor;
        if (i >= size) {
            return;
        }
        final Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length) {
            throw new ConcurrentModificationException();
        }
        while (i != size && modCount == expectedModCount) {
            consumer.accept((E) elementData[i++]);
        }
        // update once at end of iteration to reduce heap write traffic
        cursor = i;
        lastRet = i - 1;
    
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
    }   
    

13.List integers = list1.subList(1, 3);

    for(Integer i:integers) {
        Log.e("TAG", "integers==="+i);
    }

 public List<E> subList(int fromIndex, int toIndex) {
    //Check for out of line
    subListRangeCheck(fromIndex, toIndex, size);
     //A new object SubList has been created. This SubList is equivalent to the same class as ArrayList, which has the same methods as ArrayList  
   return new SubList(this, 0, fromIndex, toIndex);
}

//Although I used the enhanced for loop, I actually called the get () method. However, I found that the difference between it and ArrayList is that with the increase of offset, I still maintain the array due to

Tags: less

Posted on Thu, 13 Feb 2020 10:01:59 -0800 by bdcode