ArrayList 与 LinkedList 的实现和区别

ArrayList 的实现

ArrayList 底层是通过数组实现的，其数据保存在 transient Object[] elementData; List 接口主要特性就是长度可变，数组在创建的时候必须要指定其大小，那么基于数组实现无法直接达到长度可变。

通过构造方法参数 initialCapacity 来创建默认大小的 ArrayList，如果使用无参构造方法或者指定 initialCapacity 为 0 创建对象，则 ArrayList 会在第一次 add 时将容器 capacity初始化为 10 这样的做有几个好处：

• 延迟初始化数组有益于避免空 List 的空间浪费。
• 长度为 10 可以有效减少初期频繁的扩容操作。（若默认长度为 0 add 10 次需要扩容的次数比较频繁）

确定 ArrayList 的大小可以避免很多扩容操作，也能有效减少空间/内存浪费，所以在使用 ArrayList 时要尽量确认目标大小。

可以通过trimToSize方法去掉浪费掉的空间

ArrayList 可以通过元素下标直接获得，随机访问时间复杂度O(1) 假设 ArrayList 的大小初始化为 10 不过并未添加任何元素，此时访问任意下标的元素会抛出 IndexOutOfBoundsException 异常，也就是下标越界，可见 ArrayList 是根据实际元素长度来界定是否越界的。

ArrayList 随机删除元素需要将数组内元素进行移位来保证元素连续，时间复杂度为 O(n) 如果移除的是最后一位元素时间复杂度则为 O(1)，移除的操作实际上是将指定下标赋值为 null 并更新 size，删除元素并不需要创建新的数组，也不需要进行缩容。其中 fastRemove 的私有方法不会访问元素，而remove需要返回被移除的元素，需要访问数组内元素。

1. 为什么 elementData 修饰为transient ？
2. ArrayList 是泛型对象为什么 elementData 不使用泛型而使用 Object？
3. ArrayList 是如何达到长度可变的（扩容）？
4. ArrayList 可以无限添加数据吗？
5. ArrayList 可以 add null 吗？
6. modCount的作用是什么？

为什么 elementData 修饰为transient ？

被transient关键字修饰的成员不能参与序列化和反序列化。由于数组实现原因直接序列化可能存在空间浪费，ArrayList 提供了支持序列化和反序列化的两个方法 writeObject 和 readObject
工作方式：https://www.jianshu.com/p/14876ef38721

ArrayList 是泛型对象为什么 elementData 不使用泛型而使用 Object？

因为 Java 中不能直接 E[] data = new E[1] 创建所谓的泛型数组，可能是遗留问题？
why-does-arraylist-use-object-instead-of-e-internally
Why does the ArrayList implementation use Object[]?

ArrayList 是如何达到长度可变的？

ArrayList 通过创建一个大于现有数组长度的数组，并将原数组数据按顺序拷贝到新数组变相完成长度可变的。

在调用 add 方法时首先会确认目标大小是否大于数组长度，如果小于直接数组末尾插入 elementData[size++] = e; 注意此处会首先确定数组下标再进行自增；如果目标大小无法满足，将会进行扩容操作，因为数组一旦创建长度就确定了，所以扩容实际就是创建一个新的数组将现有数据拷贝过去，来看一下源码：

    /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        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);
    }

通过上方代码可得知，新数组长度为原数组的 1.5 倍，int newCapacity = oldCapacity + (oldCapacity >> 1); 也就是扩容 50%

ArrayList 可以无限添加数据吗？

不能，ArrayList 内部是存在长度限制的，在 ArrayList 扩容机制里，如果新的数组长度大于 MAX_ARRAY_SIZE 没有超过 Integer 最大值之前可以继续添加，否则将抛出 OOM 异常。

为什么 MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

Why the maximum array size of ArrayList is Integer.MAX_VALUE - 8?

ArrayList 可以 add null 吗

可以。

List<Integer> list = new ArrayList<>();
list.add(null);
list.add(null);

modCount的作用是什么

在操作（添加，删除，排除等） ArrayList 时经常出现 modCount 成员变量，其主要作用是为了检测和判定在使用迭代器迭代过程中的 ArrayList 操作不当引起的迭代器游标异常。
modCount 并非仅检测多线程环境下的异常，个人认为主要还是因为在迭代器场景中错误删除等操作，导致迭代器游标未能按照预期结果进行引入的机制。ArrayList 本身就是非线程安全的，切勿在线程竞争的环境下使用。

单线程环境下，下方代码会抛出 ConcurrentModificationException 异常。

public class TestArrayListIterator {
    public static void main(String[] args)  {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(10);
        Iterator<Integer> iterator = list.iterator();
        while(iterator.hasNext()){
            Integer integer = iterator.next();
            if(integer==10)
                list.remove(integer);   //注意这个地方
        }
    }
}

arraylist等记录修改次数modCount有什么作用？ - wuxinliulei的回答 - 知乎
https://www.zhihu.com/question/24086463/answer/64717159

迭代器提供了安全的删除元素的remove方法。

LinkedList 实现

LinkedList 由双向链表实现，保存了 first 和 last 指针，同时实现了 List 和 Deque 接口。由于链表的特性LinkedList原生支持 List 变长特性，LinkedList 支持变相通过下标访问元素，其实现方式是通过遍历链表访问元素的。LinkedList 每一个元素都需要保存 pre 和 next 指针来维持其链表特性，在内存使用上会有所增加。

LinkedList add操作仅需要在尾部链接元素即可，时间复杂度O(1)
LinkedList remove操作非常快速，在查找到元素只需将前一个元素与后一个元素链接即可

1. LinkedList 长度是无限的吗 ？

LinkedList 长度是无限的吗 ？

查看源码后，LinkedList 内部对长度并没有限制，但是记录容器大小 size 可能会溢出，从而导致相关下标访问操作异常。

    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

LinkedList 和 ArrayList 的区别

• ArrayList 的变长能力是通过创建更大的数组实现的
• LinkedList 的变长能力通过链表实现

• ArrayList 可以初始化容器长度
• LinkedList 无法初始化容器长度

• ArrayList 在实现上长度是有限制的
• LinkedList 在实现上是没有长度限制的，但是无限的长度会导致 int size 溢出，依赖 size 的相关方法可能出现异常。
• 在 List 接口 int size() 可以看出两者都受限于 int 最大值，List 接口对长度是有限制的。

• ArrayList 随机查找能力非常强时间复杂度 O(1)
• LinkedList 随机查找能力相较 ArrayList 弱，其具体算法为不是从头遍历到尾，而是通过下标确定从哪个方向开始遍历 index < (size >> 1) 如果小于 mid 则从头部开始，否则从尾部倒序遍历。

• ArrayList 的插入删除操作理论上时间复杂度较高

• LinkedList 的插入删除操作理论性能优于 ArrayList

• 对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。

• 根据场景的不同，ArrayList 和 LinkedList 并不完全与理论一致。http://blog.sina.com.cn/s/blog_3df05c220102ycq8.html

• ArrayList 和 LinkedList 都使用 transient 关键字修饰了容器数据，通过 writeObject 和 readObject进行序列化和反序列

• ArrayList 和 LinkedList 对 Itertor 添加了 modCount 检查支持，防止异常操作。