【譯】JavaScript數據結構（3）：單向鏈表與雙向鏈表

Chiclaim 發布于2019-08-20 18:20 / 828人閱讀

摘要：計算機科學中最常見的兩種數據結構是單鏈表和雙鏈表。雙向鏈表雙向鏈表具有單鏈表的所有功能，并將其擴展為在鏈表中可以進行雙向遍歷。雙向鏈表的操作我們的鏈表將包括兩個構造函數和。與單鏈表不同，雙向鏈表包含對鏈表開頭和結尾節點的引用。

翻譯：瘋狂的技術宅
英文：https://code.tutsplus.com/art...
說明：本文翻譯自系列文章《Data Structures With JavaScript》，總共為四篇，原作者是在美國硅谷工作的工程師 Cho S. Kim 。這是本系列的第三篇。

說明：本專欄文章首發于公眾號：jingchengyideng 。

計算機科學中最常見的兩種數據結構是單鏈表和雙鏈表。

在我學習這些數據結構的時候，曾經問我的同伴在生活中有沒有類似的概念。我所聽到的例子是購物清單和火車。但是我最終明白了，這些類比是不準確的，購物清單更類似隊列，火車則更像是一個數組。

隨著時間的推移，我終于發現了一個能夠準確類比單鏈表和雙向鏈表的例子：尋寶游戲。如果你對尋寶游戲和鏈表之間的關系感到好奇，請繼續往下讀。

單鏈表

在計算機科學中，單鏈表是一種數據結構，保存了一系列鏈接的節點。每個節點中包含數據和一個可指向另一個節點的指針。

單鏈列表的節點非常類似于尋寶游戲中的步驟。每個步驟都包含一條消息（例如“您已到達法國”）和指向下一步驟的指針（例如“訪問這些經緯度坐標”）。當我們開始對這些多帶帶的步驟進行排序并形成一系列步驟時，就是在玩一個尋寶游戲。

現在我們對單鏈表有了一個基本的概念，接下來討論單鏈表的操作

單鏈表的操作

因為單鏈表包含節點，這兩者的構造函數可以是兩個獨立的構造函數，所以我們需要些構造函數：Node 和 SinglyList

Node

data 存儲數據

next 指向鏈表中下一個節點的指針

SinglyList

_length 用于表示鏈表中的節點數量

head 分配一個節點作為鏈表的頭

add(value) 向鏈表中添加一個節點

searchNodeAt(position) 找到在列表中指定位置 n 上的節點

remove(position) 刪除指定位置的節點

單鏈表的實現

在實現時，我們首先定義一個名為Node的構造函數，然后定義一個名為SinglyList的構造函數。

Node 的每個實例都應該能夠存儲數據并且能夠指向另外一個節點。要實現此功能，我們將分別創建兩個屬性：data和next。

function Node(data) {
    this.data = data;
    this.next = null;
}

下一步我們定義SinglyList:

function SinglyList() {
    this._length = 0;
    this.head = null;
}

SinglyList 的每個實例有兩個屬性：_length和head。前者保存鏈表中的節點數，后者指向鏈表的頭部，鏈表前面的節點。由于新創建的singlylist實例不包含任何節點，所以head的默認值是null，_length的默認值是 0。

單鏈表的方法

我們需要定義可以從鏈表中添加、查找和刪除節點的方法。先從添加節點開始。

方法1/3: add(value)

太棒了，現在我們來實現將節點添加到鏈表的功能。

SinglyList.prototype.add = function(value) {
    var node = new Node(value),
        currentNode = this.head;
 
    // 1st use-case: an empty list 
    if (!currentNode) {
        this.head = node;
        this._length++;
         
        return node;
    }
 
    // 2nd use-case: a non-empty list
    while (currentNode.next) {
        currentNode = currentNode.next;
    }
 
    currentNode.next = node;
 
    this._length++;
     
    return node;
};

把節點添加到鏈表會涉及很多步驟。先從方法開始。我們使用add(value)的參數來創建一個節點的新實例，該節點被分配給名為node的變量。我們還聲明了一個名為currentNode的變量，并將其初始化為鏈表的_head。如果鏈表中還沒有節點，那么head的值為null。

