Java集合框架之LinkedList浅析

一、LinkedList综述：

1.1LinkedList简介

• 同ArrayList一样，位于java.util包下的LinkedList是Java集合框架的重要组成成员之一，LinkedList在jdk1.8中的定义如下：public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
• LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
• LinkedList 实现 List 接口，能对它进行队列操作。
• LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
• LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
• LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
• LinkedList 是非同步的。

1.2LinkedList的数据结构

LinkedList的继承关系

java.lang.Object

   ↳     java.util.AbstractCollection<E>

         ↳     java.util.AbstractList<E>

               ↳     java.util.AbstractSequentialList<E>

                     ↳     java.util.LinkedList<E>

public class LinkedList<E>

    extends AbstractSequentialList<E>

    implements List<E>, Deque<E>, Cloneable, java.io.Serializable {}

LinkedList与Collection关系如下图：

LinkedList的本质是双向链表。
(01) LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。
(02) LinkedList包含两个重要的成员：header 和 size。
　　header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。
　　size是双向链表中节点的个数。

(03) LinkedList 实际上是通过双向链表去实现的。

　　它包含一个非常重要的内部类：Entry。Entry是双向链表节点所对应的数据结构，它包括的属性有：当前节点所包含的值，上一个节点，下一个节点。
(04) 从LinkedList的实现方式中可以发现，它不存在LinkedList容量不足的问题。
(05) LinkedList的克隆函数，即是将全部元素克隆到一个新的LinkedList对象中。
(06) LinkedList实现java.io.Serializable。当写入到输出流时，先写入“容量”，再依次写入“每一个节点保护的值”；当读出输入流时，先读取“容量”，再依次读取“每一个元素”。
(07) 由于LinkedList实现了Deque，而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。每种方法都存在两种形式：一种形式在操作失败时抛出异常，另一种形式返回一个特殊值（null 或 false，具体取决于操作）。

总结起来如下表格：

        第一个元素（头部）                 最后一个元素（尾部）

        抛出异常        特殊值            抛出异常        特殊值

插入    addFirst(e)    offerFirst(e)    addLast(e)        offerLast(e)

移除    removeFirst()  pollFirst()      removeLast()    pollLast()

检查    getFirst()     peekFirst()      getLast()        peekLast()

(08) LinkedList可以作为FIFO(先进先出)的队列，作为FIFO的队列时，下表的方法等价：

队列方法       等效方法

add(e)        addLast(e)

offer(e)      offerLast(e)

remove()      removeFirst()

poll()        pollFirst()

element()     getFirst()

peek()        peekFirst()

(09) LinkedList可以作为LIFO(后进先出)的栈，作为LIFO的栈时，下表的方法等价：

栈方法        等效方法

push(e)      addFirst(e)

pop()        removeFirst()

peek()       peekFirst()

二、LinkedList与ArrayList对比：

1、顺序插入速度ArrayList会比较快，因为ArrayList是基于数组实现的，数组是事先new好的，只要往指定位置塞一个数据就了；LinkedList则不同，每次顺序插入的时候LinkedList将new一个对象出来，如果对象比较大，那么new的时间势必会长一点，再加上一些引用赋值的操作，所以顺序插入LinkedList必然慢于ArrayList

2、基于上一点，因为LinkedList里面不仅维护了待插入的元素，还维护了Entry的前置Entry和后继Entry，如果一个LinkedList中的Entry非常多，那么LinkedList将比ArrayList更耗费一些内存

3、数据遍历的速度，使用各自遍历效率最高的方式，ArrayList的遍历效率会比LinkedList的遍历效率高一些

4、有些说法认为LinkedList做插入和删除更快，这种说法其实是不准确的：

（1）LinkedList做插入、删除的时候，慢在寻址，快在只需要改变前后Entry的引用地址

（2）ArrayList做插入、删除的时候，慢在数组元素的批量copy，快在寻址

　　所以，如果待插入、删除的元素是在数据结构的前半段尤其是非常靠前的位置的时候，LinkedList的效率将大大快过ArrayList，因为ArrayList将批量copy大量的元素；越往后，对于LinkedList来说，因为它是双向链表，所以在第2个元素后面插入一个数据和在倒数第2个元素后面插入一个元素在效率上基本没有差别，但是ArrayList由于要批量copy的元素越来越少，操作速度必然追上乃至超过LinkedList。

　　从这个分析看出，如果你十分确定你插入、删除的元素是在前半段，那么就使用LinkedList；如果你十分确定你删除、删除的元素在比较靠后的位置，那么可以考虑使用ArrayList。如果你不能确定你要做的插入、删除是在哪儿呢？那还是建议你使用LinkedList吧，因为一来LinkedList整体插入、删除的执行效率比较稳定，没有ArrayList这种越往后越快的情况；二来插入元素的时候，弄得不好ArrayList就要进行一次扩容，记住，ArrayList底层数组扩容是一个既消耗时间又消耗空间的操作

　　最后一点，一切都是纸上谈兵，在选择了List后，有条件的最好可以做一些性能测试，比如在你的代码上下文记录List操作的时间消耗。

三、LinkedList方法摘要：

参考：

　　https://www.cnblogs.com/skywang12345/p/3308807.html#a1

　　https://www.cnblogs.com/xrq730/p/5005347.html