啃透JDK源码-LinkedList（中）

4.2 首位添加

addFirst(E e)

linkFirst(E e)

图解首位添加

主要流程：

• 将原 first 节点保存到 f
• 将插入元素封装成 newNode，并且该新节点的next指向原来的头节点，即f
• 若原来的头节点 f 为null，那么新插入头节点也是 last 尾节点，否则设置 f 的前置节点为NewNode，即 NewNode 现在是first 头节点.

• size加一，修改计数器加一

4.3 指定位置插入

add(int index, E element)

首先调用checkPositionIndex检查index值是否在范围内

checkPositionIndex

isPositionIndex

• 判断参数是否为迭代器或者添加操作的有效位置的索引.

• 

• 如果index在最后的话，就调用在尾部插入的函数，否则调用LinkBefore

LinkBefore

图解指定位置插入元素

5 remove

• 因为 Deque 接口，所以本类也实现了如下方法支持双端操作:

• 

5.1 removeFirst()

unlinkFirst(Node f)

5.2 removeLast

unlinkLast

删除非空的尾节点

remove(int index)

在指定index删除

检验index是否合法.如果删除成功，返回删除的节点。 具体实现在unlink

unlink

图解 unlink 过程

流程如下:

• 将删除的节点保存在element，同时把要删除节点的前驱节点标记为prev,后继节点标记为next
• 若prev为null，则 next 节点直接为 first 节点，反之把prev的next指向next节点，如图上面弯曲的红色箭头
• 若 next 为空，那么prev节点直接为last节点，反之把next的prev指向prev节点，如图下面弯曲的蓝色箭头
• 把要删除的节点置空，返回第一步保存的element