介绍

LinkedList同时实现了List接口和Deque对口，也就是收它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（stack），这样看来，linkedList简直就是无敌的，当你需要使用栈或者队列时，可以考虑用LinkedList,一方面是因为Java官方已经声明不建议使用Stack类，更遗憾的是，Java里根本没有一个叫做Queue的类（只是一个接口的名字）。关于栈或队列，现在首选是ArrayDeque，它有着比LinkedList（当作栈或队列使用时）更好的性能。

LinkedList的实现方式决定了所有跟下表有关的操作都是线性时间，而在首段或者末尾删除元素只需要常数时间。为追求效率LinkedList没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。

继承体系

LinkedList 的继承体系较为复杂，继承自 AbstractSequentialList，同时又实现了 List 和 Deque 接口。

LinkedList 继承自 AbstractSequentialList，AbstractSequentialList 又是什么呢？从实现上，AbstractSequentialList 提供了一套基于顺序访问的接口。通过继承此类，子类仅需实现部分代码即可拥有完整的一套访问某种序列表（比如链表）的接口。深入源码，AbstractSequentialList 提供的方法基本上都是通过 ListIterator 实现的，比如：

所以只要继承类实现了listIterator方法，它不需要再额外实现什么即可使用。对于随机访问集合类一般建议继承AbstractList而不是AbstractSequentialList。LinkedList和其他父类一样，也是基于顺序访问。所以LinkedList继承了AbstractSequentialList，但LinkedList并没有直接使用父类的方法，而是重新实现了一套方法。
另外，LinkedList还实现了Deque（double ended queue）,Deque又继承自Queue接口。这样LinkedList就具备了队列的功能。比如：

Queue<T> queue = new LinkedList<>();

LinkedLists实现

底层数组结构

LinkedList底层通过双向链表实现，双向链表的每个节点用内部类Node表示。LinkedList通过first和last引用分别指向链表的第一个和最后一个元素。
在这里没有所谓的哑元，当链表为空的时候first和last都指向null。

其中Node是私有的内部类

构造函数

getFirst(),getLast()

获取第一个元素以及获取最后一个元素

removeFirest(),removeLast(),remove(e),remove(index)

remove()方法同样是有两个版本，一个是根据指定元素删除匹配相等的第一个元素remove(Object o),另一个是删除指定下标处的元素remove(int index)。

删除元素-指的是删除第一次出现的这个元素，如果没有这个元素，则返回false;判断的依据是equals方法，如果是equals,则直接unlink这个node;由于LinkedList可存放null元素，故也可以删除第一次出现null的元素；


remove(int index)使用的是下标计数，只需要判断该index是否有元素即可，如果有则直接unlink这个node。

删除head元素

删除last元素

add()

add()方法也有两个版本，一个add(E e)，该方法在LinkedList的末尾插入元素，因为有last指向链表末尾，在末尾插入元素的花费是常数时间，只需简单修改几个相关引用即可；另外一个add(int index,E e),该方法是在指定下标出插入元素，需要通过线性查找找到具体位置，然后修改相关引用完成插入操作。


add(int index,E e),当index==size时，等同于add(E e);如果不是，则需要分为两步：

• 现根据index找到要插入的位置，即node(index)方法；
• 修改引用，完成插入操作
  
  上面代码中的node(int index)函数有一点小trick,因为链表时双向的，可以从后往前找，也可以从前往后招，具体朝哪个方向取决于条件 index < (size >> 1) ，也就是index是靠近前端还是后端。从这里可以看出，linkedList通过index检查元素的效率没有arrayList高。
  
  
  

LinkedList新增元素的逻辑流程
（1）创建新节点，并指明新节点的前驱和后继
（2）将succ的前驱引用指向新节点
（3）如果succ的前驱不为空，则将succ前驱的后继引用指向新节点

addAll()

addAll(index,c)实现方式并不是直接调用add(index,e)实现的，主要是因为效率问题，另一个就是fail-fast中modCount只会增加1次；

clear()

为了让GC更快可以回收放置的元素，需要将node之间的引用关系赋空

查找操作

LinkedList 底层基于链表结构，无法向 ArrayList 那样随机访问指定位置的元素。LinkedList 查找过程要稍麻烦一些，需要从链表头结点（或尾节点）向后查找，时间复杂度为 O(N)。

主要是通过遍历的方式定位目标位置的节点。获取到节点后，取出节点存储的值返回即可。这里面有个小优化，即通过比较 index 与节点数量 size/2 的大小，决定从头结点还是尾节点进行查找。

遍历

链表的遍历过程也很简单，和上面查找过程类似，我们从头节点往后遍历就行了。但对于 LinkedList 的遍历还是需要注意一些，不然可能会导致代码效率低下。通常情况下，我们会使用 foreach 遍历 LinkedList，而 foreach 最终转换成迭代器形式。所以分析 LinkedList 的遍历的核心就是它的迭代器实现。


TIP：LinkedList不擅长随机位置访问，如果使用随机访问遍历LinkedList效率会很差，如下：