下文帶/**/為原始碼注釋//為個人注釋，源代碼使用這個顏色

Node物件存盤元素和元素左右資料的指標
add(e)，我將我自己添加到上一個元素的Next

addFirst(e)替換鏈表頭
addLast(e)替換鏈表尾
addadd(index,ele)---linkLast or linkBefore
getFirst();getLast();效率最高的兩個獲取
為什么說鏈表獲取元素慢！
set(index,ele)更新元素同樣需要遍歷集合！
removeFirst洗掉并重新賦值first
removeLast洗掉并重新賦值Last
remove(index)四種洗掉情況！
remove(obj)洗掉指定元素的兩種情況

Node物件存盤元素和元素左右資料的指標

/*構建一個空串列*/

//無參構造器

public LinkedList() {}

//將要添加的元素放到Node物件中的item屬性中，

//多個Node物件構成一個鏈表，物件中持有下一個

//和上一個Node物件

private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {

//當前Node物件
this.item = element;

//下一個
this.next = next;

//上一個
this.prev = prev;
}
}

/**指向最后一個節點的指標**/

transient Node<E> last;//LinkedList的成員變數

/*指向第一個節點的指標*/

transient Node<E> first;//LinkedList的成員變數

/*該串列被修改的次數*/

protected transient int modCount = 0;//LinkedList的成員變數

//當前集合的元素總個數

transient int size = 0;//LinkedList的成員變數

add(e)，我將我自己添加到上一個元素的Next

/*將指定的元素追加到串列的末尾，*/

//添加元素

public boolean add(E e) {
linkLast(e);
return true;
}

/*e作為最后一個元素，*/

void linkLast(E e) {

//先拿到串列中最后一個元素，串列是第一次添加元素是沒有的
final Node<E> l = last;

//創建Node物件，將最后一個元素當成Node的prev

//傳入的元素是當前Node元素，下一個不傳
final Node<E> newNode = new Node<>(l, e, null);

//當前創建的Node成為最后一個元素，也就是下一個Node的prev
last = newNode;

//如果上一個為null，當鏈表是第一次添加元素這個是null
if (l == null)

//將新增的Node賦值到第一個節點的指向，現在來看這個值只會被賦值一次？
first = newNode;
else

//如果last不是null則表示串列內已經有元素

//一個新增加的元素其實是一個Node但是這個Node是沒有next的

//這個賦值代表著，如果鏈表內有元素，將這個新創建的Node賦值

//給上一個Node的next
l.next = newNode;

size++;
modCount++;
}

addFirst(e)替換鏈表頭

/*在串列的開頭插入指定的元素，*/

public void addFirst(E e) {
linkFirst(e);
}

/*e作為第一個元素，*/

private void linkFirst(E e) {

//拿到first元素
final Node<E> f = first;

//創建新Node它的first是null,next是原來的first
final Node<E> newNode = new Node<>(null, e, f);

//將first指標指向新Node
first = newNode;

//如果f是null表示之前沒有元素
if (f == null)

//則新添加的node同時也是last
last = newNode;
else//如果f不是null

//將新添加的Node指標賦值給原有first的prev

f.prev = newNode;

//計數器
size++;
modCount++;
}

addLast(e)替換鏈表尾

/*將指定的元素追加到串列的末尾，*/

public void addLast(E e) {
linkLast(e);
}

/*e作為最后一個元素，*/

void linkLast(E e) {

//拿到原來的last
final Node<E> l = last;

//創建新的Node它的prev是原來的last阿德next是null
final Node<E> newNode = new Node<>(l, e, null);

//將新創建的Node賦值給last
last = newNode;

//如果l==null表示原來沒有元素
if (l == null)

//此時只有新增加的元素，所以它也是first
first = newNode;
else

//如果原來有元素，則原來的last的next為新創建的Node
l.next = newNode;

//計數器
size++;
modCount++;
}

addadd(index,ele)---linkLast or linkBefore

/*

在串列的指定位置插入指定的元素，將元素當前的位置

(如果有的話)和后續的元素向右移動(在它們的索引中添加一個)，

*/

