LinkedList 的实现原理浅析
LinkedList内部结构
查看LinkedList的源码，发现其继承自AbstractSequentialList，实现了List，Deque，Cloneable以及Serializable接口，如：
也就意味着：
-
LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
-
LinkedList 实现 List 接口，能对它进行列表操作。
-
LinkedList 实现 Deque 接口，即能将LinkedList当作双端队列使用。
-
LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
-
LinkedList 实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
从上述代码可以看出，LinkedList中有size，first以及last全局变量，其作用分别是：
-
size -- 存放当前链表有多少个节点。
-
first -- 指向链表的第一个节点的引用
-
last -- 指向链表的最后一个节点的引用
其中，Node是内部类，内容如下：
从上述代码可以看出，
一个节点除了包含元素内容之外，同时包含前一个节点和后一个节点的引用~
各个节点通过指定前一个节点和后一个节点，最终形成了一个链表~
代码示例：
输出结果：
debug查看LinkedList的结构如下：
形成了一个链表
方法 add 的实现
源代码
add方法会调用linkLast方法，会在链表尾端添加节点~
linkLast方法步骤
-
获取原来的last节点，然后创建一个新的节点，其prev为原来的last节点，其next节点为null
-
将last只想新的节点
-
如果原来的last节点为null，其实就是还没有元素，那么新的节点同样也是first节点；如果不为null，则原来的last节点的next就是新的节点
-
因为有新元素加入，size加1，且修改次数加1（modCount++）
方法 addAll 的实现
源代码
addAll在LinkedList内部其实就是调用了方法addAll(int index, Collection<? extends E> c)
方法addAll(int index, Collection<? extends E> c)
方法addAll(int index, Collection<? extends E> c) 主要包含如下几个步骤：
-
检查指定index是否合理
index的有效位置是[0,size]
-
定义pred和succ节点，并根据index的大小确定pred和succ节点
-
对Collection转换成数组（Object[] a = c.toArray()）的元素进行循环遍历，确定first、pred.next等节点信息
-
检查succ是否为空，如果为null，则表示目前的pred节点就是最后一个了，将last节点指向pred；反之，如果不为null，则将prev的next节点指向succ，同时succ的prev节点指向pred。
-
最后修改size和modCount的值
上述是往指定位置添加多个元素，那么，往指定位置添加单个元素add(int index, E element) 就变得很简单了。
方法add(int index, E element)
该方法包含如下两个步骤
-
检查指定index的值是否有效[0,size]
-
如果index == size 则使用linkLast添加在尾部；如果index ！= size， 则使用linkBefore将新元素添加在指定位置之前~
linkBefore方法如下
本文上述已经讲述了linkLast，linkBefore的方法实现思路类似，这里就不再具体给出解释了。
此外，LinkedList还提供了addFirst以及addLast方法，分别用于将元素插在列表头部和尾部~
其中，linkFirst和linkLast方法如下：
方法 remove 的实现
LinkedList支持多种删除元素的方法~
一起来看看具体是怎么样的~
无参数remove方法
无参数的remove方法其实就是调用了removeFirst方法，也就是移除first元素~
removeFirst方法
removeFirst使用了unlinkFirst方法来移除元素~
unlinkFirst方法处理主要包含如下几个步骤：
-
获取first元素值，然后获取first的next元素
-
将first节点指向next，同时原来的first节点的属性值置为null（包括item和next）
-
如果next节点（原first节点的nex节点）为null，则将last置为null值；如果不为null，则将next节点的prev属性置为null
-
然后修正元素个数以及修改次数（size和modCount）
同样，也存在移除尾节点的方法removeLast
removeLast方法
其使用了unlinkLast方法实现
unlinked方法的实现与unlinkedFirst的方法思路类似，就不在这里一一说明了~
方法remove(int index)
按照指定位置移除元素，主要包含如下几个部分：
-
检查index是否有效
-
通过node(index)查找index位置下的节点
从上述代码可以看出，方法node(int index)中
先判断index和中间点（size >>1）位置的大小。如果index < (size >> 1), 那么按下标从小到大查找；否则，按下标从大到小查找~
-
使用unlink(Node<E> x)修改链表的连接关系，达到移除元素的效果
方法remove(Object o)
按照指定对象的移除，在代码中，区分删除的元素是否为null值，然后从first开始遍历链表，如果元素值和删除的值内容一致，则调用unlink方法移除元素~
方法 indexOf 的实现
源代码
从上述代码可以看出：
LinkedList的indexOf实现区分null和非null值。从first节点开始遍历，如果找到符合条件的元素，则返回元素所在的下标值。如果没有找到，则返回-1~
与之对应的还有lastIndexOf方法，该方法和indexOf的思路一致，区别就是，lastIndexOf是以last节点开始往前寻找~
方法 contains 的实现
源代码
从上述代码可以看出，contains方法内调用了indexOf方法，然后采用获取的结果与-1比较，如果不相等表示有匹配的元素，否则表示没有符合条件的元素~
方法 clear 的实现
源代码
clear方法，从first开始遍历链表，将元素的item、prev和nex属性置为null值，然后将first和last置为null。同时将size置为0，修改次数加1（modCount+）
方法 get 的实现
LinkedList支持按索引查找以及获取first和last元素的操作~ 如：
方法get(int index)的实现
此方法包含两个步骤：
-
检查指定的index的值是否有效
-
调用node(index)获取节点，返回值node(index).item即可
方法getFirst
方法getFirst获取first节点的值item即可，得先判断first是否为空~
方法getLast
方法getLast获取last节点的值item即可，得先判断last是否为空~
方法 listIterator 的实现
源代码
其使用了内部类ListItr来实现，ListItr类内容如下：
listIterator接口继承自Iterator接口，具备更多的方法，如add，set，previous等等
ListIterator示例
输出结果：
方法descendingIterator的实现
源代码
descendingIterator与Iterator的区别在于，Iterator是从first开始往后遍历；而descendingIterator是从last开始往前遍历；
Iterator和descendingIterator示例：
输出结果：
方法 toArray 的实现
源代码
从first节点开始，依次遍历，然后得到一个数组对象~