Java集合-LinkedList

上一節分析了ArrayList,這次分析一下LinkedList，LinkedList相對我來說使用的比較少一些，一般都直接使用ArrayList，這次看源碼希望自己可以把這些集合能夠使用的更加適合的場景，能夠根據實際情況做更多的考慮。

一看名字就知道它肯定是使用鏈表實現的List集合，LinkedList是基於雙向鏈表實現的，

實現所有可選的列表操作，並允許所有元素（包括null）。注意LinkedList實現不是同步的，所以如果需要在多線程中使用它，則它必須在外部進行同步。使用這樣的：

List list = Collections.synchronizedList(new LinkedList(...));

LinkedList也具有快速失敗的特性，如果列表迭代器結構改性後創建的任何時間，以任何方式除了通過迭代器的刪除或添加方法，迭代器將拋出一個concurrentmodificationexception。因此，面對並發修改時，迭代器會快速而乾淨地失敗，而不是在未來的某個時間內冒任意、不確定的行為。

public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, java.io.Serializable

繼承AbstractSequentialList，AbstractList此類提供了 List 介面的骨幹實現，從而最大限度地減少了實現受「連續訪問」數據存儲（如鏈接列表）支持的此介面所需的工作。對於隨機訪問數據（如數組），應該優先使用AbstractList，而不是先使用此類(百度百科)。實現了List,Deque雙端隊列。是一種具有隊列和棧的性質的數據結構。實現了Cloneable、序列化Serializable。

2.2、屬性

transient int size = 0;//大小等於0

transient Node first;//指向第一個節點。

transient Node last;//指向最後一個節點。

private static final long serialVersionUID = 876323262645176354L;//序列號

private static class Node {//節點對象，典型的雙向鏈表定義方式
E item;//元素
Node next;//下一個節點
Node prev;//上一個節點
Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

2.3、構造方法

public LinkedList {//構造一個空的列表，裡面什麼都沒有做
}

public LinkedList(Collection c) {////構造一個包含指定集合的元素的列表，按照它們由集合的迭代器返回的順序。
this;//調用空的構造
addAll(c);
}
//按照指定集合的迭代器返回的順序將指定集合中的所有元素追加到此列表的末尾。 如果在操作進行中修改了指定的集合，則此操作的行為是未定義的。 （注意，如果指定的集合是此列表，並且它是非空的，則會發生這種情況。）
public boolean addAll(Collection c) {
return addAll(size, c);
}
//將指定集合中的所有元素插入到此列表中，從指定的位置開始。 將當前位於該位置（如果有的話）的元素和隨後的任何元素移動到右邊（增加其索引）。 新元素將按照指定集合的迭代器返回的順序顯示在列表中。
public boolean addAll(int index, Collection c) {
checkPositionIndex(index);//檢查下標

Object a = c.toArray;//變為數組
int numNew = a.length;//插入的個數
if (numNew == 0)//如果為0，返回false
return false;

Node pred, succ;//定義2個節點
if (index == size) {////獲取插入位置的節點，若插入的位置在size處，則是插入到原來的後面，
succ = null;
pred = last;
} else {//否則獲取index位置處的節點，插入到他們之間
succ = node(index);//獲得index下的節點
pred = succ.prev;
}

for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;//把O轉換為E
Node newNode = new Node<>(pred, e, null);//否則獲取index位置處的節點
if (pred == null)//原來就是沒有的情況，插入到第一個的情況
first = newNode;
else//原來就是有的情況，pred = last;最後一個next掛新的節點
pred.next = newNode;
pred = newNode;//pred賦值新的節點
}

if (succ == null) {//插入到原來的最後面的情況
last = pred;
} else {//插入到原來的中間的情況
pred.next = succ;
succ.prev = pred;
}

size += numNew;//元素個數增加
modCount++;//操作次數增加
return true;
}

Node node(int index) {//返回指定元素索引處的（非空）節點。
if (index < (size >> 1)) {//小於一半就從前往後找
Node x = first;
for (int i = 0; i < index; i++) x = x.next; return x; } else {//大於一半就從後面找 Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

2.4、增加方法

public boolean add(E e) {//將指定的元素追加到此列表的末尾。
linkLast(e);
return true;
}
void linkLast(E e) {//鏈接e作為最後一個元素。
final Node l = last;//定義一個新的節點賦值為last
final Node newNode = new Node<>(l, e, null);//根據插入的值創建一個新節點，新節點的pre指向last,next為null
last = newNode;//last節點賦值為新節點
if (l == null)//如果l為空，即裡面沒有節點的情況
first = newNode;第一個節點為新節點
else//LinkedList裡面有節點的情況
l.next = newNode;//最後一個節點的下一個節點為新節點
size++;//列表大小加1
modCount++;//操作數增加
}

基於增加方法在1.7確實有一些難以理解，我還是簡單畫一個流程圖來展示：

public void addFirst(E e) {//在該列表開頭插入指定的元素。
linkFirst(e);
}
private void linkFirst(E e) {//鏈接e作為第一個元素。
final Node f = first;//定義f比賦值first
final Node newNode = new Node<>(null, e, f);//創建一個節點，節點的pre為null,值為e,next為first
first = newNode;//first賦值為新節點
if (f == null)//如果f==null,就是原來就沒有值的情況，
last = newNode;//last就為新節點
else//原來有值的情況
f.prev = newNode;原來的頭節點的pre指向了新的節點
size++;
modCount++;
}

add(int index, E element)：在此列表中指定的位置插入指定的元素。

addAll(Collection c)：添加指定 collection 中的所有元素到此列表的結尾，順序是指定 collection 的迭代器返回這些元素的順序。

addAll(int index, Collection c)：將指定 collection 中的所有元素從指定位置開始插入此列表。

2.5、移除方法

//從列表中刪除指定元素的第一個出現（如果存在）。 如果此列表不包含該元素，則它將保持不變。 更正式地，刪除具有最低索引的元素
public boolean remove(Object o) {
if (o == null) {//如果o為null
for (Node x = first; x != null; x = x.next) {
if (x.item == null) {//刪除第一個null
unlink(x);//取消鏈接非空節點x。
return true;
}
}
} else {
for (Node x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
E unlink(Node x) {//取消鏈接非空節點x。
// assert x != null;
final E element = x.item;
final Node next = x.next;
final Node prev = x.prev;

if (prev == null) {//如果prev為null，說明是第一個節點
first = next;
} else {//
prev.next = next;//空掉中間的節點
x.prev = null;//原來x的prev置空
}

if (next == null) {//最後一個節點，
last = prev;
} else {//
next.prev = prev;
x.next = null;
}

x.item = null;//置空
size--;
modCount++;
return element;
}

2.5、查找方法

public E get(int index) {//獲取index的值
checkElementIndex(index);//檢查下標
return node(index).item;//獲得index下的值
}
Node node(int index) {
// assert isElementIndex(index);

if (index < (size >> 1)) {//簡單的使用了二分法
Node x = first;
for (int i = 0; i < index; i++) x = x.next; return x; } else { Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！