啃透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