美女面試官問我鏈表的CURD，我徹底懵圈了……
一、基礎(chǔ)
1、定義
鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。
2、相關(guān)概念
一個完整的鏈表需要由以下幾個部分組成：
- 頭指針：一個普通的指針，它的特點是永遠指向鏈表第一個結(jié)點的位置。
- 結(jié)點：節(jié)點包含三類：頭結(jié)點、首元節(jié)點和其它節(jié)點。
(1)頭結(jié)點(非必須)：一個不存任何數(shù)據(jù)的空節(jié)點，通常作為鏈表的第一個節(jié)點。
(2)首元結(jié)點：鏈表中第一個存有數(shù)據(jù)的節(jié)點稱為首元結(jié)點。
(3)其它結(jié)點：鏈表中的其它結(jié)點。
3、結(jié)點包含內(nèi)容
鏈表中每個節(jié)點包含兩個部分：
- 數(shù)據(jù)域：存儲數(shù)據(jù)元素本身。
- 指針域：指向直接后續(xù)元素的指針。
二、鏈表分類及相關(guān)操作
鏈表存在很多種類，下面重點講述單向鏈表、雙向鏈表的結(jié)點結(jié)構(gòu)，以及其對應(yīng)的CURD(添加、更改、查找、刪除)。
1、 單向鏈表
對于單鏈表的相應(yīng)編程，我們均按照默認頭指針指向首元結(jié)點這樣的結(jié)構(gòu)進行代碼實現(xiàn)。
（1）結(jié)點結(jié)構(gòu)
結(jié)點作為鏈表的重要組成部分，其結(jié)構(gòu)可用如下代碼表示：
function ListNode(val, next) {
this.val = val;
this.next = next === undefined ? null : next;
}
擴展：如何根據(jù)一個數(shù)組創(chuàng)建鏈表。
function createLinkedList(arr) {
const head = new ListNode(arr[0]);
let current = head;
for (let i = 1; i < arr.length; i++) {
const node = new ListNode(arr[i]);
current.next = node;
current = current.next;
}
return head;
}
（2）遍歷(查找)
在鏈表中查找指定數(shù)據(jù)元素，其思路是從表頭依次遍歷表中節(jié)點，用被查找元素與各結(jié)點中存儲的數(shù)據(jù)元素進行對比，直到對比成功或遍歷至鏈表最末端的null。
// 查找
function selectVal(head, val) {
let current = head;
// 判斷是否為null
while (current) {
// 判斷是否對比成功
if (current.val === val) {
return current;
}
current = current.next;
}
return null;
}
（3）添加
向鏈表中添加元素，根據(jù)添加位置不同，可分為3中情況:
- 插入到鏈表的頭部。
- 插入到鏈表中間的某個位置。
- 插入到鏈表的最末端，作為鏈表中最后一個數(shù)據(jù)元素。
插入思想
- 將新結(jié)點的next指針指向插入位置后的結(jié)點。
- 將插入位置前結(jié)點的next指針指向插入結(jié)點。
function insertVal(head, val, add) {
const newNode = new ListNode(add);
// 查找插入節(jié)點
const currentNode = selectVal(head, val);
if (!currentNode) {
return null;
}
// 1. 將新結(jié)點的next指針指向插入位置后的節(jié)點
newNode.next = currentNode.next;
// 2. 將插入位置前節(jié)點的next指針指向插入節(jié)點
currentNode.next = newNode;
return head;
}
（4）刪除
刪除的元素的時候要注意鏈表的結(jié)構(gòu)，注意有沒有空值的頭結(jié)點，有頭結(jié)點的時候刪除的時候就不需要判斷刪除的是不是第一個值，否則需要進行判斷。
function delVal(head, val) {
// 當一個結(jié)點也不存在時，直接返回空
if (!head) {
return null;
}
// 如果刪除的是第一個節(jié)點，直接將head指向第二個節(jié)點
if (head.val === val) {
head = head.next;
return head;
}
// 如果刪除的不是第一個節(jié)點
let current = head;
// 找到待刪除元素的前一個值
while (current.next && current.next.val !== val) {
current = current.next;
}
if (current.next) {
// 將刪除結(jié)點的前一個結(jié)點的next值直接指向刪除結(jié)點的下一個節(jié)點
current.next = current.next.next;
}
return head;
}
（5）更改
更新鏈表中的元素，只需要通過遍歷找到存儲此元素的節(jié)點，對節(jié)點中的數(shù)據(jù)域做更改操作即可。
function updateVal(head, val, newVal) {
let current = head;
while (current) {
if (current.val === val) {
current.val = newVal;
return head;
}
current = current.next;
}
return null;
}
2、 雙向鏈表
單鏈表只有一個方向，從頭結(jié)點到尾結(jié)點，雙向鏈表指各個節(jié)點之間的邏輯關(guān)系是雙向的，其結(jié)點結(jié)構(gòu)和鏈表結(jié)構(gòu)如下所示：
結(jié)點結(jié)構(gòu)：
鏈表結(jié)構(gòu)：
（1）結(jié)點結(jié)構(gòu)
雙向鏈表的節(jié)點結(jié)構(gòu)相比于單向鏈表，多了一個prev屬性，如下所示：
function ListNode(val, prev, next) {
this.val = val;
this.prev = prev === undefined ? null : prev;
this.next = next === undefined ? null : next;
}
（2）遍歷(查找)
雙向鏈表的查找和單向鏈表的查找類似，都是遍歷鏈表。
function selectVal(head, val) {
let current = head;
while (current) {
if (current.val === val) {
return current;
}
current = current.next;
}
return null;
}
（3）添加
在某個節(jié)點后插入結(jié)點，其思想是：
- 找到該插入結(jié)點。
- 將新結(jié)點的next指針指向插入位置后的結(jié)點。
- 將新結(jié)點的prev指針指向插入位置的結(jié)點。
- 將插入節(jié)點的next指針指向新結(jié)點。
/**
* 插入(在某個節(jié)點后插入)
*/
function insertVal(head, val, add) {
const newNode = new ListNode(add);
// 查找插入節(jié)點
const currentNode = selectVal(head, val);
if (!currentNode) {
return null;
}
// 1. 將新結(jié)點的next指針指向插入位置后的結(jié)點
newNode.next = currentNode.next;
// 2. 將新結(jié)點的prev指針指向插入位置的結(jié)點
newNode.prev = currentNode;
// 3. 將插入節(jié)點的next指針指向新結(jié)點
currentNode.next = newNode;
return head;
}
（4）刪除
雙鏈表刪除結(jié)點時，只需要遍歷鏈表找到要刪除的鏈表，然后將該鏈表從表中摘除即可。
(注：針對頭指針直線的結(jié)點需要做特殊處理，否則head永遠指向的是原始的第一個節(jié)點)。
/**
* 刪除
*
* 雙鏈表刪除結(jié)點時，只需要遍歷鏈表找到要刪除的鏈表，然后將該鏈表從表中摘除即可
*/
function delVal(head, val) {
let current = head;
while (current) {
if (current.val === val) {
if (current.next) {
current.next.prev = current.prev;
}
if (current.prev) {
current.prev.next = current.next;
} else {
// 針對頭指針直線的結(jié)點需要做特殊處理，否則head永遠指向的是原始的第一個節(jié)點
head = current.next;
}
return head;
}
current = current.next;
}
return null;
}
（5）更改
更新鏈表中的元素，只需要通過遍歷找到存儲此元素的節(jié)點，對節(jié)點中的數(shù)據(jù)域做更改操作即可。
/**
* 更新
*
* 更新鏈表中的元素，只需要通過遍歷找到存儲此元素的節(jié)點，對節(jié)點中的數(shù)據(jù)域做更改操作即可
*/
function updateVal(head, val, newVal) {
let current = head;
while (current) {
if (current.val === val) {
current.val = newVal;
return head;
}
current = current.next;
}
return null;
}
