日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
美女面試官問我鏈表的CURD，我徹底懵圈了……

一、基礎(chǔ)

1、定義

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

2、相關(guān)概念

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

  1. 頭指針：一個普通的指針，它的特點是永遠(yuǎn)指向鏈表第一個結(jié)點的位置。
  2. 結(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é)點包含兩個部分：

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

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

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

1、 單向鏈表

對于單鏈表的相應(yīng)編程，我們均按照默認(rèn)頭指針指向首元結(jié)點這樣的結(jié)構(gòu)進(jìn)行代碼實現(xiàn)。

（1）結(jié)點結(jié)構(gòu)

結(jié)點作為鏈表的重要組成部分，其結(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é)點，用被查找元素與各結(jié)點中存儲的數(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é)點的next指針指向插入位置后的結(jié)點。
  2. 將插入位置前結(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é)點的時候刪除的時候就不需要判斷刪除的是不是第一個值，否則需要進(jìn)行判斷。

function delVal(head, val) {
    // 當(dāng)一個結(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é)點，其思想是：

  1. 找到該插入結(jié)點。
  2. 將新結(jié)點的next指針指向插入位置后的結(jié)點。
  3. 將新結(jié)點的prev指針指向插入位置的結(jié)點。
  4. 將插入節(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永遠(yuǎn)指向的是原始的第一個節(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永遠(yuǎn)指向的是原始的第一個節(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;
}

當(dāng)前文章：美女面試官問我鏈表的CURD，我徹底懵圈了……
標(biāo)題鏈接：http://www.5511xx.com/article/cdohghj.html