底層存儲結(jié)構(gòu)
與 數(shù)組 對比，數(shù)組需要一塊 連續(xù)的內(nèi)存空間 來存儲峻堰，對內(nèi)存要求很高米辐。如果我們申請 50MB 的內(nèi)存痕寓，即便內(nèi)存的剩余內(nèi)存大于 50MB，但是如果內(nèi)存不是連續(xù)的揪漩，也是很有可能申請失敗。
而 鏈表 與之相反，它并不需要一塊連續(xù)的內(nèi)存哮内，通過 指針 將一組 零散的內(nèi)存塊 串聯(lián)起來使用。
下面的圖片可以看出兩者之間的區(qū)別：
鏈表分類
單鏈表
單鏈表每個節(jié)點有兩部分組成壮韭，數(shù)據(jù) 和 后繼指針 next 北发。
第一個節(jié)點稱為 頭結(jié)點， 最后一個節(jié)點稱為 尾節(jié)點 泰涂，尾節(jié)點 next 指向 null鲫竞。鏈表的插入增加和刪除，不需要移動逼蒙，只需要改變前后節(jié)點 next 的指針即可實現(xiàn)从绘。
但是，如果需要訪問第 N 個元素，則需要時間復雜度為 僵井。
循環(huán)鏈表
循環(huán)鏈表是從鏈尾直接連接到鏈頭陕截。
雙向鏈表
相比于單鏈表，雙向鏈表具有兩個節(jié)點：前繼節(jié)點和后繼節(jié)點批什。
LRU 緩存淘汰算法
維護一個有序單鏈表农曲，越靠近鏈尾的節(jié)點是越早訪問的，當有一個新的數(shù)據(jù)訪問時驻债，我們從鏈表頭部開始順序遍歷鏈表乳规。
- 如果該數(shù)據(jù)已經(jīng)存在于鏈表中，那么遍歷拿個這個數(shù)據(jù)的節(jié)點刪除合呐，并將新的插入到頭部暮的。
- 如果此數(shù)據(jù)沒有再緩存鏈表中：
- 如果緩存未滿，則直接將該節(jié)點插入鏈表的頭部
- 如果此時鏈表已滿淌实，則鏈表尾節(jié)點刪除冻辩，將新的數(shù)據(jù)節(jié)點插入到鏈表的頭部。
鏈表小總結(jié)
說一句尷尬的話拆祈，本人大學的時候也是掛了 算法與數(shù)據(jù)結(jié)構(gòu) 這門課恨闪，說實話，對算法也是有一點陰影放坏，總感覺自己會學不好咙咽。就拿寫鏈表而言，經(jīng)常被引用的移動產(chǎn)生誤解轻姿，在過程中經(jīng)常不知道指針移到到哪了犁珠，導致并不會實現(xiàn)自己預期想要的結(jié)果。其實練習題做下來還是蠻有感觸的互亮，還是要多練習犁享，從中可以找到一些技巧，下面總結(jié)一下：
理解指針或引用的含義
對于我這個學習 Java 的而言豹休，其實就是要理解引用的含義炊昆。
將某個變量賦值給引用，實際上是將這個變量的地址賦值給該引用威根，或者反過來說凤巨，引用中存儲了這個變量的內(nèi)存地址，指向了這個變量洛搀，通過這個指針就能找到這個變量敢茁。
例子
Node node1 = new Node(null, 1);
node1 = new Node(null, 2);
Node node2 = new Node(null, 3);
node1 = node2;
node1.value = 3;
只要是 node = 引用后面直接跟上等于，那就證明只是單純的將這個引用指向另一個內(nèi)存地址留美，并不會影響任何變量的值彰檬。而如果 node. 引用通過 . 的方式伸刃，那么他的值就有變化的可能。
警惕引用丟失和內(nèi)存泄漏
比如鏈表插入節(jié)點操作逢倍。
Node targetNode = new Node(null, 1); // 待被插入的節(jié)點
Node preNode; // 已經(jīng)被找到插入前一個節(jié)點
錯誤示范：
preNode.next = targetNode;
targeNode.next = preNode.next.next;
這里現(xiàn)將前節(jié)點指向目標節(jié)點捧颅，然后目標節(jié)點再指向前節(jié)點的下下個節(jié)點，意思是沒有錯誤较雕，但是會導致后節(jié)點以及之后都會被丟失碉哑。
正確的做法應該是：
targetNode.next = preNode.next.next;
preNode.next = targeNode;
雖然僅僅是調(diào)換了順序，就會產(chǎn)生不同的結(jié)果亮蒋。同樣刪除節(jié)點時扣典，也要記得手動釋放內(nèi)存。
利用哨兵簡化實現(xiàn)難度
針對鏈表的插入慎玖、刪除操作激捏，需要對插入第一個結(jié)點和刪除最后一個結(jié)點的情況進行特殊處理。
重點留意邊界條件處理
- 如果鏈表為空凄吏，代碼是否能正常工作
- 如果鏈表只包含一個節(jié)點，代碼是否能正常工作
- 如果鏈表只包含兩個節(jié)點闰蛔，代碼是否能正常工作
- 代碼邏輯在處理頭結(jié)點和尾節(jié)點的時候痕钢，代碼是否能正常工作
舉例畫圖，輔助思考
我平常在做練習題時序六，身邊必備一張紙和一紙筆任连，對特殊的邏輯進行畫圖舉例演示，很大程度上可以幫助自己理清邏輯例诀。
多寫多練
多多練習吧随抠！
下面寫幾個練習題
代碼實現(xiàn)單鏈列表
class SinglyLinkedList {
private Node head = null;
void insertToHead(Node node) {
if (head == null) {
head = node;
} else {
node.next = head;
head = node;
}
System.out.println("insert head " + node.value + " data:\t" + toString());
}
void insertToHead(int value) {
insertToHead(createNode(value));
}
void insertAfter(Node node, Node newNode) {
if (node == null) return;
newNode.next = node.next;
node.next = newNode;
System.out.println("insertAfter data:\t" + toString());
}
void insertAfter(Node node, int value) {
insertAfter(node, createNode(value));
}
void insertBefore(Node before, Node newNode) {
if (before == null) return;
if (head == before) {
insertToHead(newNode);
return;
}
Node temp = head;
while (temp != null && temp.next != before) {
// 直到找打 before 的上個節(jié)點
temp = temp.next;
}
newNode.next = before;
temp.next = newNode;
System.out.println("insertBefore data:\t" + toString());
}
void insertBefore(Node before, int value) {
insertBefore(before, createNode(value));
}
Node findByValue(int value) {
Node temp = head;
while (temp != null && temp.value != value) {
temp = temp.next;
}
return temp;
}
Node findByIndex(int index) {
Node temp = head;
int pos = 0;
while (temp != null && pos != index) {
temp = temp.next;
pos++;
}
return temp;
}
void insertLast(Node node) {
if (head == null) {
head = node;
System.out.println("insert last " + node.value + " data:\t" + toString());
return;
}
Node temp = head;
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
System.out.println("insert last " + node.value + " data:\t" + toString());
}
void insertLast(int value) {
insertLast(createNode(value));
}
private Node createNode(int value) {
return new Node(null, value);
}
void deleteByValue(int value) {
if (head == null) {
return;
}
Node before = null;
Node current = head;
while (current != null && current.value != value) {
before = current;
current = current.next;
}
if (current == null) {
return;
}
if (before == null) {
head = head.next;
} else {
before.next = current.next;
}
System.out.println("deleteByValue:\t" + toString());
}
void deleteByNode(Node node) {
if (head == null || node == null) {
return;
}
Node temp = head;
while (temp != null && temp.next != node) {
temp = temp.next;
}
temp.next = node.next;
System.out.println("deleteByNode:\t" + toString());
}
@Override
public String toString() {
Node temp = head;
StringBuilder sb = new StringBuilder();
sb.append("[");
while (temp != null) {
sb.append(temp.value).append(",");
temp = temp.next;
}
sb.append("]");
return sb.toString();
}
static class Node {
int value;
Node next;
Node(Node next, int value) {
this.next = next;
this.value = value;
}
int getData() {
return value;
}
}
public static void main(String[] args) {
SinglyLinkedList linkedList = new SinglyLinkedList();
linkedList.insertLast(1);
linkedList.insertLast(2);
linkedList.insertLast(3);
linkedList.insertLast(4);
linkedList.insertToHead(5);
linkedList.insertAfter(linkedList.findByValue(3), 6);
linkedList.insertBefore(linkedList.findByValue(1), 7);
linkedList.deleteByValue(2);
linkedList.deleteByNode(linkedList.findByValue(1));
}
}
輸出結(jié)果：
insert last 1 data: [1,]
insert last 2 data: [1,2,]
insert last 3 data: [1,2,3,]
insert last 4 data: [1,2,3,4,]
insert head 5 data: [5,1,2,3,4,]
insertAfter data: [5,1,2,3,6,4,]
insertBefore data: [5,7,1,2,3,6,4,]
deleteByValue: [5,7,1,3,6,4,]
deleteByNode: [5,7,3,6,4,]
判斷是否為回文數(shù)
核心思想：使用兩個指針，一個慢指針繁涂，每次移動一個節(jié)點拱她，一個快指針，每次移動兩個節(jié)點扔罪。
private boolean isPalindrome() {
if (head == null || head.next == null) {
return false;
}
Node pre = null;
Node slow = head;
Node fast = head;
while (fast != null && fast.next != null) {
// 快指針每次跳兩個
fast = fast.next.next;
// 臨時指針指向下個節(jié)點
Node temp = slow.next;
// 將 slow 回轉(zhuǎn)
slow.next = pre;
pre = slow;
slow = temp;
}
if (fast != null) {
// 這種代表著節(jié)點數(shù)為偶數(shù)秉沼，slow 需要往后移動一位
slow = slow.next;
}
while (slow != null && pre != null) {
if (slow.value != pre.value) {
return false;
}
slow = slow.next;
pre = pre.next;
}
return true;
}
輸出結(jié)果
insert last 1 data: [1,]
insert last 2 data: [1,2,]
insert last 2 data: [1,2,2,]
insert last 1 data: [1,2,2,1,]
是否為回文函數(shù): true
節(jié)點回轉(zhuǎn)
核心思想：每次遍歷時，回轉(zhuǎn)節(jié)點的邏輯操作順序矿酵，且看代碼
private static Node reversed(Node node) {
if (node.next == null) {
return node;
}
Node pre = null;
while (node != null) {
// 現(xiàn)將下個節(jié)點用 temp 保存下來
Node temp = node.next;
node.next = pre;
pre = node;
node = temp;
}
return pre;
}
輸出結(jié)果：
01234
43210
判斷是否是循環(huán)節(jié)點
核心思想：循環(huán)節(jié)點的特點就在于鏈表的尾部指向頭部唬复，只需要是用快慢節(jié)點進行遍歷，如果不是循環(huán)節(jié)點全肮，循環(huán)一次就結(jié)束了敞咧。
/**
* 判斷是否是循環(huán)鏈表
* 快慢節(jié)點，如果兩者相等必然是循環(huán)鏈表辜腺，時間復雜度為 O(n)
*/
private static boolean isCircle(Node node) {
int count = 0;
Node slow = node;
Node fast = node;
while (slow != null && fast != null && fast.next != null) {
count++;
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
System.out.println("循環(huán)了 " + count + "次");
return true;
}
}
System.out.println("循環(huán)了 " + count + "次");
return false;
}
輸出結(jié)果
循環(huán)了 5次
is circle: true
拼接兩個有序節(jié)點
核心思想：首先創(chuàng)建一個空的頭節(jié)點休建，然后兩個有序鏈表依次遍歷乍恐，誰小就把這個空節(jié)點指向誰(默認從小到大排序)。其中需要注意的是丰包，如果一個節(jié)點提前結(jié)束了禁熏，那么就需要將新節(jié)點直接指向剩下的那個節(jié)點。
private static Node mergeNode(Node aNode, Node bNode) {
Node head = new Node(null, -1);
Node tail = head;
if (aNode == null) {
head = bNode;
}
if (bNode == null) {
head = aNode;
}
while (aNode != null && bNode != null) {
if (aNode.value > bNode.value) {
tail.next = bNode;
bNode = bNode.next;
} else {
tail.next = aNode;
aNode = aNode.next;
}
tail = tail.next;
}
if (aNode == null) {
tail.next = bNode;
}
if (bNode == null) {
tail.next = aNode;
}
if (head == null) {
return null;
}
return head.next;
}
輸出結(jié)果：
A 節(jié)點: 135
B 節(jié)點: 24689
12345689
刪除倒數(shù)第 N 個節(jié)點
核心思想：快慢指針邑彪，快的比慢 的多 N 個瞧毙，遍歷到最后，慢節(jié)點指向倒數(shù)第 N 個節(jié)點寄症，然后直接進行刪除宙彪。
/**
* 刪除倒數(shù) N 個節(jié)點
*
*/
private static void deleteLast(Node node, int n) {
int count = 0;
Node head = node;
while (head != null) {
count ++;
head = head.next;
}
if (n > count) {
return;
}
if (n == count) {
if (n == 1) {
node.next = null;
} else {
node.value = node.next.value;
node.next = node.next.next;
}
return;
}
Node slow = node;
Node fast = node;
int tempCount = 0;
while (slow != null && fast.next != null) {
if (tempCount < n) {
tempCount ++;
} else {
slow = slow.next;
}
fast = fast.next;
}
slow.next = slow.next.next;
}
輸出結(jié)果：
01234567
0124567
找出中間節(jié)點
核心思想：直接使用快慢指針進行遍歷，慢指針每次移動一個有巧，快指針每次移動兩個释漆。
private static int findMiddleNode(Node node) {
Node fast = node;
Node slow = node;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow.value;
}
輸出結(jié)果：
01234567
4
參考自極客時間
