一、基礎(chǔ)

1、定義

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

2、相關(guān)概念

一個完整的鏈表需要由以下幾個部分組成：

1. 頭指針：一個普通的指針，它的特點(diǎn)是永遠(yuǎn)指向鏈表第一個結(jié)點(diǎn)的位置。
2. 結(jié)點(diǎn)：節(jié)點(diǎn)包含三類：頭結(jié)點(diǎn)、首元節(jié)點(diǎn)和其它節(jié)點(diǎn)。

(1)頭結(jié)點(diǎn)(非必須)：一個不存任何數(shù)據(jù)的空節(jié)點(diǎn)，通常作為鏈表的第一個節(jié)點(diǎn)。

(2)首元結(jié)點(diǎn)：鏈表中第一個存有數(shù)據(jù)的節(jié)點(diǎn)稱為首元結(jié)點(diǎn)。

(3)其它結(jié)點(diǎn)：鏈表中的其它結(jié)點(diǎn)。

3、結(jié)點(diǎn)包含內(nèi)容

鏈表中每個節(jié)點(diǎn)包含兩個部分：

1. 數(shù)據(jù)域：存儲數(shù)據(jù)元素本身。
2. 指針域：指向直接后續(xù)元素的指針。

二、鏈表分類及相關(guān)操作

鏈表存在很多種類，下面重點(diǎn)講述單向鏈表、雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)，以及其對應(yīng)的CURD(添加、更改、查找、刪除)。

1、 單向鏈表

對于單鏈表的相應(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ù)一個數(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)中存儲的數(shù)據(jù)元素進(jìn)行對比，直到對比成功或遍歷至鏈表最末端的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中情況:

1. 插入到鏈表的頭部。
2. 插入到鏈表中間的某個位置。
3. 插入到鏈表的最末端，作為鏈表中最后一個數(shù)據(jù)元素。

插入思想

1. 將新結(jié)點(diǎn)的next指針指向插入位置后的結(jié)點(diǎn)。
2. 將插入位置前結(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）刪除

刪除的元素的時候要注意鏈表的結(jié)構(gòu)，注意有沒有空值的頭結(jié)點(diǎn)，有頭結(jié)點(diǎn)的時候刪除的時候就不需要判斷刪除的是不是第一個值，否則需要進(jìn)行判斷。

function delVal(head, val) {
    // 當(dāng)一個結(jié)點(diǎn)也不存在時，直接返回空
    if (!head) {
        return null;
    }
    // 如果刪除的是第一個節(jié)點(diǎn)，直接將head指向第二個節(jié)點(diǎn)
    if (head.val === val) {
        head = head.next;
        return head;
    }
    // 如果刪除的不是第一個節(jié)點(diǎn)
    let current = head;
    // 找到待刪除元素的前一個值
    while (current.next && current.next.val !== val) {
        current = current.next;
    }
    if (current.next) {
        // 將刪除結(jié)點(diǎn)的前一個結(jié)點(diǎn)的next值直接指向刪除結(jié)點(diǎn)的下一個節(jié)點(diǎn)
        current.next = current.next.next;
    }
    return head;
}

（5）更改

更新鏈表中的元素，只需要通過遍歷找到存儲此元素的節(jié)點(diǎn)，對節(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、 雙向鏈表

單鏈表只有一個方向，從頭結(jié)點(diǎn)到尾結(jié)點(diǎn)，雙向鏈表指各個節(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)相比于單向鏈表，多了一個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é)點(diǎn)后插入結(jié)點(diǎn)，其思想是：

1. 找到該插入結(jié)點(diǎn)。
2. 將新結(jié)點(diǎn)的next指針指向插入位置后的結(jié)點(diǎn)。
3. 將新結(jié)點(diǎn)的prev指針指向插入位置的結(jié)點(diǎn)。
4. 將插入節(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)。

/**
 * 插入(在某個節(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)時，只需要遍歷鏈表找到要刪除的鏈表，然后將該鏈表從表中摘除即可。

(注：針對頭指針直線的結(jié)點(diǎn)需要做特殊處理，否則head永遠(yuǎn)指向的是原始的第一個節(jié)點(diǎn))。

/**
 * 刪除
 * 
 * 雙鏈表刪除結(jié)點(diǎn)時，只需要遍歷鏈表找到要刪除的鏈表，然后將該鏈表從表中摘除即可
 */
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é)點(diǎn)需要做特殊處理，否則head永遠(yuǎn)指向的是原始的第一個節(jié)點(diǎn)
                head = current.next;
            }
            return head;
        }
        current = current.next;
    }
    return null;
}

（5）更改

更新鏈表中的元素，只需要通過遍歷找到存儲此元素的節(jié)點(diǎn)，對節(jié)點(diǎn)中的數(shù)據(jù)域做更改操作即可。

/**
 * 更新
 * 
 * 更新鏈表中的元素，只需要通過遍歷找到存儲此元素的節(jié)點(diǎn)，對節(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;
}

當(dāng)前文章：美女面試官問我鏈表的CURD，我徹底懵圈了……
網(wǎng)址分享：http://uogjgqi.cn/article/cdohghj.html