基礎(chǔ)知識
鏈表是一種物理存儲單元上非連續(xù)的一種數(shù)據(jù)結(jié)構(gòu)，看名字我們就知道他是一種鏈式的結(jié)構(gòu)，就像一群人手牽著手一樣。鏈表有單向的，雙向的，還有環(huán)形的。
1，單向鏈表
我們先定義一個最簡單的單向鏈表結(jié)點類
class Node<E> {
E data;
Node<E> next;
Node(E data, Node<E> next) {
this.data = data;
this.next = next;
}
}
這個類非常簡單，他只有兩個變量，一個是data值，一個是指向下一個結(jié)點的指針。我們先來看一下單向的鏈表是什么樣的，
鏈表頭是不存儲任何數(shù)據(jù)的，他只有指向下一個結(jié)點的指針，當(dāng)然如果我們不需要頭結(jié)點，直接拿第一個結(jié)點當(dāng)做頭結(jié)點也是可以的，像下面這樣
單向鏈表的增刪
鏈表不像數(shù)組那樣，可以通過索引來獲取，單向鏈表查找的時候必須從頭開始往后一個個找，而不能從中間找，也不能從后往前找。我們來看一下鏈表的添加
1，添加到尾結(jié)點
添加到尾結(jié)點比較簡單，我們只需要找到之前鏈表的尾結(jié)點，然后讓他的next指針指向新的結(jié)點即可。
2，添加到中間結(jié)點
添加到中間結(jié)點，分為兩步，比如我們要在ab結(jié)點之間添加新結(jié)點n，第一步讓新結(jié)點n的指針指向b，然后再讓a的指針指向新結(jié)點n即可。
3，刪除鏈表的尾結(jié)點
只需要讓尾結(jié)點的上一個結(jié)點的指針指向null即可。
4，刪除鏈表的中間結(jié)點
只需要把要刪除結(jié)點的前一個結(jié)點的指針指向要刪除結(jié)點的下一個結(jié)點即可，最好還要把要刪除結(jié)點的數(shù)據(jù)清空，并且讓他的指針指向null。
2，單向環(huán)形鏈表
環(huán)形鏈表一般分為兩種，一種是單向環(huán)形鏈表，一種是雙向環(huán)形鏈表。我們首先來看一下單向的環(huán)形鏈表是什么樣的
他和單向非環(huán)形鏈表的區(qū)就是，單向非環(huán)形鏈表的尾結(jié)點的指針是指向null的，而環(huán)形的是指向頭結(jié)點。關(guān)于他的增刪和單向非環(huán)形的差不多，只不過在尾結(jié)點的時候會有點區(qū)別，我們主要來看下這兩種
1，添加到尾結(jié)點
2，刪除尾結(jié)點
3，雙向鏈表
我們來定義一個雙向鏈表結(jié)點的類
class Node<E> {
E data;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E data, Node<E> next) {
this.data = data;
this.next = next;
this.prev = prev;
}
}
雙向鏈表不光有指向下一個結(jié)點的指針，而且還有指向上一個結(jié)點的指針，他比單向鏈表多了一個指向前一個結(jié)點的指針，單向鏈表我們只能從前往后找，而雙向鏈表我們不光可以從前往后找，而且還可以從后往前找。我們來看一下雙向鏈表是什么樣的。
雙向鏈表我們可以從頭到尾查找，也可以從尾到頭查找，雙向鏈表在代碼中最常見的就是LinkedList了（java語言），雙向鏈表的增刪和單向鏈表的增刪很類似，只不過雙向鏈表不光要調(diào)整他指向的下一個結(jié)點，還要調(diào)整他指向的上一個結(jié)點。這里我們來結(jié)合圖形和代碼的方式來分析一下雙向鏈表的增刪。
1，添加到尾結(jié)點
我們結(jié)合著代碼來看下
void linkLast(Object e) {
final Node<Object> last = tail;
final Node<Object> newNode = new Node<>(last, e, null);
tail = newNode;
if (last == null)
head = newNode;
else
last.next = newNode;
size++;
}
總共分為4步
2，添加到頭結(jié)點
private void linkFirst(Object e) {
//用臨時變量firt保存head結(jié)點
final Node<Object> first = head;
//創(chuàng)建一個新的結(jié)點，讓他的pre指針指向null，next指針指向head結(jié)點
final Node<Object> newNode = new Node<>(null, e, first);
//讓head指向新的結(jié)點
head = newNode;
//如果之前的first為空，說明之前鏈表是空的，讓head和tial同時指向新結(jié)點即可
if (first == null)
tail = newNode;
else//如果之前鏈表不為空，讓之前first結(jié)點的pre指向新的結(jié)點
first.prev = newNode;
size++;
}
添加到頭結(jié)點和添加到尾結(jié)點很類似，圖就不在畫了，大家可以看下上面的代碼。
3，添加到指定結(jié)點之前
比如我們在a結(jié)點之前添加一個指定的結(jié)點，先來看下代碼
void linkBefore(Object e, Node<Object> a) {
final Node<Object> pred = a.prev;
final Node<Object> newNode = new Node<>(pred, e, a);
a.prev = newNode;
if (pred == null)
head = newNode;
else
pred.next = newNode;
size++;
}
假如我們在a結(jié)點之前添加一個結(jié)點，圖就不在細畫，簡單看一下即可
4，刪除鏈表的尾結(jié)點
private Object unlinkLast(Node<Object> last) {
final Object element = last.data;
final Node<Object> prev = last.prev;
last.data = null;
last.prev = null;
tail = prev;
if (prev == null)//如果只有一個結(jié)點，把尾結(jié)點刪除，相當(dāng)于把鏈表清空了
head = null;
else
prev.next = null;
size--;
return element;
}
如果鏈表只有一個結(jié)點的話，我們把它刪除，相當(dāng)于直接把鏈表清空了，這種很好理解，就不再畫。下面畫一個長度大于1的鏈表，然后刪除最后一個結(jié)點
5，刪除鏈表的頭結(jié)點
private Object unlinkFirst(Node<Object> first) {
final Object element = first.data;
final Node<Object> next = first.next;
first.data = null;
first.next = null;
head = next;
if (next == null)
tail = null;
else
next.prev = null;
size--;
return element;
}
6，刪除鏈表的中間結(jié)點
Object unlink(Node<Object> x) {
final Object element = x.data;
final Node<Object> next = x.next;//x的前一個結(jié)點
final Node<Object> prev = x.prev;//x的后一個結(jié)點
if (prev == null) {//前一個結(jié)點是空
head = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {//后一個結(jié)點是空
tail = prev;
} else {
next.prev = prev;
x.next = null;
}
x.data = null;
size--;
return element;
}
4，雙向環(huán)形鏈表
雙向環(huán)形鏈表在代碼中最常見的就是LinkedHashMap了，這個一般用于圖片緩存的比較多一些，LRUCache這個類里面主要使用的就是LinkedHashMap（java語言中），通過上面的分析，如果對linkedList能理解的話，那么雙向環(huán)形鏈表也就不難理解了，其實原理都差不多，這里就不在過多介紹，下面是雙向環(huán)形鏈表的圖。
