ArrayList

数据结构

底层数据接口是根据动态数组存储数据，根据System.arraycopy()方法去动态扩容。

ArrayList和LinkedList对比

因为底层数据结构是数组，所以获取元素的很快，但新增元素或删除元素时，如果涉及到数组拷贝则效率会很慢，所以在使用时最好指定数组的长度，防止频繁的进行数组的拷贝，如果频繁的进行删除和新增则可以使用LindekList进行存储数据，因为LinkedList底层是双向链表，只需要改变上一个元素或下一元素的指向则可进行删除和新增，效率会比ArrayList更高

因为底层数据结构的不同，占用的空间会小于LinkedList 但ArrayList每次扩容大小都是当前数组长度的1.5倍，所以会浪费内存空间

所以如果你对内存占用敏感并且频繁访问元素，ArrayList 可能是更好的选择。如果你频繁插入和删除元素，尤其是在中间位置，LinkedList 会更适合

核心字段

字段 含义 代码
DEFAULT_CAPACITY 默认大小 private static final int DEFAULT_CAPACITY = 10
elementData 数据存储 transient Object[] elementData
size 数组大小 private int size
DEFAULTCAPACITY_EMPTY_ELEMENTDATA 用于默认大小的空实例的共享空数组实例 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

构造方法

  • 无参构造方法

    1
    2
    3
    4
    5
    6
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

  • 指定数组长度的构造方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    /**
      * Constructs an empty list with the specified initial capacity.
      *
      * @param  initialCapacity  the initial capacity of the list
      * @throws IllegalArgumentException if the specified initial capacity
      *         is negative
      */
     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);
         }
     }

  • 根据传入的集合去构造方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection<? extends E> c) {
        Object[] a = c.toArray();
        if ((size = a.length) != 0) { // 判断是否是空数组
            if (c.getClass() == ArrayList.class) {
                elementData = a; // 如果类型是ArryList则直接指向
            } else {
                elementData = Arrays.copyOf(a, size, Object[].class); // 如果不是则进行拷贝
            }
        } else {
            // replace with empty array. 如果是空数组则默认为{}
            elementData = EMPTY_ELEMENTDATA; 
        }
    }

