Debug LinkedList源碼 前置知識 LinkedList基於鏈表，LinkedList的Node節點定義 成員變數 //鏈表中元素的數量 transient int size = 0; /** * 鏈表的頭節點：用於遍歷 */ transient Node<E> first; /** * ...
目錄
Debug LinkedList源碼
前置知識
- LinkedList基於鏈表，LinkedList的Node節點定義
-
成員變數
//鏈表中元素的數量 transient int size = 0; /** * 鏈表的頭節點：用於遍歷 */ transient Node<E> first; /** * 鏈表的尾節點：用於添加元素 */ transient Node<E> last;
2.1 Debug 分析第一個元素是如何進入鏈表的
編寫測試代碼，打上斷點：
進入方法內部：
- add方法預設添加到鏈表的尾部
- 該方法等同於addLast（區別就是add方法需要返回一個true，而addLast沒有任何返回值）
進入linkLast方法內部：
/**
* 當前方法執行完後，若添加的節點為第一個節點，鏈表的last和first都指向新節點
*/
void linkLast(E e) {
//獲取到鏈表的最後一個元素
final Node<E> l = last;
//創建一個節點，前一個節點為當前鏈表的last，後一個節點為空
final Node<E> newNode = new Node<>(l, e, null);
//修改last為新添加的節點
last = newNode;
//若鏈表為空，first節點為新添加的節點，否則添加前最後一個節點的next指向新節點
if (l == null)
first = newNode;
else
l.next = newNode;
//鏈表長度加一
size++;
//鏈表修改次數加1
modCount++;
}
//=================================================================
Node帶三個參數的構造函數：
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
2.2 Debug 分析如何通過下標插入指定位置add（index，e）
編寫測試用例：
進入方法內部：
public void add(int index, E element) {
//檢查下標是否合法：大於等於0小於等於size【return index >= 0 && index <= size;】
checkPositionIndex(index);
//若等於size，相當於在鏈表尾部添加節點
if (index == size)
linkLast(element);
else
//linkBefore中的Before指的是傳入索引元素前
linkBefore(element, node(index));
}
進入node（index）方法：返回索引為index的元素
Node<E> node(int index) {
// assert isElementIndex(index);
//查找元素的思路是遍歷一半，先折半分區，然後若在小於折半的區域就從first開始往後遍歷，反之從last往前遍歷
//右移一位相當於除以2
if (index < (size >> 1)) {
//獲取到first節點
Node<E> x = first;
//從first遍歷到index的位置
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
//獲取到next的節點
Node<E> x = last;
//從last往前遍歷到index的位置
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
回到linkBefore方法：
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//獲取index節點的上一個節點
final Node<E> pred = succ.prev;
//創建新節點，下一個節點指向index節點，上一個節點指向index節點的上一個節點
final Node<E> newNode = new Node<>(pred, e, succ);
//index節點的上一個節點指向變為指向新節點
succ.prev = newNode;
//**若index節點的頭節點為空，相當於從頭部插入節點，直接將新節點賦給first節點
if (pred == null)
first = newNode;
else
//index的上一個節點的下一個節點指向改為新節點
pred.next = newNode;
//節點長度+1
size++;
//鏈表修改次數+1
modCount++;
}
2.3 Debug 分析如何通過下標獲取指定元素
編寫測試代碼，打上斷點：
進入get方法內部：
public E get(int index) {
//檢查下標範圍
checkElementIndex(index);
//遍歷一半，返回節點的值
return node(index).item;
}
LinkedList支持的查詢除了通過下標獲取外，還支持getLast和getFirst
get(0)和getFirst時間複雜度有區別嗎？
理論上來說，getFirst和getLast都是直接獲取到節點，時間複雜度為O（1），而通過get(index)方法查詢節點，都會折半後遍歷一半的元素，時間複雜度為O（n）。但實際情況下，for迴圈遍歷的第一個元素就100%是頭節點或尾節點，不會進入之後的迴圈，實際運行的也是O（1）。
2.4 Debug 分析如何通過下標刪除元素
打上斷點：
進入方法內部：
public E remove(int index) {
//檢查下標範圍
checkElementIndex(index);
//node(index)獲取需要刪除的節點，折半遍歷
return unlink(node(index));
}
進入unlink方法內部：
刪除中間元素的過程圖：
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
//若刪除的節點為頭節點，將當前節點的下一個節點賦值給first節點
first = next;
} else {
//若刪除的節點為中間節點，將當前節點的上一個節點的下一個節點指向變為當前節點的下一個節點（step1）
prev.next = next;
//當前節點的上一個節點指向置為null（step2）
x.prev = null;
}
if (next == null) {
//若刪除的節點為尾節點，將當前節點的上一個節點賦給last
last = prev;
} else {
//若刪除的節點為中間節點，將當前節點的下一個節點的上一個節點指向變為當前節點的上一個節點（step3）
next.prev = prev;
//當前節點的下一個節點指向置為null（step4）
x.next = null;
}
//節點元素內容置為空
x.item = null;
//鏈表長度-1
size--;
//鏈表修改次數+1
modCount++;
//返回刪除節點內容
return element;
}
2.5 Debug 分析如何通過對象刪除節點（內容）
public boolean remove(Object o) {
//若節點為null，從first往下遍歷（說明LinkedList是允許為空值的，並且允許多個）
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
}
//若節點不為空，遍歷鏈表後刪除節點
else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
