Java（ArrayList）

Java（ArrayList）

package com.atguigu.javase.collection;

import java.util.AbstractList;
import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.RandomAccess;

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable {
	
	
	private static final int DEFAULT_CAPACITY = 10;
	
	private static final Object[] EMPTY_ELEMENTDATA = {};
	
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
	
	// 内部最核心的数组存储
	transient Object[] elementData; // non-private to simplify nested class access
	
	// 计数器
	private int size;
	
	// 记录修改次数
	protected transient int modCount = 0;
	
	// 内部数组初始时是一个空数组,长度为0
	public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
	
	public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
	
	private static int calculateCapacity(Object[] elementData, int minCapacity) { // [], 1
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 第一次添加元素时进入
            return Math.max(DEFAULT_CAPACITY, minCapacity); // 10, 1
        }
        return minCapacity;
    }

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

    private void ensureExplicitCapacity(int minCapacity) { // 10
        modCount++; // 调整修改次数

        // overflow-conscious code
        if (minCapacity - elementData.length > 0) // 10 - 0 > 0
            grow(minCapacity); // 10
    }
    
    private void grow(int minCapacity) { // 10
        // overflow-conscious code
        int oldCapacity = elementData.length; // 0
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容1.5倍
        if (newCapacity - minCapacity < 0) // 0 - 10 
            newCapacity = minCapacity; // 10
        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); // 10
    }
    
    E elementData(int index) {
        return (E) elementData[index];
    }
    
    public E remove(int index) { // 2
        rangeCheck(index);

        modCount++; // 修改次数
        E oldValue = elementData(index);

        int numMoved = size - index - 1; // 11 - 2 - 1
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved); // 把元素整体左移
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
    
    private class Itr implements Iterator {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount; // 内部有一个期望的修改的次数
        
        final void checkForComodification() {
            if (modCount != expectedModCount) // 取元素时, 发现当前的修改次数和期望的有出入, 抛出异常
                throw new ConcurrentModificationException();
        }
    }
    
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1, size - index); // 把元素整体右移
        elementData[index] = element;
        size++;
    }
}