Android开发数据结构算法ArrayList源码详解

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandoMaccess, Cloneable, java.io.Serializable
{
    @java.io.Serial
    //序列化uid
    private static final long serialVersionUID = 8683452581122892189L;
    //默认初始容量
    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;　　//其他代码}

　　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);
        }
    }
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) {
            if (c.getClass() == ArrayList.class) {
                elementData = a;
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class);
            }
        } else {
            elementData = EMPTY_ELEMENTDATA;
        }
    }　　//此处为copyOf运行代码　　
    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;　　
         }

    public void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length
            && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                 && minCapacity <= DEFAULT_CAPACITY)) {
            modCount++;
            grow(minCapacity);
        }
    }
　　//核心部分
    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, 
                    oldCapacity >> 1           );
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }
    private Object[] grow() {
        return grow(size + 1);
    }
　　//newLength部分
    public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;
        } else {
            // put code cold in a separate method
            return hugeLength(oldLength, minGrowth);
        }
    }
    private static int hugeLength(int oldLength, int minGrowth) {
        int minLength = oldLength + minGrowth;
        if (minLength < 0) { // overflow
            throw new OutOfMemoryError(
                "Required array length " + oldLength + " + " + minGrowth + " is too large");
        } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) {
            return SOFT_MAX_ARRAY_LENGTH;
        } else {
            return minLength;
        }
    }　　 public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;

　　//在尾部添加一个元素　　
　　private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)　　//此处s为size的意思
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }　　//在指定位置添加元素　　
    public void add(int index, E element) {    
        rangeCheckForAdd(index);    modCount++;    
        final int s;    Object[] elementData;    
        if ((s = size) == (elementData = this.elementData).length)        
        elementData = grow();    
        System.arraycopy(elementData, index,                     
        elementData, index + 1,                     s - index);    
        elementData[index] = element;    size = s + 1;　
    }　　
        private void rangeCheckForAdd(int index) {    
            if (index > size || index < 0)        
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));　　
            
        }

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        modCount++;
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        //elementData剩余容量不足则进行扩容
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        //上文有提到的关于arraycopy的代码，此处为从数组尾部添加元素
        System.arraycopy(a, 0, elementData, s, numNew);
        size = s + numNew;
        return true;
    }
    public boolean addAll(int index, Collection<? extends E> c) {
        //上文提到的判定语句
        rangeCheckForAdd(index);
        Object[] a = c.toArray();
        modCount++;
        //要添加进来的元素的数量
        int numNew = a.length;
        if (numNew == 0)
            return false;
        Object[] elementData;
        final int s;
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew);
        //计算要将多少元素向后移动
        int numMoved = s - index;
        if (numMoved > 0)
        //要在index位置，新增numNew个元素，所以从index位置开始，往后挪numNew位，一共有numMoved个元素需要挪动
            System.arraycopy(elementData, index,
                    elementData, index + numNew,
                    numMoved);
        //空出来的位置即为要添加的元素的位置
        System.arraycopy(a, 0, elementData, index, numNew);
        size = s + numNew;
        return true;
    }

public E remove(int index) {
        Objects.checkIndex(index, size);
        final Object[] es = elementData;
        @SuppressWarnings("unchecked") E oldValue = (E) es[index];
        fastRemove(es, index);
        return oldValue;
}
public staticint checkIndex(int index, int length) {    return Preconditions.checkIndex(index, length, null);}
private void fastRemove(Object[] es, int i) {
        modCount++;
        final int newSize;
        if ((newSize = size - 1) > i)
            System.arraycopy(es, i + 1, es, i, newSize - i);
        es[size = newSize] = null;
}//删除指定元素方法
public boolean remove(Object o) {    final Object[] es = elementData;    final int size = this.size;    int i = 0;    // 正序找对应元素下标    found: {        if (o == null) {            for (; i < size; i++)                if (es[i] == null)                    break found;        } else {            for (; i < size; i++)                if (o.equals(es[i]))                    break found;        }        return false;    }    // 找到了，调用fastRemove，进行删除    fastRemove(es, i);    return true;}

//删除集合c中的所有元素public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false, 0, size);
    }//保留集合c中的所有元素
public boolean retainAll(Collection<?> c) {
        return batchRemove(c, true, 0, size);
    }//核心代码
boolean batchRemove(Collection<?> c, boolean complement,
                        final int from, final int end) {　　　　　//判断集合c是否为空
        Objects.requireNonNull(c);
        final Object[] es = elementData;
        int r;
        // Optimize for initial run of survivors
        for (r = from;; r++) {
            if (r == end)
                return false;
            if (c.contains(es[r]) != complement)
                break;
        }　　　　　//w用于写入保留的元素
        int w = r++;
        try {
            for (Object e; r < end; r++)
                if (c.contains(e = es[r]) == complement)
                    es[w++] = e;　　//当这个元素可以保留时，将其赋给es[]
        } catch (Throwable ex) {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            System.arraycopy(es, r, es, w, end - r);
            w += end - r;
            throw ex;
        } finally {　　　　　　　//相关善后工作　　
            modCount += end - w;
            shiftTailOverGap(es, w, end);
        }
        return true;
    }
private void shiftTailOverGap(Object[] es, int lo, int hi) {　　　　//善后工作相关代码    System.arraycopy(es, hi, es, lo, size - hi);
　　　// 从索引hi开始，有size-hi个元素需要往左挪，这些元素依次挪到lo以及lo之后的位置
     // 它们都向左挪了hi-lo个单位
　　// 挪动之后，原先的索引size-1的元素，对应的是size-1-(hi-lo)，这个索引之后的元素都赋值为null    for (int to = size, i = (size -= hi - lo); i < to; i++)        es[i] = null;}

public E set(int index, E element) {
        Objects.checkIndex(index, size);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
public static
    int checkIndex(int index, int length) {
        return Preconditions.checkIndex(index, length, null);
    }
public static <X extends RuntimeException>
    int checkIndex(int index, int length,
                   BiFunction<String, List<Number>, X> oobef) {
        if (index < 0 || index >= length)
            throw outOfBoundsCheckIndex(oobef, index, length);
        return index;
    }

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