摘要：在上一篇文章中，我們了解了隊列和棧的描述，現(xiàn)在讓我們來了解一下單鏈表和雙向鏈表的實現(xiàn)。單鏈表和雙向鏈表具有以下特點可動態(tài)分配空間，但不能隨機訪問。

在上一篇文章中，我們了解了隊列和棧的JavaScript描述，現(xiàn)在讓我們來了解一下 單鏈表 和雙向鏈表 的實現(xiàn)。本文的代碼并非所有都由本人所寫，只是出于學(xué)習(xí)目的，在此分享出來，并加上一定的解釋，便于大家學(xué)習(xí)。

本系列文章的代碼可在https://github.com/HolyZheng/...找到。

我們直入話題：

單鏈表 是存儲結(jié)構(gòu)的一種，它具有以下特點：

單鏈表不可隨機訪問

單鏈表不需要占連續(xù)的存儲空間，可動態(tài)分配

插入與刪除操作不需要移動多個元素

每個節(jié)點既存儲數(shù)據(jù)，又同時存儲指向下一節(jié)點的地址

現(xiàn)在我們創(chuàng)建一個單鏈表，并給它添加add、searchNode、remove 三個方法。
創(chuàng)建一個單鏈表：

//單鏈表
function SinglyList () {
    this._length = 0;
    this.head = null;
}

這個單鏈表暫時又兩個屬性： _length 鏈表的長度，head 鏈表頭節(jié)點。

每一個節(jié)點需要存儲數(shù)據(jù)，還要指向下一節(jié)點，所以為每個節(jié)點創(chuàng)建一個node類：

//結(jié)點
function Node (data) {
    this.data = data;
    this.next = null;
} 

node類 具有兩個屬性，data 存儲數(shù)據(jù)，next 指向下一節(jié)點。
現(xiàn)在我們?yōu)樗砑訋讉€基本的方法：add、searchNode 和 remove 函數(shù)。我們先實現(xiàn) add 方法，給單鏈表添加節(jié)點。在 add 方法中我們需要考慮兩中情況，分別為：單鏈表為空和單鏈表不為空。

//add方法

SinglyList.prototype.add = function (value) {
    var node = new Node(value),
        currentNode = this.head;
        
        //1st：當(dāng)單鏈表為空時
        if (!currentNode) {
            this.head = node;
            this._length++;
            return node;
        }

        //2nd：單鏈表不為空
        while (currentNode.next) {
            currentNode = currentNode.next;
        }

        currentNode.next = node;
        this._length++;
        return node;
}

可以看到在代碼中，我們先定義了一個 currentNode 變量，指向 this.head ，然后判斷如果當(dāng)前鏈表為空，直接將新節(jié)點賦值給 this.head ，如果不為空，先將currentNode指向最后的節(jié)點，然后再執(zhí)行 currentNode.next = node將新節(jié)點添加到鏈表的末尾。
再來實現(xiàn) searchNode 方法：
searchNode方法的作用是搜索特定位置的節(jié)點

//searchNode方法

SinglyList.prototype.searchNode = function (position) {
    var currentNode = this.head,
        length = this._length,
        message = {failure: "Failure: non-existent node in this list"};
    
    //1st：位置position非法
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    } 

    //2nd：位置position合法
    for (var i = 1; i < position; i++) {
        currentNode = currentNode.next;
    }
    return currentNode;
}

我們很簡單就實現(xiàn)了這個方法，先檢測鏈表是否為空和查詢的位置是否合法，不為空且位置合法的話，利用一個循環(huán)，將currentNode指向特定的position，然后就可以訪問到需要的節(jié)點了。

我們現(xiàn)在來看一下最后的一個方法： remove。 remove方法比起前兩個方法的話，要復(fù)雜一點，因為要考慮刪減了一個元素之后，還要保持整個鏈表的連續(xù)性。

//remove方法

SinglyList.prototype.remove = function (position) {
    var currentNode = this.head,
        length = this._length,
        message = {failure: "Failure: non-existent node in this list"},
        beforeNodeToDelete = null,
        nodeToDelete = null;
    
    //1st 位置position非法
    if (position < 0 || position > length) {
        throw new Error(message.failure);
    }

    //2nd 位置position為 1
    if (position === 1) {
        this.head = currentNode.next;
        nodeToDelete = currentNode;
        currentNode = null;
        this._length--;
        return nodeToDelete;
    }

    //3rd position為其他位子
    for(var i = 1; i < position; i++) {
        beforeNodeToDelete = currentNode;
        nodeToDelete = currentNode.next;
        
        currentNode = currentNode.next;
    }

    beforeNodeToDelete.next = nodeToDelete.next;
    currentNode = null;
    this._length--;
    return nodeToDelete;
}