public void add(int index, E element) {

//index只能大于=0或者小于=size,否則例外

checkPositionIndex(index);

if (index == size)

//如果index等于size表示當前做的是追加操作
linkLast(element);
else

//那這里應該是包含0的情況其實就是linkFirst()

//不清楚為啥不判斷下，

//首先獲取下標Node
linkBefore(element, node(index));
}

private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/*告知引數是否是迭代器或添加操作的有效位置的索引，*/

private boolean isPositionIndex(int index) {
return index >= 0 && index <= size;
}

/*將元素e插入到非空節點succ之前，*/

void linkBefore(E e, Node<E> succ) {
// assert succ != null;

//拿到下標Node的prev

final Node<E> pred = succ.prev;

//創建新的Node它的prev是succ Node的prev,它的next是succ

//簡單描述新創建的元素在index的前邊
final Node<E> newNode = new Node<>(pred, e, succ);

//index Node的prev指標變成了新創建的Node
succ.prev = newNode;

//原來的Node的prev如果是null表示它原來是第一個元素

//那就把新創建的Node賦值到first
if (pred == null)
first = newNode;

//原來的Node不是first則將原有Node的prev的next賦值成newNode
else
pred.next = newNode;

//計數器
size++;
modCount++;
}

getFirst();getLast();效率最高的兩個獲取

//第一個Node創建后，last和first都是Node1，第二個Node創建后last是Node2，還是firstNode1，

//拿到Node后獲取成員item，

/*回傳串列中的第一個元素，*/

public E getFirst() {

final Node<E> f = first;

if (f == null)

throw new NoSuchElementException();

return f.item;

}

/*回傳串列中的最后一個元素*/

public E getLast() {

final Node<E> l = last;

if (l == null)

throw new NoSuchElementException();

return l.item;

}

為什么說鏈表獲取元素慢！

/*回傳串列中指定位置的元素，*/

public E get(int index) {

//判斷index是否合法

checkElementIndex(index);

//這是個重點方法，

return node(index).item;

}

