面试中的ArrayList和LinkedList

ArrayList

掌握扩容机制，首次扩容为 10，再次扩容为原 1.5 倍

ArrayList 的构造函数，在 jdk1.8 中，ArrayList 有三种方式来初始化

• 无参构造，创建空数组
• 带初始容量的有参构造
• 带 collection 集合的有参构造

/**
  * 默认初始容量大小
  */
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
  *默认构造函数，使用初始容量10构造一个空列表(无参数构造)
  */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
  *带初始容量参数的构造函数。
  */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {//初始容量大于0
        //创建initialCapacity大小的数组
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {//初始容量等于0
        //创建空数组
        this.elementData = EMPTY_ELEMENTDATA;
    } else {//初始容量小于0，抛出异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
/**
  *构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
  *如果指定的集合为null，throws NullPointerException。
  *Arrays.copyOf()后面说
  */
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

以无参数构造创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正添加元素（add）操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10。

jdk1.7 无参构造创建 ArrayList 对象时，直接创建了长度是10的 Object[] 数组 elementData 。jdk7中的 ArrayList 的对象的创建类似于单例的饿汉式，而 jdk8 中的 ArrayList 的对象的创建类似于单例的懒汉式。

/**
  * 将指定的元素追加到此列表的末尾。
  */
public boolean add(E e) {
    //添加元素之前，先调用ensureCapacityInternal
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //这里看到ArrayList添加元素的实质就相当于为数组赋值
    elementData[size++] = e;
    return true;
}
//jdk7 得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 获取默认的容量和传入参数的较大值
        // 当要add第1个元素时，minCapacity为1，在Math.max()方法比较后，minCapacity为10。
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    // 10-0>0 扩容
    if (minCapacity - elementData.length > 0)
        //调用grow方法进行扩容，调用此方法代表已经开始扩容了
        grow(minCapacity);
}

JDK11 移除了 ensureCapacityInternal() 和 ensureExplicitCapacity() 方法

grow() 扩容

/**
  * Integer.MAX_VALUE - 8 可以避免一些内存溢出
  */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
  * ArrayList扩容的核心方法。
  */
private void grow(int minCapacity) {
    // oldCapacity 为旧容量，newCapacity 为新容量
    int oldCapacity = elementData.length;
    //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
    //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量大于 MAX_ARRAY_SIZE，执行 hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE
    // 如果 minCapacity 大于 MAX_ARRAY_SIZE，则新容量则为 Integer.MAX_VALUE，否则：新容量大小则为 MAX_ARRAY_SIZE，即 Integer.MAX_VALUE - 8
    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);
}
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //对minCapacity和MAX_ARRAY_SIZE进行比较
    //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
    //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

扩容 1.5 倍后的容量不够用时，就直接使用需要的最小容量。如果新容量(扩容1.5倍)后的结果超过 MAX_ARRAY_SIZE，那就不去扩容1.5倍了，而是去拿目前需要的容量来跟 MAX_ARRAY_SIZE 比较，没超过就用 MAX_ARRAY_SIZE，超过就用 Integer.MAX_VALUE，因此 ArrayList 最大容量其实是 Integer.MAX_VALUE。

Arrays.copyOf() 方法

public static int[] copyOf(int[] original, int newLength) {
    // 申请一个新的数组
    int[] copy = new int[newLength];
    // 调用System.arraycopy,将源数组中的数据进行拷贝,并返回新的数组
    System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
    return copy;
}

System.arraycopy() 方法

// arraycopy 是一个 native 方法
/**
  * 复制数组
  * @param src 源数组
  * @param srcPos 源数组中的起始位置
  * @param dest 目标数组
  * @param destPos 目标数组中的起始位置
  * @param length 要复制的数组元素的数量
  */
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

题外话：ArrayList 源码中有一个 ensureCapacity() 方法，能让你提前扩容容量，在增加大量数据前调用它，可以减少一定的时间消耗。

/**
  *
  * @param minCapacity 所需的最小容量
  */
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

LinkedList

掌握 LinkedList 和 ArrayList 比较

LinkedList

1. 基于双向链表，无需连续内存
2. 随机访问慢（要沿着链表遍历）
3. 头尾插入删除性能高
4. 占用内存多

ArrayList

1. 基于数组，需要连续内存
2. 随机访问快（指根据下标访问）
3. 尾部插入、删除性能可以，其它部分插入、删除都会移动数据，因此性能会低
4. 可以利用 cpu 缓存，局部性原理

补充：

同样在中间位置插入元素，LinkedList 的速度简直不敢恭维，因为它去查询到该位置就已经消耗了很多时间。

下面的言论是不准确的，必须纠正的是，查询的意思是查询某个元素，而不是随机访问，对于随机访问确实是 ArrayList 快，但对于查询来说事实上他们两者都不太适合用来查询，选择一种更高效的数据结构例如 HashMap、TreeMap 更好。