LinkedList底層數(shù)據(jù)結(jié)構(gòu)是一個(gè)具有頭尾節(jié)點(diǎn)的雙向鏈表。雙向鏈表的優(yōu)點(diǎn)就是通過(guò)某個(gè)節(jié)點(diǎn)訪問(wèn)其前驅(qū)和后驅(qū)表較方便。缺點(diǎn)是需要額外存儲(chǔ)其前驅(qū)和后驅(qū)的空間。LinkeList鏈表允許null元素；
問(wèn)題一：LinkedList如何初始化
LinkedList構(gòu)造函數(shù)有兩種，無(wú)參構(gòu)造和帶集合的構(gòu)造函數(shù)
1.無(wú)參構(gòu)造，初始化集合大小size=0，初始不用存儲(chǔ)任何數(shù)據(jù)，內(nèi)存占用低；
public LinkedList() {
this.size = 0;
}
2.帶集合的構(gòu)造函數(shù)，創(chuàng)建一個(gè)大小和傳入集合大小一致的鏈表，記錄頭尾節(jié)點(diǎn)
public LinkedList(Collection<? extends E> c) {
this();
this.addAll(c);
}
3.接著2我們來(lái)看下addAll方法，他的參數(shù)有index和傳入的集合，猜想index應(yīng)該是傳入集合存儲(chǔ)開始的地方。
public boolean addAll(int index, Collection<? extends E> c) {
//判斷這個(gè)index是否超過(guò)鏈表有效位置的范圍，超出的話會(huì)報(bào)IndexOutOfBoundsException.
this.checkPositionIndex(index);
//返回包含這個(gè)集合中所有數(shù)據(jù)的數(shù)組，感覺(jué)是個(gè)耗時(shí)操作
Object[] a = c.toArray();
//獲取參數(shù)集合的長(zhǎng)度，是構(gòu)造之后鏈表的長(zhǎng)度
int numNew = a.length;
//參數(shù)集合長(zhǎng)度為0，說(shuō)明不需要存儲(chǔ)任何數(shù)據(jù)，就不用做任何事了直接返回。
if (numNew == 0) {
return false;
} else {
//輔助構(gòu)造鏈表
LinkedList.Node pred;
LinkedList.Node succ;
//index = this.size從鏈表尾部插入
if (index == this.size) {
succ = null;
pred = this.last;
} else {
//index != this.size從鏈表中間插入
succ = this.node(index);
pred = succ.prev;
}
Object[] var7 = a;
int var8 = a.length;
//遍歷參數(shù)集合的數(shù)組，從插入的位置index開始插入
for(int var9 = 0; var9 < var8; ++var9) {
Object o = var7[var9];
LinkedList.Node<E> newNode = new LinkedList.Node(pred, o, (LinkedList.Node)null);
//插入集合的第一個(gè)節(jié)點(diǎn)
if (pred == null) {
this.first = newNode;
} else {
//上一個(gè)節(jié)點(diǎn)記錄一下當(dāng)前節(jié)點(diǎn)，形成鏈表
pred.next = newNode;
}
//pred記錄當(dāng)前節(jié)點(diǎn)，開始下一個(gè)節(jié)點(diǎn)的插入
pred = newNode;
}
//succ =null說(shuō)明是從鏈表尾部開始插入的，所以記錄一下鏈表頭部，就行了。
if (succ == null) {
this.last = pred;
} else {
//相反的不是從鏈表尾部插入，從第index個(gè)插入，index元素排在插入的數(shù)據(jù)后面，形成新鏈表。
pred.next = succ;
succ.prev = pred;
}
//記錄新的鏈表長(zhǎng)度
this.size += numNew;
++this.modCount;
return true;
}
}
問(wèn)題二：LinkedList怎么插入數(shù)據(jù)？
LinkedList堆插入操作做了相關(guān)優(yōu)化。由于其基于雙端鏈表實(shí)現(xiàn)，所以其在頭尾插入速度較快，在鏈表中部插入相對(duì)較慢。
1.頭部插入元素，直接通過(guò)頭節(jié)點(diǎn)first插入，頭節(jié)點(diǎn)變成第二個(gè)元素，更新頭節(jié)點(diǎn)，非常簡(jiǎn)單。
private void linkFirst(E e) {
LinkedList.Node<E> f = this.first;
LinkedList.Node<E> newNode = new LinkedList.Node((LinkedList.Node)null, e, f);
this.first = newNode;
if (f == null) {
this.last = newNode;
} else {
f.prev = newNode;
}
++this.size;
++this.modCount;
}
2.尾部插入元素，直接通過(guò)尾節(jié)點(diǎn)插入新元素 ，待插入節(jié)點(diǎn)變成新的尾節(jié)點(diǎn)。
void linkLast(E e) {
LinkedList.Node<E> l = this.last;
LinkedList.Node<E> newNode = new LinkedList.Node(l, e, (LinkedList.Node)null);
this.last = newNode;
if (l == null) {
this.first = newNode;
} else {
l.next = newNode;
}
++this.size;
++this.modCount;
}
3.中間插入元素，如果index=鏈表長(zhǎng)度則表示在鏈表尾部插入數(shù)據(jù)，否則實(shí)在指定元素之前插入元素。
public void add(int index, E element) {
this.checkPositionIndex(index);
if (index == this.size) {
this.linkLast(element);
} else {
this.linkBefore(element, this.node(index));
}
}
4.在看linkBefore之前我看下node方法，這個(gè)方法是通過(guò)index找到鏈表中的某個(gè)數(shù)據(jù)。通過(guò)以下代碼我們可以看到它使用了一次二分查找，提高了一次查找效率，但是隨著數(shù)據(jù)增多這個(gè)函數(shù)的效率會(huì)變得越來(lái)越低。
LinkedList.Node<E> node(int index) {
LinkedList.Node x;
int i;
if (index < this.size >> 1) {
x = this.first;
for(i = 0; i < index; ++i) {
x = x.next;
}
return x;
} else {
x = this.last;
for(i = this.size - 1; i > index; --i) {
x = x.prev;
}
return x;
}
}
5.接著看下linkBefore方法。找到指定元素就非常好辦了，生成新節(jié)點(diǎn)，把新節(jié)點(diǎn)放在指定元素的前面就可以了。
void linkBefore(E e, LinkedList.Node<E> succ) {
LinkedList.Node<E> pred = succ.prev;
LinkedList.Node<E> newNode = new LinkedList.Node(pred, e, succ);
succ.prev = newNode;
//如果succ是頭節(jié)點(diǎn)，還需要更新頭節(jié)點(diǎn)指針。
if (pred == null) {
this.first = newNode;
} else {
pred.next = newNode;
}
++this.size;
++this.modCount;
}
問(wèn)題三：LinkedList怎么刪除元素
刪除節(jié)點(diǎn)和增加節(jié)點(diǎn)都是通過(guò)node方法找到指定元素，然后刪除指定節(jié)點(diǎn)，鏈表的基本操作，這里不再贅敘。
