LinkedList源码分析

上次写了ArrayList的源码分析，本篇写一下ArrayList的同胞兄弟LinkedList.

简单介绍

LinkedList由名字可知是基于链表实现的，他实现了Dequeue与List接口，说明他同时具有List与双端队列的功能。因为是链表实现，所以相比ArrayList而言，增删只需要操作节点之间的引用关系即可，而数组却需要移动相应的元素，所以在增删上是要优于ArrayList的。然而查找性能的话ArrayList是要优于LinkedList的，因为数组内数据可随机访问，而链表内存地址不一定是连续的，必须通过上一节点才能访问下一节点的数据。

实例变量

可以看到LinkedList只有三个实例变量，分别为代表链表容量的size，指向首节点的first指针，指向尾节点的last指针。因为有首尾指针，所以我们可以知道LinkedList为双向链表。

节点类

节点类是链表的内部表示。其中的实例变量分别为代表着实际元素的item，上一个节点prev以及下一个节点next。LinkedList的所有操作都是基于node类来进行的。

内部辅助方法

LinkedList内部为了方便操作，编写了相关的辅助方法

由上至下依次为：将节点插入链表首，将节点插入到链表尾，在指定节点前插入节点，移除首节点，移除尾节点，移除任意节点。具体的方法实现就是链表的简单操作，就不展开方法了，只需注意对之前的实例变量first与last指针做特别处理即可。

有了这些辅助方法，暴露给外部的公共方法实现就比较容易了，简单的调用一下即可。

链表的实现比较简单，好像也没啥可说的。。。这里就说一下他的几个需要注意的api方法吧。

peek（）：返回头结点但并不移除，api提供了语义更准确的peekFirst与peekLast，推荐使用语义准确的方法。

poll（）：返回头结点并移除，这里其实是队列的方法。api提供了语义更准确的pollFirst与pollLast，推荐使用语义准确的方法。

remove（）：返回头结点并移除

offer（）：在链表尾部插入节点，api提供了语义更准确的offerFirst与offerLast，比较推荐使用语义准确的方法。

push（）：从链表头部添加节点

pop（）：从链表头部移除节点

removeFirstOccurrence（）与removeLastOccurrence（）：移除第一次出现的元素或最后一次出现的元素。

是不是感觉很多重复功能的方法。。我第一次使用时也是这样感觉的，觉得没必要实现这么多重复功能的方法，但其实后来开始有点明白了，这些方法都有着各自的语义，因为LinkedList实现了List与Deque，他们各自代表了列表与队列的语义，虽然方法功能冗余，但是语义却更加明确了。