private void checkElementIndex(int index) {

if (!isElementIndex(index))

 throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

/**告知引數是否為現有元素的索引，**/

private boolean isElementIndex(int index) {

//要查詢的index在0和size-1之間則回傳true

return index >= 0 && index < size;

}

/*回傳指定元素索引處的(非空)節點，*/

Node<E> node(int index) {

//如果要查詢的index小于當前size/2

if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//如果要查詢的index大于當前size/2
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

//這里假設LinkedList元素總個數為100，當前查詢的index為49則100/2=50

//49<50，先獲取集合內第一個Node,然后從0開始，每次都取Node的Next

//也就是Next代表的Node，需要回圈49次才能拿到index為49的元素，

//如果當前元素為100，當前查詢的index為50，則從99開始，往后回圈查詢

//需要回圈48次，最快的兩種情況是要查詢第0號下標則第一個回圈不滿足直接

//回傳first或者要查詢99號下標不滿足第二個回圈直接回傳last，但是這兩

//中情況使用getFirst()或者getLast()是最快的，

set(index,ele)更新元素同樣需要遍歷集合！

/*將串列中指定位置的元素替換為指定元素，*/

public E set(int index, E element) {

//檢驗下標是否合格，上邊說過這個方法，
checkElementIndex(index);

//同樣需要找到對應的Node，上邊說過這個方法，
Node<E> x = node(index);

//獲取老的元素
E oldVal = x.item;

//新的元素替換老的元素
x.item = element;

//回傳被替換的元素
return oldVal;
}

removeFirst洗掉并重新賦值first

/*洗掉并回傳串列中的第一個元素，*/

public E removeFirst() {

//獲取first元素
final Node<E> f = first;
if (f == null)

//如果是null表示當前集合沒有元素，拋出例外
throw new NoSuchElementException();
return unlinkFirst(f);
}

/*斷開第一個非空節點的鏈接*/

private E unlinkFirst(Node<E> f) {

//獲取第一個Node的item
final E element = f.item;

//獲取第一個Node的Next
final Node<E> next = f.next;

//將item置為null
f.item = null;

//將next置為null,因為first是沒有prev的，所以將

//Node的ele元素和next全部置為null則代表可以

//進行垃圾回收
f.next = null; // help GC

//第一個Node被移除后它next的理應的是first
first = next;

//如果被移除的Node的next現在是first是null則表示

//當前集合沒有元素則last也應當是null
if (next == null)
last = null;

//如果first被移除后集合內還有元素，則新的first的prev是null
else
next.prev = null;

//計數器操作

size--;
modCount++;

//回傳被移除的元素
return element;
}

removeLast洗掉并重新賦值Last

/*洗掉并回傳串列中的最后一個元素，*/

public E removeLast() {

//獲取最后一個Node
final Node<E> l = last;

//如果是null拋例外
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}

/*解除最后一個非空節點l的鏈接，*/

private E unlinkLast(Node<E> l) {

//拿到last的元素
final E element = l.item;

//拿到last的上一個
final Node<E> prev = l.prev;

//斷掉指標
l.item = null;

//斷掉指標，等待被回收
l.prev = null; // help GC

//last被洗掉后它的prev理應的是新的last
last = prev;

//如果新的last是null，則表示集合內沒有元素

//first置為null
if (prev == null)
first = null;
else

//順利成為last后它失去next的指標，也就是oldNext的指標
prev.next = null;

//計數器
size--;
modCount++;

//回傳被洗掉的元素
return element;
}

remove(index)四種洗掉情況！

/*

移除此串列中指定位置的元素，將后面的元素向左移動

(從它們的索引中減去1)，回傳從串列中洗掉的元素，

*/

public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}

/*Unlinks non-null node x.*/

E unlink(Node<E> x) {
// assert x != null;

//需要被洗掉Node的元素內容
final E element = x.item;

//需要被洗掉Node的下一個
final Node<E> next = x.next;

//需要被洗掉Node的上一個
final Node<E> prev = x.prev;

//如果上一個等于null表示被洗掉的元素是第一個

if (prev == null) {

//則需要將被洗掉的Node的next賦值到first
first = next;
} else {

//如果被洗掉的Node不是第一個，需要將它的next

prev.next = next;

//賦值給它的prev的next，并且將它的上一個指標斷掉，
x.prev = null;
}

//如果被洗掉的Node的next是null表示它是最后一個

if (next == null) {

//則需要將它的prev賦值到last
last = prev;
} else {

//否則表示它不是最后一個，需要將被洗掉的Node的prev

//轉移到下一個Node的prev
next.prev = prev;

//將next指標斷掉
x.next = null;
}

//將元素內容指標斷掉

x.item = null;

//計數器操作
size--;
modCount++;
return element;
}

remove(obj)洗掉指定元素的兩種情況

/*如果指定元素出現，則從串列中洗掉第一個出現的元素，如果此串列不包含該元素，則將對其進行更改，*/

//其實這個注釋是非常不令人理解的，，，我的理解是不包含該元素則不對其進行更改

public boolean remove(Object o) {

//如果被洗掉的是null
if (o == null) {

//從頭遍歷集合，根據每一個Node的item判斷是不是null

//回圈結束條件是next==null

for (Node<E> x = first; x != null; x = x.next) {

//如果找到了就洗掉還是執行的unlink()最后回傳true
if (x.item == null) {
unlink(x);
return true;
}
}
} else {

//如果不是null照樣也是從頭遍歷集合呼叫被洗掉元素的equals

//這意味著如果你被洗掉的元素和集合內其他元素的型別不同則

//可能會報錯
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {

//如果相同則洗掉并且回傳true
unlink(x);
return true;
}
}
}

//最后沒有滿足條件的回傳false洗掉失敗
return false;
}

標籤：Java

上一篇：2020年高頻Java面試題集錦（含答案），讓你的面試之路暢通無阻！

下一篇：程式員你是怎么繪制架構圖？