實現了這一點之后，我們將處理兩種情況。

第一種情況考慮將節點添加到空的鏈表中，如果head沒有指向任何節點的話，那么將該node指定為鏈表的頭，同時鏈表的長度加一，并返回node。

第二種情況考慮將節點添加到飛空鏈表。我們進入while循環，在每次循環中，判斷currentNode.next是否指向下一個節點。（第一次循環時，CurrentNode指向鏈表的頭部。）

如果答案是否定的，我們會把currentnode.next指向新添加的節點，并返回node。

如果答案是肯定的，就進入while循環。在循環體中，我們將currentNode重新賦值給currentNode.next。重復這個過程，直到currentNode.next不再指向任何。換句話說，currentNode指向鏈表中的最后一個節點。

while循環結束后，使currentnode.next指向新添加的節點，同時_length加1，最后返回node。

方法2/3: searchNodeAt(position)

現在我們可以將節點添加到鏈表中了，但是還沒有辦法找到特定位置的節點。下面添加這個功能。創建一個名為searchNodeAt(position) 的方法，它接受一個名為 position 的參數。這個參數是個整數，用來表示鏈表中的位置n。

SinglyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: "Failure: non-existent node in this list."};
 
    // 1st use-case: an invalid position 
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: a valid position 
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
 
    return currentNode;
};

在if中檢查第一種情況：參數非法。

如果傳給searchNodeAt(position)的索引是有效的，那么我們執行第二種情況 —— while循環。在while的每次循環中，指向頭的currentNode被重新指向鏈表中的下一個節點。

這個循環不斷執行，一直到count等于position。

方法3/3: remove(position)

最后一個方法是remove(position)。

SinglyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 0,
        message = {failure: "Failure: non-existent node in this list."},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
 
    // 1st use-case: an invalid position
    if (position < 0 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
        deletedNode = currentNode;
        currentNode = null;
        this._length--;
         
        return deletedNode;
    }
 
    // 3rd use-case: any other node is removed
    while (count < position) {
        beforeNodeToDelete = currentNode;
        nodeToDelete = currentNode.next;
        count++;
    }
 
    beforeNodeToDelete.next = nodeToDelete.next;
    deletedNode = nodeToDelete;
    nodeToDelete = null;
    this._length--;
 
    return deletedNode;
};

我們要實現的remove(position)涉及三種情況：

無效的位置作為參數傳遞。

