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