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