ArrayList && LinkedList

ArrayList

一、概述：

继承了AbstractList，实现了List接口，它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能
除了列表接口外，该类提供了一种方法来操作该数组的大小来存储该列表中的数组的大小
实现Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输

1. 时间复杂度：

ArrayList 实现了RandomAccess 接口，即提供了随机访问功能
方法size、isEmpty、get、set、iterator和listIterator的调用是常数时间的。
添加删除的时间复杂度为O(N)。其他所有操作也都是线性时间复杂度。

2. 容量：

每个ArrayList都有容量，容量大小至少为List元素的长度，默认初始化为10, 容量可以自动增长.
如果提前知道数组元素较多，可以在添加元素前通过调用ensureCapacity()方法提前增加容量以减小后期容量自动增长的开销。
也可以通过带初始容量的构造器初始化这个容量。

3. 线程不安全：

ArrayList不是线程安全的，在多线程中可以选择 Vector或者 CopyOnWriteArrayList，用Collections.synchronizedList把一个普通ArrayList包装成一个线程安全版本的数组容器也可以

二、LinkedList

底层使用双向链表实现、保留了头尾两个指针、LinkedList的其他操作

ArrayList和LinkedList的区别

LinkedList 实现了 List 和 Deque 接口，一般称为双向链表；ArrayList 实现了 List 接口，动态数组；
LinkedList 在插入和删除数据时效率更高，ArrayList 在查找某个 index 的数据时效率更高；
LinkedList 比 ArrayList 需要更多的内存, 因为需要维护前后两个指针

三、思考

1. ArrayList插入删除一定慢么？

不一定，取决于插入删除的位置离数组末端有多远，比如刚好插入到尾部，那时间复杂度就是 O(1)

2. ArrayList的遍历和LinkedList遍历性能比较如何?

论遍历的话ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销

3. ArrayList是如何扩容的?

拿添加元素来说，首先calculateCapacity()方法计算所需容量，ensureExplicitCapacity方法内部调用 grow 方法进行扩容，grow方法具体实现:

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 扩容到原来容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 判断扩容后是否足够，不够的话就直接使用 minCapacity 作为容量大小
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 若预设值大于默认最大值检查是否溢出
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 将数组指向 newCapacity 新的连续内存空间并拷贝数据
    elementData = Arrays.copyOf(elementData, newCapacity);
}

4. ArrayList的默认最大数组大小为什么是`Integer.MAX_VALUE - 8`?

数组对象有一个额外的元数据，用于表示数组的大小, 需要额外的 8 bytes存储这部分元数据

5. ArrayList是线程安全的么？

ArrayList不是线程安全的，在多线程中可以选择 Vector或者用Collections.synchronizedList把一个普通ArrayList包装成一个线程安全版本的数组容器,原理类似，都是直接用synchronized加锁. CopyOnWriteArrayList是线程安全的，是一种读写分离的机制实现，适用于读多写少的场景，原理参考: CopyOnWriteArrayList实现原理及源码分析

6. 数组用来做队列合适么？

队列一般是FIFO的，如果用ArrayList做队列，就需要在数组尾部追加数据，数组头部删除数组，反过来也可以。但是无论如何总会有一个操作会涉及到数组的数据搬迁，这个是比较耗费性能的。
但是定长数组却是很合适的，比如ArrayBlockingQueue内部实现就是一个环形队列，它是一个定长队列，内部是用一个定长数组来实现的。另外著名的Disruptor开源Library也是用环形数组来实现的超高性能队列

7. Array 和 ArrayList 有什么区别？什么时候该应 Array 而不是 ArrayList 呢？

Array 可以包含基本类型和对象类型，ArrayList 只能包含对象类型。
Array 大小是固定的，ArrayList 的大小是动态变化的。
ArrayList 提供了更多的方法和特性，比如：addAll()，removeAll()，iterator() 等等

四、参考链接

坑人无数的Java面试题之ArrayList