ArrayList源码分析：数据结构

ArrayList源码分析：数据结构

• ArrayList为什么建议初始化就声明大小？
• 数据结构
• 常规操作时间复杂度
• • 插入
  • 删除
  • 查询
• 源码分析
• • 初始化
  • add[根据下标插入]：arraycopy
  • remove[根据下标删除]：arraycopy
  • arraycopy：复制当前数组，根据偏移量移动
  • • arraycopy：时间复杂度
  • get查询和set替换
  • • get/set时间复杂度
  • 扩容源码分析
  • • 初始化ArrayList的代码
    • ArrayList底层源码逻辑
    • • 相关变量声明
      • 添加的两种方式
      • 判断是否是为声明大小的数组和判断扩容
      • ArrayList扩容grow()
      • grow()调用Arrays.copyOf()扩容：arraycopy
• ArrayList源码，jdk1.8

ArrayList为什么建议初始化就声明大小？

ArrayList底层是基于数组的，数组属于线性表，线性表的通病就是插入删除时间复杂度O(n)，查询和修改O(1)。

ArrayList不声明大小，会在首次执行add的时候进行扩容到10，之后每次超出每次扩容，而扩容grow()调用Arrays.copyOf()进行扩容，底层是System.arraycopy，arraycopy复制当前数组，根据偏移量移动，arraycopy这样做，时间复杂度是O(n)，因此一般采取声明大小来避免ArrayList扩容出现。

数据结构

是基于数组来定义的，线性表的一种数据结构

常规操作时间复杂度 插入

是插入，不是替换，是需要往后移的插入
时间复杂度：
(1+2+3+…+n) / n = n(n+1) / 2n = n/2+1/2 = O(n)

最好情况，末位插入，1次，O(1)
最坏情况，首位插入，n次，O(n)

删除

和插入一样的逻辑
时间复杂度：
(1+2+3+…+n) / n = n(n+1) / 2n = n/2+1/2 = O(n)

最好情况，末位删除，1次，O(1)
最坏情况，首位删除，n次，O(n)

查询

根据下标index去查：O(1)
根据value的值去查：O(n)

源码分析 初始化

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;//Object数组

//无参构造
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//有参构造
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);
    }
}

add[根据下标插入]：arraycopy

是插入，不是替换，是需要往后移的插入

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

remove[根据下标删除]：arraycopy

public E remove(int index) {
    rangeCheck(index);

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

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

arraycopy：复制当前数组，根据偏移量移动

arraycopy这样做，当然插入的效率就比较低

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

arraycopy：时间复杂度

(1+2+3+…+n) / n = n(n+1) / 2n = n/2+1/2 = O(n)

最好情况，末位插入，1次，O(1)
最坏情况，首位插入，n次，O(n)

get查询和set替换

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

public E set(int index, E element) {
    rangeCheck(index);

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

get/set时间复杂度

直接根据index去找值，没有任何遍历操作，因此时间复杂度是O(1)

扩容源码分析 初始化ArrayList的代码

//不声明ArrayList大小
ArrayList