什么是LinkedList
- LinkedList 是一個繼承于AbstractSequentialList的雙向鏈表饱岸。它也可以被當作堆棧掺出、隊列或雙端隊列進行操作。
- LinkedList 實現(xiàn) List 接口苫费，能對它進行列表操作汤锨。
- LinkedList 實現(xiàn) Deque 接口，即能將LinkedList當作雙端隊列使用百框。
- LinkedList 實現(xiàn)了Cloneable接口闲礼，即覆蓋了函數(shù)clone()，能克隆。
- LinkedList 實現(xiàn)java.io.Serializable接口柬泽，這意味著LinkedList支持序列化慎菲，能通過序列化去傳輸。
- LinkedList 是非同步的锨并。
- 適用于亂序插入, 刪除. 指定序列操作則性能不如ArrayList, 這也是其數(shù)據(jù)結(jié)構(gòu)決定的.
繼承關(guān)系
繼承關(guān)系
圖解說明LinkedList操作
以下內(nèi)容來自于 圖解Java常用數(shù)據(jù)結(jié)構(gòu)
add(E) / addLast(E)
image
add(index, E)
這邊有個小的優(yōu)化, 他會先判斷index是靠近隊頭還是隊尾, 來確定從哪個方向遍歷鏈入.
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;6
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
靠隊頭
image
靠隊尾
image
get(index)
也是會先判斷index, 不過性能依然不好, 這也是為什么不推薦用for(int i = 0; i < lengh; i++)的方式遍歷linkedlist, 而是使用iterator的方式遍歷.
靠隊頭
image
靠隊尾
image
remove(E)
image
LinkedList內(nèi)部做了查詢優(yōu)化：遍歷時先判斷索引是靠近隊頭還是隊尾露该，如果靠近隊頭，從first開始遍歷第煮；否則從last遍歷解幼。