首先檢查 position 的值是否合法，然后看position的值是否為 1，如果為 1 那就好辦了，將 this.head 指向原this.head.next，然后長度減 1 即可。如果position為其他位置，那就要先拿到 要刪除節(jié)點的前一節(jié)點 <和 要刪除的節(jié)點 然后將前一節(jié)點的next指向要刪除節(jié)點的next，以保持刪除節(jié)點后，鏈表的連續(xù)。理解了這點，那就基本可以理解代碼了。

雙向鏈表就是在單鏈表的基礎(chǔ)上，添加了一個指向當(dāng)前結(jié)點的前驅(qū)的變量，這樣就可以方便的由后繼來找到其前驅(qū)，就可以雙向的訪問鏈表。
同樣我們先來創(chuàng)建一個 結(jié)點類 ：

//節(jié)點類

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

可以看到這里多了一個 this.previous ，作用就是指向它的前驅(qū)。

然后再來看一下雙向鏈表這個類：

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

比起 單鏈表， 雙向鏈表 多了一個指向尾結(jié)點的 this.tail。
同樣，在這里我們實現(xiàn) add、searchNode 和 remove 三個方法。先來看 add 方法：

//add方法

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;
}

在插入新結(jié)點的時候我們一如既往的需要檢查鏈表是否為空，如果鏈表為空，就將 this.head 和 this.tail 都指向新結(jié)點，如果不為空，那就將新結(jié)點添加到鏈表末尾，并將新結(jié)點的 previous 指向原 this.tail 。這樣就完成了 add 方法。

searchNode方法：

//searchNode

DoublyList.prototype.searchNode = function (position) {
    var currentNode = this.head,
        length = this._length,
        message = {failure: "Failure: non-existent node in this list"};
    if(length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }
    for (var i = 1; i < position; i++) {
        currentNode = currentNode.next;
    }
    return currentNode;
}

雙向鏈表的searchNode方法和單鏈表的差不多，都是借助循環(huán)直接拿到要訪問的結(jié)點。

最后是最復(fù)雜的remove方法

//remove方法

DoublyList.prototype.remove = function (position) {
    var currentNode = this.head,
        length = this._length,
        message = {failure: "Failure: non-existent node in this list"},
        beforeNodeToDelete = null,
        nodeToDelete = null,
        afterNodeToDelete = null;
    
    //1st: 位置position非法
    if (length === 0 || position < 1 || position > length) {
        throw new Error(message.failure);
    }

    //2nd 位置為第一個節(jié)點
    if (position === 1) {
        nodeToDelete = this.head;
        this.head = currentNode.next;
        if (this.head) {
            this.head.previous = null;
        } else {
            this.tail = null;
        }
    //3rd 位置為最后一個節(jié)點
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    //4th 位置為其他節(jié)點
    } else {
        for (var i = 1; i < position; i++) {
            currentNode = currentNode.next;
        }
        beforeNodeToDelete = currentNode.previous;
        nodeToDelete = currentNode;
        afterNodeToDelete = currentNode.next;

        beforeNodeToDelete.next = afterNodeToDelete;
        afterNodeToDelete.previous = beforeNodeToDelete;
    }
    this._length--;
    return nodeToDelete;
}

remove方法要對傳進來的 position 進行判斷，分成 4 種情況，

分別為：

position非法，拋出錯誤。

position為 1，將this.head 指向下一個結(jié)點，然后將this.head.previous = null，這時要判斷一下 this.head 是否為空，如果為空就表明這個雙向鏈表原本只有一個結(jié)點，所以 remove 后 需要把 this.tail = null 。

當(dāng) position 為最后一個結(jié)點時，我們把 this.tail 前移this.tail = this.tail.previous，此時 this.tail 指向倒數(shù)第二個結(jié)點，再執(zhí)行this.tail.next = null，就把最后一個結(jié)點remove掉了

最復(fù)雜的情況，position 為其他位置，我們先定位到要remove掉的結(jié)點，然后將要刪除結(jié)點的前一結(jié)點與要刪除結(jié)點的后一結(jié)點鏈接起來，就把要刪除的結(jié)點remove掉了，既beforeNodeToDelete.next = afterNodeToDelete ; afterNodeToDelete.previous = beforeNodeToDelete

單鏈表和雙向鏈表，為存儲結(jié)構(gòu)的一種。

單鏈表和雙向鏈表具有以下特點：

可動態(tài)分配空間，但不能隨機訪問。

插入和刪除操作不需要移動多個元素

每個節(jié)點既存儲數(shù)據(jù)，又同時存儲指向下一節(jié)點的地址

雙向鏈表為在單鏈表的基礎(chǔ)上，添加了一個指向當(dāng)前結(jié)點的前驅(qū)的變量，這樣就可以方便的由后繼來找到其前驅(qū)，就可以雙向的訪問鏈表。