集合9-LinkedList源码分析及使用

定义

1. LinkdList 继承了AbstractSequentialList，实现可随机访问的方法
2. LinkdList 实现了List和Deque接口的双向链接的列表，用于存储所有元素包括null元素。
3. LinkedList还实现了Cloneable和Serializable接口

下面将按照这1、2、3进行分析

0- 内部静态节点类

节点内除了保存节点上的对象，也保存了前后的节点的引用，可以从这了看出双向链表的定义。

1- 随机访问

LinkedList继承AbstractSequentialList，而AbstractSequentialList又拓展自AbstractList接口并实现了一部分相关的方法，所以LinkedList也就实现了随机访问的方法

接下来分析一下add方法的实现过程，来对随机访问的总体实现来管中窥豹

add

linkBefore

node

这是定位链表中指定位置节点的方法，可以看见的是，它是通过根据索引的大小来确定遍历的起始位置。
其他的随机访问和集合方法可以参考接口的实现集合1-Collection接口，集合2-List

2- 队列的实现方法

由于单向队列和双向队列在源码中实现比较简单，所以这里就不在赘述了，感兴趣的读者可以自行查看。详细的方法列表可见集合8-Queue和Deque接口

3- Cloneable克隆接口的实现

从实现上来看，clone方法实现的是浅拷贝，即双向链表的元素对象本身没有被克隆，只是将原来链表中所有元素的引用添加到从父类集成过来的LinkedList对象上。

4- Serializable序列化接口的实现

序列化方法

反序列化方法

** 集合的序列化反序列化方法都比较相似，一般都是将size序列化，然后再将所有元素序列化，同样反序列化也是类似的。**

4- LinkedList的使用

1. 当双向队列来使用

方法参见Deque的接口方法

1. 当List集合来使用

方法参见List的接口方法

1. 当单向队列来使用

方法参见Queue的接口方法

1. 当栈来使用

LinkedList对Stack包装的方法

可以看出，Stack栈顶位于链表的First节点，不同于java.util.Stack中位于Vector缓冲数组的末尾。

5- LinkedList的遍历

LinkedList支持多种遍历方式。建议不要采用随机访问的方式去遍历LinkedList，而采用按照链表顺序地逐个遍历的方式，因为从add方法可以看出，每一次随机查找都将遍历链表的一部分，所以效率很低