第一個位置（鏈表的的`head）作為參數的傳遞。

一個合法的位置（不是第一個位置）作為參數的傳遞。

前兩種情況是最簡單的處理。關于第一種情況，如果鏈表為空或傳入的位置不存在，則會拋出錯誤。

第二種情況處理鏈表中第一個節點的刪除，這也是頭節點。如果是這種情況，就執行下面的邏輯：

頭被重新賦值給currentNode.next。

deletedNode指向currentNode。

currentNode被重新賦值為null。

將的鏈表的長度減1。

返回deletedNode。

第三種情況是最難理解的。其復雜性在于我們要在每一次循環中操作兩個節點的必要性。在每次循環中，需要處理要刪除的節點和它前面的節點。當循環到要被刪除的位置的節點時，循環終止。

在這一點上，我們涉及到三個節點：
beforeNodeToDelete, nodeToDelete, 和 deletedNode。刪除nodeToDelete之前，必須先把它的next的值賦給beforeNodeToDelete的next，如果不清楚這一步驟的目的，可以提醒自己有一個節點負責鏈接其前后的其他節點，只需要刪除這個節點，就可以把鏈表斷開。

接下來，我們將deletedNode賦值給nodeToDelete。然后我們將nodeToDelete的值設置為null，將列表的長度減1，最后返回deletedNode。

單向鏈表的完整實現

以下是單向鏈表的完整實現：

function Node(data) {
    this.data = data;
    this.next = null;
}
 
function SinglyList() {
    this._length = 0;
    this.head = null;
}
 
SinglyList.prototype.add = function(value) {
    var node = new Node(value),
        currentNode = this.head;
 
    // 1st use-case: an empty list
    if (!currentNode) {
        this.head = node;
        this._length++;
 
        return node;
    }
 
    // 2nd use-case: a non-empty list
    while (currentNode.next) {
        currentNode = currentNode.next;
    }
 
    currentNode.next = node;
 
    this._length++;
     
    return node;
};
 
SinglyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: "Failure: non-existent node in this list."};
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: a valid position
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
 
    return currentNode;
};
 
SinglyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 0,
        message = {failure: "Failure: non-existent node in this list."},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
 
    // 1st use-case: an invalid position
    if (position < 0 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
        deletedNode = currentNode;
        currentNode = null;
        this._length--;
         
        return deletedNode;
    }
 
    // 3rd use-case: any other node is removed
    while (count < position) {
        beforeNodeToDelete = currentNode;
        nodeToDelete = currentNode.next;
        count++;
    }
 
    beforeNodeToDelete.next = nodeToDelete.next;
    deletedNode = nodeToDelete;
    nodeToDelete = null;
    this._length--;
 
    return deletedNode;
};

從單鏈表到雙鏈表

我們已經完整的實現了單鏈表，這真是極好的。現在可以在一個占用費連續的空間的鏈表結構中，進行添加、刪除和查找節點的操作了。

然而現在所有的操作都是從鏈表的起始位置開始，并運行到鏈表的結尾。換句話說，它們是單向的。

可能在某些情況下我們希望操作是雙向的。如果你考慮了這種可能性，那么你剛才就是描述了一個雙向鏈表。

雙向鏈表

雙向鏈表具有單鏈表的所有功能，并將其擴展為在鏈表中可以進行雙向遍歷。換句話說，我們可從鏈表中第一個節點遍歷到到最后一個節點；也可以從最后一個節點遍歷到第一個節點。

在本節中，我們將重點關注雙向鏈表和單鏈列表之間的差異。

雙向鏈表的操作

我們的鏈表將包括兩個構造函數：Node和DoublyList。看看他們是怎樣運作的。

Node

data 存儲數據。

next 指向鏈表中下一個節點的指針。

previous 指向鏈表中前一個節點的指針。

DoublyList

_length 保存鏈表中節點的個數

head 指定一個節點作為鏈表的頭節點

tail 指定一個節點作為鏈表的尾節點

add(value) 向鏈表中添加一個節點

searchNodeAt(position) 找到在列表中指定位置 n 上的節點

remove(position) 刪除鏈表中指定位置上的節點

雙向鏈表的實現

現在開始寫代碼！

在實現中，將會創建一個名為Node的構造函數：

function Node(value) {
    this.data = value;
    this.previous = null;
    this.next = null;
}

想要實現雙向鏈表的雙向遍歷，我們需要指向鏈表兩個方向的屬性。這些屬性被命名為previous和next。

接下來，我們需要實現DoublyList并添加三個屬性：_length，head和tail。

與單鏈表不同，雙向鏈表包含對鏈表開頭和結尾節點的引用。由于DoublyList剛被實例化時并不包含任何節點，所以head和tail的默認值都被設置為null。

function DoublyList() {
    this._length = 0;
    this.head = null;
    this.tail = null;
}

雙向鏈表的方法

接下來我們討論以下方法：add(value), remove(position), 和 searchNodeAt(position)。所有這些方法都用于單鏈表; 然而，它們必須備重寫為可以雙向遍歷。

方法1/3 add(value)

DoublyList.prototype.add = function(value) {
    var node = new Node(value);
 
    if (this._length) {
        this.tail.next = node;
        node.previous = this.tail;
        this.tail = node;
    } else {
        this.head = node;
        this.tail = node;
    }
 
    this._length++;
     
    return node;
};

在這個方法中，存在兩種可能。首先，如果鏈表是空的，則給它的head 和tail分配節點。其次，如果鏈表中已經存在節點，則查找鏈表的尾部并把心節點分配給tail.next；同樣，我們需要配置新的尾部以供進行雙向遍歷。換句話說，我們需要把tail.previous設置為原來的尾部。

方法2/3 searchNodeAt(position)

searchNodeAt(position)的實現與單鏈表相同。如果你忘記了如何實現它，請通過下面的代碼回憶：

DoublyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: "Failure: non-existent node in this list."};
 
    // 1st use-case: an invalid position 
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: a valid position 
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
 
    return currentNode;
};

方法3/3 remove(position)

理解這個方法是最具挑戰性的。我先寫出代碼，然后再解釋它。

DoublyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: "Failure: non-existent node in this list."},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
 
        // 2nd use-case: there is a second node
        if (!this.head) {
            this.head.previous = null;
        // 2nd use-case: there is no second node
        } else {
            this.tail = null;
        }
 
    // 3rd use-case: the last node is removed
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    // 4th use-case: a middle node is removed
    } else {
        while (count < position) {
            currentNode = currentNode.next;
            count++;
        }
 
        beforeNodeToDelete = currentNode.previous;
        nodeToDelete = currentNode;
        afterNodeToDelete = currentNode.next;
 
        beforeNodeToDelete.next = afterNodeToDelete;
        afterNodeToDelete.previous = beforeNodeToDelete;
        deletedNode = nodeToDelete;
        nodeToDelete = null;
    }
 
    this._length--;
 
    return message.success;
};

remove(position) 處理以下四種情況：

如果remove(position)的參數傳遞的位置存在, 將會拋出一個錯誤。

如果remove(position)的參數傳遞的位置是鏈表的第一個節點（head），將把head賦值給deletedNode ，然后把head重新分配到鏈表中的下一個節點。此時，我們必須考慮鏈表中否存在多個節點。如果答案為否，頭部將被分配為null，之后進入if-else語句的if部分。在if的代碼中，還必須將tail設置為null —— 換句話說，我們返回到一個空的雙向鏈表的初始狀態。如果刪除列表中的第一個節點，并且鏈表中存在多個節點，那么我們輸入if-else語句的else部分。在這種情況下，我們必須正確地將head的previous屬性設置為null —— 在鏈表的頭前面是沒有節點的。

如果remove(position)的參數傳遞的位置是鏈表的尾部，首先把tail賦值給deletedNode，然后tail被重新賦值為尾部之前的那個節點，最后新尾部后面沒有其他節點，需要將其next值設置為null。

這里發生了很多事情，所以我將重點關注邏輯，而不是每一行代碼。一旦CurrentNode指向的節點是將要被remove(position)刪除的節點時，就退出while循環。這時我們把nodeToDelete之后的節點重新賦值給beforeNodeToDelete.next。相應的，
把nodeToDelete之前的節點重新賦值給afterNodeToDelete.previous。——換句話說，我們把指向已刪除節點的指針，改為指向正確的節點。最后，把nodeToDelete 賦值為null。

最后，把鏈表的長度減1，返回deletedNode。

雙向鏈表的完整實現

function Node(value) {
    this.data = value;
    this.previous = null;
    this.next = null;
}
 
function DoublyList() {
    this._length = 0;
    this.head = null;
    this.tail = null;
}
 
DoublyList.prototype.add = function(value) {
    var node = new Node(value);
 
    if (this._length) {
        this.tail.next = node;
        node.previous = this.tail;
        this.tail = node;
    } else {
        this.head = node;
        this.tail = node;
    }
 
    this._length++;
 
    return node;
};
 
DoublyList.prototype.searchNodeAt = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: "Failure: non-existent node in this list."};
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: a valid position
    while (count < position) {
        currentNode = currentNode.next;
        count++;
    }
 
    return currentNode;
};
 
DoublyList.prototype.remove = function(position) {
    var currentNode = this.head,
        length = this._length,
        count = 1,
        message = {failure: "Failure: non-existent node in this list."},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        deletedNode = null;
 
    // 1st use-case: an invalid position
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
 
    // 2nd use-case: the first node is removed
    if (position === 1) {
        this.head = currentNode.next;
 
        // 2nd use-case: there is a second node
        if (!this.head) {
            this.head.previous = null;
        // 2nd use-case: there is no second node
        } else {
            this.tail = null;
        }
 
    // 3rd use-case: the last node is removed
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    // 4th use-case: a middle node is removed
    } else {
        while (count < position) {
            currentNode = currentNode.next;
            count++;
        }
 
        beforeNodeToDelete = currentNode.previous;
        nodeToDelete = currentNode;
        afterNodeToDelete = currentNode.next;
 
        beforeNodeToDelete.next = afterNodeToDelete;
        afterNodeToDelete.previous = beforeNodeToDelete;
        deletedNode = nodeToDelete;
        nodeToDelete = null;
    }
 
    this._length--;
 
    return message.success;
};

總結

本文中已經介紹了很多信息。如果其中任何地方看起來令人困惑，就再讀一遍并查看代碼。如果它最終對你有所幫助，我會感到自豪。你剛剛揭開了一個單鏈表和雙向鏈表的秘密，可以把這些數據結構添加到自己的編碼工具彈藥庫中！

歡迎掃描二維碼關注公眾號，每天推送我翻譯的技術文章。

云服務器 GPU云服務器單向鏈表詳解雙向鏈表 java雙向鏈表單向鏈表的操作c語言

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/84362.html

javascript數據結構與算法（一）單向鏈表與雙向鏈表

摘要：創建雙向鏈表創建節點繼承添加前繼指針初始化雙向鏈表對鏈表最后一個元素進行引用插入操作尾插法任意位置添加元素刪除操作刪除特定位置的元素查詢操作查詢元素的位置查詢尾部元素修改操作清空雙向鏈表雙向鏈表對象轉為字符串線性表（List）：零個或者多個數據元素的有限序列。線性表是一個序列，具有一對一的關系，而不能具備一對多的關系。線性表要求有限性，數據類型也要相同。本文參考的主要是大話數據結構...

William_Sang 2019-08-26 10:48 評論0 收藏0
學習JavaScript數據結構與算法（二）：鏈表

摘要：實現移除給定的元素要移除的元素返回值表示移除成功方法說明移除單向鏈表中某個位置的元素。的前端樂園原文鏈接寒假前端學習學習數據結構與算法二鏈表本系列的第一篇文章: 學習JavaScript數據結構與算法（一），棧與隊列第二篇文章：學習JavaScript數據結構與算法（二）：鏈表第三篇文章：學習JavaScript數據結構與算法（三）：集合第四篇文章：學習JavaScript數據結構與...

lolomaco 2019-08-22 11:00 評論0 收藏0
Javascript數據結構與算法（二）循環鏈表與有序鏈表

摘要：循環鏈表可以像單向鏈表引用，也可以像雙向鏈表有雙向引用。以下就以如何創建棧數據結構為例。循環鏈表可以像單向鏈表引用，也可以像雙向鏈表有雙向引用。性能上也跟雙向鏈表差不多，如果position大于length/2，那就可以從尾部開始迭代，可以減少迭代的元素。唯一的區別在于最后一個元素指向下一個元素的指針(tail.next)不是undefine，而是第一個元素（head）。接下來來看一...

YacaToy 2019-08-26 10:49 評論0 收藏0
JavaScript的數據結構與算法（四） —— 雙向鏈表

摘要：鏈表鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。鏈表又包括單向鏈表和雙向鏈表雙向鏈表雙向鏈表與單向鏈表很是相像。但在雙向鏈表中，還有指向上一個節點的鏈接，是雙向的。鏈表鏈表存儲有序的元素集合，但不同于數組，鏈表中的元素在內存中并不是連續放置的。每個元素由一個存儲元素本事的節點和一個指向下一個元素的引用組成。相對于傳統的數組，鏈表的一個好處在于，添加或...

Youngdze 2019-08-21 17:13 評論0 收藏0
2017-07-28 前端日報

2017-07-28 前端日報精選 React的新引擎—React Fiber是什么？Chromeless 讓 Chrome 自動化變得簡單【譯】JavaScript屬性名稱中的隱藏信息前端測試框架 JestES6中的JavaScript工廠函數Why Composition is Harder with ClassesGET READY: A NEW V8 IS COMING, NODE.JS...

golden_hamster 2019-08-20 18:22 評論0 收藏0