LinkedList特點
LinkedList底層是通過一個雙向鏈表實現(xiàn)，不是線程安全的〉跬荩可以被當(dāng)作雙向鏈表甚纲、堆棧、隊列或雙端隊列進(jìn)行操作。
LinkedList結(jié)構(gòu)
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
List：用來存儲有序的、可重復(fù)的數(shù)據(jù)讯沈。
AbstractSequentialList：是個抽象類并且父類為AbstractList凝果，只是使用了列表迭代器(listIterator)重寫了增刪改查操作（查看AbstractSequentialList源碼）祝迂，而ListIterator的nextIndex()方法和previousIndex()方法可以實現(xiàn)雙向鏈表的操作，使得繼承AbstractSequentialList抽象類的實現(xiàn)類擁有操作雙向鏈表的屬性器净。
Deque：LinkedList實現(xiàn)Deque 接口型雳，即能將LinkedList當(dāng)作雙端隊列使用可作為隊列使用。Deque接口主要有ArrayDeque實現(xiàn)山害，ArrayDeque這個雙端隊列（用數(shù)組實現(xiàn)）線程不安全纠俭，區(qū)別于用鏈表實現(xiàn)的雙端隊列LinkedList。
Cloneable：LinkedList實現(xiàn)了Cloneable接口浪慌，并覆蓋了函數(shù)clone()冤荆，能被克隆。
Serializable：實現(xiàn)java.io.Serializable 接口后LinkedList支持序列化权纤，能通過序列化去傳輸钓简。
LinkedList屬性
//元素的實際個數(shù)
transient int size = 0;
/**
*指向第一個節(jié)點
* Pointer to first node.
* Invariant[?n?ve?ri?nt]: adj. 無變化的，不變的
(first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
*指向最后一個節(jié)點
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
//內(nèi)部類汹想，用于實現(xiàn)鏈表
private static class Node<E> {
E item; //存儲的元素
Node<E> next; //下一個節(jié)點,尾元素的next指向為null
Node<E> prev; //上一個節(jié)點,頭元素的prev的指向為null
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
LinkedList方法分析
類源碼方法層面的分析最好的方法是使用Debug一步步走一遍該方法外邓。
add(E e)方法
/**
* 增加指定元素到list的末尾
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* 使用對應(yīng)參數(shù)作為尾節(jié)點
*/
void linkLast(E e) {
//將新加節(jié)點的前驅(qū)指向last節(jié)點(<--)
final Node<E> l = last;
//創(chuàng)建節(jié)點(前驅(qū)是last節(jié)點，元素為e古掏，后繼為null節(jié)點)
final Node<E> newNode = new Node<>(l, e, null);
//將last節(jié)點修改為指向新節(jié)點
last = newNode;
//判斷新節(jié)點的前節(jié)點(就是以前的last節(jié)點)是不是為空
if (l == null)
//如果新節(jié)點的前節(jié)點為空损话，
// 說明這個list集合是一個空集合，這個新加節(jié)點是添加的第一個節(jié)點槽唾，
//將first節(jié)點修改為指向新節(jié)點
first = newNode;
else
//如果新節(jié)點的前節(jié)點不為空
//說明這個list集合有元素
//將前節(jié)點的后繼修改為新節(jié)點(-->)
l.next = newNode;
size++;
modCount++;
}
方法思路：直接將新增的元素放置鏈表的最后面丧枪，然后鏈表的長度（size）加1，修改的次數(shù)（modCount）加1
add(int index, E element)方法
public void add(int index, E element) {
checkPositionIndex(index);//檢查位置的角標(biāo)庞萍，[0,size]
if (index == size) //如果指定位置為最后拧烦，則添加到鏈表最后
linkLast(element);
else
//如果指定位置不是最后，則添加到指定位置前
linkBefore(element, node(index));
}
//在指定節(jié)點前插入節(jié)點挂绰，節(jié)點succ不能為空
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;//取出指定節(jié)點的前驅(qū)節(jié)點
//新建一個以指定節(jié)點為后繼節(jié)點屎篱，當(dāng)指定節(jié)點的前驅(qū)節(jié)點為前驅(qū)節(jié)點的節(jié)點
final Node<E> newNode = new Node<>(pred, e, succ);
//修改指定節(jié)點的前驅(qū)為新節(jié)點
succ.prev = newNode;
if (pred == null)
//如果指定節(jié)點為first節(jié)點
first = newNode;//將first節(jié)點修改為新節(jié)點
else
//將指定節(jié)點的前節(jié)點指向新節(jié)點
pred.next = newNode;
size++;
modCount++;
}
方法思路：
- 1、檢查索引是否越界
- 2葵蒂、如果指定位置是最后交播，則添加到鏈表最后
- 3、如果指定位置不是最后践付，則添加到指定位置之前
remove()方法
public E remove() {
return removeFirst();//默認(rèn)刪除首節(jié)點
}
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//刪除首節(jié)點并返回刪除前首節(jié)點的值秦士，首節(jié)點不為空,內(nèi)部使用
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;//取出首節(jié)點元素
final Node<E> next = f.next;//得到下一個節(jié)點
f.item = null;//將首節(jié)點元素置空
f.next = null; // 將節(jié)點后繼置空，幫助回收
first = next;//首節(jié)點的下一個節(jié)點成為新的首節(jié)點
if (next == null)
//如果鏈表中就有一個節(jié)點永高，首節(jié)點和尾節(jié)點都指向這個節(jié)點的話
//首節(jié)點的下一個節(jié)點為空
last = null; //如果不存在下一個節(jié)點隧土，則首尾都為null(空表)
else
next.prev = null;//如果存在下一個節(jié)點提针，那它向前指向null
size--;
modCount++;
return element;
}
remove(int index)方法
public E remove(int index) {
checkElementIndex(index);//判斷索引是否越界
return unlink(node(index));
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
/**
* 返回指定索引的節(jié)點
*/
Node<E> node(int index) {
// 判斷位置在鏈表前半段或者是后半段
if (index < (size >> 1)) {//如果index在鏈表的前半段
Node<E> x = first;//第一個節(jié)點
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {//如果index在鏈表的后半段
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//刪除不為空的節(jié)點x
E unlink(Node<E> x) {
// assert isElementIndex(index);
final E element = x.item;//取出節(jié)點的元素
final Node<E> next = x.next;//取出節(jié)點的下一個節(jié)點
final Node<E> prev = x.prev;//取出節(jié)點的上一個節(jié)點
if (prev == null) {
//如果前一個節(jié)點為空(如當(dāng)前節(jié)點為首節(jié)點)，后一個節(jié)點成為新的首節(jié)點
first = next;
} else {
//如果前一個節(jié)點不為空曹傀，那么他的后繼指向當(dāng)前的下一個節(jié)點
prev.next = next;
x.prev = null;//便于回收
}
if (next == null) {
//如果后一個節(jié)點為空(如當(dāng)前節(jié)點為尾節(jié)點)辐脖，當(dāng)前節(jié)點前一個成為新的尾節(jié)點
last = prev;
} else {
//如果后一個節(jié)點不為空，后一個節(jié)點向前指向當(dāng)前的前一個節(jié)點
next.prev = prev;
x.next = null;//方便回收
}
x.item = null;
size--;
modCount++;
return element;
}
unlink()刪除操作分以下幾個步驟：
- 1皆愉、 通過要刪除的元素x拿到它的前驅(qū)節(jié)點prev和后繼節(jié)點next嗜价。
- 2、 若前驅(qū)節(jié)點prev為null幕庐，說明x是集合中的首個元素久锥，直接將first指向后繼節(jié)點next即可；
若不為null异剥，則讓前驅(qū)節(jié)點prev的next指向后繼節(jié)點next瑟由，再將x的prev置空。（這時prev與x的關(guān)聯(lián)就解除了冤寿，并與next建立了聯(lián)系）歹苦。 - 3、若后繼節(jié)點next為null疚沐，說明x是集合中的最后一個元素暂氯，直接將last指向前驅(qū)節(jié)點prev即可；（下圖分別對應(yīng)步驟2中的兩種情況）
若不為null亮蛔，則讓后繼節(jié)點next的prev指向前驅(qū)節(jié)點prev，再將x的next置空擎厢。（這時next與x的關(guān)聯(lián)就解除了究流，并與prev建立了聯(lián)系） - 4、最后动遭，讓記錄集合長度的size減1芬探。
