简介

ArrayList是List接口的一个完结类，它是一个调集容器，咱们通常会通过指定泛型来存储同一类数据，ArrayList默许容器巨细为10，自身能够主动扩容，当容量缺乏时，扩大为本来的1.5倍，和上篇文章的Vector的最大差异应该便是线程安全了，ArrayList不能确保线程安全，但咱们也能够通过其他方式来完结线程安全。

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;　　//其他代码}

这部分可做出有关ArrayList的相关结构，如下图所示

初始化

　　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;　　}

以上代码为ArrayList的初始化，分为三种方式：

1.为给定容量的初始化，传入参数为数组的初始化长度，当该参数大于等于0时，进行初始化，当该参数小于0时，抛出反常

2.过于简略

3.首要通过c.toArray()得到了调集c对应的数据数组，假如c也是ArrayList，直接将c.toArray()赋给elementData，而关于toArray的要害代码如上代码中关于copyOf的部分所示，从该段代码中可知此处的Arrays.copyOf调用的是三参数版本的函数。这个三参数的copyOf函数比较复杂，效果便是回来一个指定的newType类型的数组，这个数组的长度是newLength，值从original仿制而来。仿制的功能由System.arraycopy( )完结：假如newLength大于原数组的长度，多出来的元素初始化为null；假如小于原数组长度，将会进行切断操作。在这儿，两参版本调用三参版本的三个参数为original, newLength, original.getClass()，故得到的数组元素类型和原数组类型一致，长度为newLength，数据由原数组仿制而来。

总之，ArrayList的无参版toArray( )回来了一个和elemantData一模一样的仿制数组。所以判别c也是ArrayList目标时，直接令elemantData 为c.toArray( )了。不然，会执行elementData = Arrays.copyOf(a, size, Object[].class)。通过上面的剖析，三参的copyOf( )是回来一个数据内容和a一模一样的数组，可是数组类型转为Object[ ]类型。之所以有这条句子，猜测可能是某些调集的toArray( )办法，回来的数组不是Object[ ]类型，比方说用一个类承继ArrayList，而且重写toArray( )办法，让它回来一些其他类型。

扩容

    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, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            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 Object[] grow(int minCapacity)为中心部分，故咱们先看这部分，if(oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA)部分阐明当该数组不是还未初始化的数组时，用newLength以及位运算来进行相应的扩容，而newLength相应的代码现已贴在了上面，让咱们来进行具体剖析：此处的minGrowth在grow部分为“minCapacity – oldCapacity”，即满意咱们需求的容量，此处的prefGrowth在grow部分为“oldCapacity >> 1”，即本来容量的一半，当没有溢出时，扩容时所扩的容量便是这两者中最大的那个，而当溢出时，调用hugeLength()来满意minGrowth，假如还时溢出则最多只能给到 Integer.MAX_VALUE – 8 这个量。

那么当核算好长度之后，return elementData = Arrays.copyOf(elementData, newCapacity)，即得到一个长度改变，元素类型和原数组相同的新数组。而当该数组不满意oldCapacity > 0 || elementData !=DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个条件时，进行数组的初始化。

增加元素

一个元素

　　//在尾部增加一个元素　　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));　　}

此处分为两个部分，一是向尾部增加一个元素的add()，如上面所示，当size与elementData.length相等时，阐明数组中无剩下空间进行增加，故进行扩容操作。将你要增加的值放入elementData[s]即数组的尾部，然后将size加一，这儿的modCount是用来核算ArrayList中的结构性变化次数。

二是在指定方位增加元素的add()，如上面所示，首要对你想要增加的元素的方位进行断定

一堆元素

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;}

此处的删去是按照下标删，首要检查index是否合法，接着取到oldValue值也便是要删的元素值，然后调用fastRemove( )函数。在fastRemove里，首要自增modCount，再判别要删的元素是不是elemantData的第size个元素（也便是实际上的最终一个元素），假如是，不需求移动元素操作，直接赋值为null即可，不然，还需求将删去方位之后的元素都往前挪一位。

当然也有个删去指定元素的办法，具体如上面**public boolean remove(Object o)**所示。

一堆元素

//删去调集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;}

此处的关于多个元素的操作分为删去多个元素和保存多个元素，而这两个操作均需求调用 “batchRemove“ ，故进行关于其的具体剖析。

“batchRemove“ 首要进行了变量”r“的声明，接着是一段for循环，而不管是“removeAll”仍是“retainAll”都是from = 0 ，end = size，即自始至终用r作为索引遍历数组，当c.contains(es[r]) != complement时break出去。对于“removeAll”，其complement为false，故当c.contains(es[r])为true的时分退出循环，即c中包含es[r]，即找到了要删去的元素，此时的r为第一个要删去的元素的索引。以此类推，对于“retainAll”，r为要保存的第一个元素的索引。关于后边w的部分，w是第一个要删的元素索引，找到要保存的元素，则把索引w的元素赋值为此元素，再自增w。这样子r一遍遍历完结后，要保存的元素也都向前移动好了。最终再进行善后工作，具体代码如上所示，详细进程已做注释。

修正元素

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;
    }

修正元素部分也与之前迥然不同，首要对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;
    }

关于此处，首要是indexOf函数，便是依据元素找索引，调用”indexOfRange“，从左往右找，找到第一个索引就回来；在ArrayList中还有个lastIndexOf，与前面说到的查找正好相反，为从右往左找。

还有一些其他较为简略的函数，这儿就不一一列出了，下一篇试着剖析下迭代器。格式没怎么调。

以上便是Android开发中的部分技能点，属于数据结构与算法这块。Android开发需求进阶的东西有很多，咱们该怎么让进阶自己必须了解自己技能层在那个方位；Android开发进阶的技能点总结如下图：

总结

ArrayList总结

ArrayList的优点

ArrayList底层以数组完结，是一种随机拜访模式，再加上它完结了
RandomAccess接口，因而查找也便是get的时分十分快。
ArrayList在次序增加一个元素的时分十分便利，仅仅往数组里边增加了一个元素而已。
依据下标遍历元素，功率高
依据下标拜访元素，功率高
能够主动扩容，默许为每次扩容为本来的1.5倍

ArrayList的缺陷

刺进和删去元素的功率不高
依据元素的值查找元素的下标需求遍历整个元素数组，功率不高
线程不安全

Android开发数据结构与算法——ArrayList源码讲解

简介

ArrayList源码讲解

初始化

扩容

增加元素

一个元素

一堆元素

删去元素

一个元素

一堆元素

修正元素

查询元素

总结

ArrayList总结

ArrayList的优点

ArrayList的缺陷

作者信息

推广

Android开发数据结构与算法——ArrayList源码讲解

简介

ArrayList源码讲解

初始化

扩容

增加元素

一个元素

一堆元素

删去元素

一个元素

一堆元素

修正元素

查询元素

总结

ArrayList总结

ArrayList的优点

ArrayList的缺陷

相关文章

Android 架构师之路6 设计模式之工厂模式

探讨xCrash 和 Matrix 对于非耗时操作ANR的处理

决策树总结 – DecisionTreeClassifier(二)

Java 并发编程解析 | 基于 JDK 源码解析 Java 领域中 ReentrantLock 锁的设计思想与实现原理

作者信息

推广