ArrayList 和 LinkedList

ArrayList

ArrayList是List接口的一个实现类，底层是基于数组实现的存储结构，可以用于装载数据，数据都是存放到一个数组变量中;关键知识点：
1、新建一个实例，默认的容量大小

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

2、动态扩容：
如果发现新增数据后，List的大小已经超过数组的容量的话，就会新增一个为原来1.5倍容量的新数组，然后把原数组的数据原封不动的复制到新数组中，再把新数组赋值给原来的数组对象就完成了。
3、插入数据
ArrayList提供支持指定index新增的方法，就是可以把数据插入到设定的索引下标，比如说我想把元素4插入到3后面的位置，也就是现在5所在的地方，

image.png

优缺点：

• 这种基于数组的查询很高效，但增删数据的时候却很耗性能，因为每增删一个元素就要移动对应index后面的所有元素，数据量少点还无所谓，但如果存储上千上万的数据就很吃力了，所以，如果是频繁增删的情况，不建议用ArrayList。

LinkedList

LinkedList 是基于双向链表实现的，不需要指定初始容量，链表中任何一个存储单元都可以通过向前或者向后的指针获取到前面或者后面的存储单元
存储单位Node

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

因为有保存前后节点的地址，LinkedList增删数据的时候不需要像ArrayList那样移动整片的数据，只需要通过引用指定index位置前后的两个节点即可。
删除数据也是同样原理，只需要改变index位置前后两个节点的指向地址即可。

虽然增删数据很快，但查询就不怎么样了，LinkedList是基于双向链表存储的，当查询对应index位置的数据时，会先计算链表总长度一半的值，判读index是在这个值的左边还是右边，然后决定从头结点还是从尾结点开始遍历，

Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

虽然根据index位置做了查询优化，但依然会有遍历一半链表长度的情况，如果是数据量非常多的话，这样的查询无疑是非常慢的。一般建议LinkedList使用于增删多，查询少的情景。

LinkedList 和 ArrayList 那个更占空间

一般情况下，LinkedList的占用空间更大，因为每个节点要维护指向前后地址的两个节点，但也不是绝对，如果刚好数据量超过ArrayList默认的临时值时，ArrayList占用的空间也是不小的，因为扩容的原因会浪费将近原来数组一半的容量，不过，因为ArrayList的数组变量是用transient关键字修饰的，如果集合本身需要做序列化操作的话，ArrayList这部分多余的空间不会被序列化。

ArrayList 增删数据，如何优化

如果频繁的增删数据，不建议使用ArrayList ，如果作为一道面试题的话，可以考虑优化--jvm的 标记.清除算法

参考文档