LinkedList与ArrayList的比较

1.LinkedList

1. 基于双向链表，无需连续内存

2. 随机访问慢（要沿着链表遍历）

3. 头尾插入删除性能高

4. 占用内存多

2.ArrayList

1. 基于数组，需要连续内存

2. 随机访问快（指根据下标访问）

3. 尾部插入、删除性能可以，其它部分插入、删除都会移动数据，因此性能会低

4. 可以利用 cpu 缓存，局部性原理

3.查询比较

? ? ? ? 在图上可以看到，ArrayList是内存地址是连续的，而LinkedList不是连续的，通过当前节点保存的下一个节点的位置（LinkedList底层是基于双向链表实现的）。所以，ArrayList 的随机读取速度快，而LinkedList需要一个一个的向后遍历知道遍历到所需元素。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}

????????可以发现，ArrayList实现了RandomAccess接口，代表了ArrayList支持随机访问。这个接口的作用仅仅是一个标记，当使用到ArrayList时，Java的底层类库发现了RandomAccess接口，就说明可以支持根据索引随机访问存储，否则就只能使用迭代器进行遍历。

为什么要使用可序列化

这里有一个小知识点，也就是我们经常可以看到一些类中实现了可序列化接口Serializable

序列化：将 Java 对象转换成字节流的过程。

反序列化：将字节流转换成 Java 对象的过程。

当 Java 对象需要在网络上传输 或者 持久化存储到文件中时，就需要对 Java 对象进行序列化处理。

序列化的实现：类实现 Serializable 接口，这个接口没有需要实现的方法。实现 Serializable 接口是为了告诉 jvm 这个类的对象可以被序列化。

注意事项：

某个类可以被序列化，则其子类也可以被序列化
声明为 static 和 transient 的成员变量，不能被序列化。static 成员变量是描述类级别的属性，transient 表示临时数据
反序列化读取序列化对象的顺序要保持一致

4.增删比较

? ? ? ? 我们通常说ArrayList增删慢、查询快，LinkedList增删快、查询慢。其实这种说法仅仅是在初学的时候加强记忆用的，并不是完全准确的。我们说查询，是根据元素的内容去查找元素的位置，如果是使用从头往后遍历的话，ArrayList和LinkedList的时间复杂度是相同的。

? ? ? ? ArrayList在中间位置添加新元素时，会把当前位置和位置后边的所有元素复制一份，然后向后移动一位，再将新元素插入进去。越靠近头部插入，需要移动的元素越多，也就越影响性能。

• 在头部插入时，ArrayList比LinkedList慢（ArrayList需要复制元素
• 在尾部插入时，ArrayList比LinkedList快（差不多，略快
• 在中间插入时，ArrayList比LinkedList快的多！！！

? ? ? ? 这个时候我们会想，在中间插入的时候，链表不应该比数组插入快的多吗？为什么会出现这样的情况。因为在中间部分插入时，首先要寻找到这个地方。而ArrayList是支持随机访问的！LinkedList则只能一个一个遍历到中间位置所以消耗的时间也就越多。

? ? ? ? 所以我们一般使用ArrayList而LinkedList使用的较少。

5.空间占用

? ? ? ? ArrayList可以利用 cpu 缓存，局部性原理来加快计算效率,而LinkedList因为不是一片连续的内存，所以不能使用，而且LinkedList占用的内存多（其中每个节点需要存储前后节点的位置）。

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