添加元素

  • 在行尾添加元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

  • 在指定下标添加元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    /**
     * Inserts the specified element at the specified position in this
     * list. Shifts the element currently at that position (if any) and
     * any subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        rangeCheckForAdd(index); // 判断添加的下标是否大于数组长度，如果大于则抛出IndexOutOfBoundsException数组下标越界的异常
        modCount++; // 操作次数+1
        final int s;
        Object[] elementData;
        if ((s = size) == (elementData = this.elementData).length)
            elementData = grow(); // 扩容大小：1
        System.arraycopy(elementData, index,
                         elementData, index + 1,
                         s - index); //指定下标后的元素下标往后移动一位
        elementData[index] = element; // 在指定下标添加元素
        size = s + 1; // 数组大小+1
    }

  • 添加集合

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    /**
     * Appends all of the elements in the specified collection to the end of
     * this list, in the order that they are returned by the
     * specified collection's Iterator.  The behavior of this operation is
     * undefined if the specified collection is modified while the operation
     * is in progress.  (This implies that the behavior of this call is
     * undefined if the specified collection is this list, and this
     * list is nonempty.)
     *
     * @param c collection containing elements to be added to this list
     * @return {@code true} if this list changed as a result of the call
     * @throws NullPointerException if the specified collection is null
     */
    public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        modCount++; // 操作次数+1
        int numNew = a.length; // 获取传入的数组长度
        if (numNew == 0)  
            return false;// 如果为空返回false
        Object[] elementData;
        final int s;
        if (numNew > (elementData = this.elementData).length - (s = size))
            elementData = grow(s + numNew); // 如果传入的数组大小大于当前数组的长度（总长度-实际长度）则数组扩容
        System.arraycopy(a, 0, elementData, s, numNew); // 将传入的数组拷贝到队尾中
        size = s + numNew; // 当前数组大小加上传入数组的大小
        return true;
    }

  • 在指定下标添加集合元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    /**
     * Inserts all of the elements in the specified collection into this
     * list, starting at the specified position.  Shifts the element
     * currently at that position (if any) and any subsequent elements to
     * the right (increases their indices).  The new elements will appear
     * in the list in the order that they are returned by the
     * specified collection's iterator.
     *
     * @param index index at which to insert the first element from the
     *              specified collection
     * @param c collection containing elements to be added to this list
     * @return {@code true} if this list changed as a result of the call
     * @throws IndexOutOfBoundsException {@inheritDoc}
     * @throws NullPointerException if the specified collection is null
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index); // 判断添加的下标是否大于数组长度，如果大于则抛出IndexOutOfBoundsException数组下标越界的异常

        Object[] a = c.toArray();
        modCount++; // 操作次数+1
        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); // 如果传入的数组大小大于当前数组的长度（总长度-实际长度）则数组扩容.扩容的大小=（当前数组长度+传入的数组长度）*1.5

        int numMoved = s - index; // 需要移动下标的大小
        if (numMoved > 0)
            System.arraycopy(elementData, index,
                             elementData, index + numNew,
                             numMoved); // 将传入的下标后的元素后移numMoved大小
        System.arraycopy(a, 0, elementData, index, numNew); // 数组拷贝
        size = s + numNew;   // 当前数组长度+传入的数组长度
        return true;
    }

删除元素

  • 根据元素删除

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
     /**
      * Removes the first occurrence of the specified element from this list,
      * if it is present.  If the list does not contain the element, it is
      * unchanged.  More formally, removes the element with the lowest index
      * {@code i} such that
      * {@code Objects.equals(o, get(i))}
      * (if such an element exists).  Returns {@code true} if this list
      * contained the specified element (or equivalently, if this list
      * changed as a result of the call).
      *
      * @param o element to be removed from this list, if present
      * @return {@code true} if this list contained the specified element
      */
     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(es, i); // 根据下标删除数据（只删除第一个找到的元素，如果有多个相同元素，则不会全部删除）
         return true;
     }
      
    /**
      * Private remove method that skips bounds checking and does not
      * return the value removed.
      */
     private void fastRemove(Object[] es, int i) {
         modCount++; // 操作次数+1
         final int newSize;
         if ((newSize = size - 1) > i) // 如果不是队尾元素则将将指定下标处的元素网球移动一位
             System.arraycopy(es, i + 1, es, i, newSize - i);
         es[size = newSize] = null; // 删除元素后，将数组末尾的元素置为 null
     }

  • 根据下标删除元素

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to be removed
     * @return the element that was removed from the list
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public E remove(int index) {
        Objects.checkIndex(index, size);  // 判断是否下标越界，如果越界则抛出数组下标越界的异常 IndexOutOfBoundsException
        final Object[] es = elementData;

        @SuppressWarnings("unchecked") E oldValue = (E) es[index]; // 根据删除坐标获取删除元素的内容
        fastRemove(es, index); // 调用的方法和根据元素删除的调用的方法一致

        return oldValue; // 返回删除元素的内容
    }

  • 根据下标范围批量删除元素 （待补充）

  • 根据传入的集合元素批量删除 （待补充）

动态扩容

System.arraycopy()

简介

arraycopy是java.lang.system类下方法

源码

1
2
public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos,
int length);

参数简介

参数 数据结构 含义
length int 要复制的数组元素的数量，一般为src.length-srcPos
src Object 源数组
srcPos int 从源数组的该下标之后开始拷贝
dest int 目标数组
destPos Object 从目标数组的该下标之后替换为源数据的数据

代码示例

1
2
3
4
5
6
7
public static void main(String[] args) {
    Object[] obj = {1, 2, 3, 4, 5};
    Object[] obj1 = {11, 22, 33, 44, 54, null, null, null};
    int srcPos = 4;
    System.arraycopy(obj, srcPos, obj1, 5, obj.length - srcPos);
    System.out.println(Arrays.toString(obj1));
}

源码

1
2
3
4
5
6
7
8
9
10
11
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 根据当前数组的长度扩容1.5倍*/);
        return elementData = Arrays.copyOf(elementData, newCapacity);
    } else {
        return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];// 设置默认大小为10
    }
}

流程图