摘要：在上一篇文章中，我們了解了隊(duì)列和棧的描述，現(xiàn)在讓我們來(lái)了解一下單鏈表和雙向鏈表的實(shí)現(xiàn)。單鏈表和雙向鏈表具有以下特點(diǎn)可動(dòng)態(tài)分配空間，但不能隨機(jī)訪問(wèn)。

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

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

我們直入話題：

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

單鏈表不可隨機(jī)訪問(wèn)

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

插入與刪除操作不需要移動(dòng)多個(gè)元素

每個(gè)節(jié)點(diǎn)既存儲(chǔ)數(shù)據(jù)，又同時(shí)存儲(chǔ)指向下一節(jié)點(diǎn)的地址

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

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

這個(gè)單鏈表暫時(shí)又兩個(gè)屬性： _length 鏈表的長(zhǎng)度，head 鏈表頭節(jié)點(diǎn)。

每一個(gè)節(jié)點(diǎn)需要存儲(chǔ)數(shù)據(jù)，還要指向下一節(jié)點(diǎn)，所以為每個(gè)節(jié)點(diǎn)創(chuàng)建一個(gè)node類(lèi)：

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

node類(lèi) 具有兩個(gè)屬性，data 存儲(chǔ)數(shù)據(jù)，next 指向下一節(jié)點(diǎn)。
現(xiàn)在我們?yōu)樗砑訋讉€(gè)基本的方法：add、searchNode 和 remove 函數(shù)。我們先實(shí)現(xiàn) add 方法，給單鏈表添加節(jié)點(diǎn)。在 add 方法中我們需要考慮兩中情況，分別為：?jiǎn)捂湵頌榭蘸蛦捂湵聿粸榭铡?/p>

//add方法

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

        //2nd：?jiǎn)捂湵聿粸榭?        while (currentNode.next) {
            currentNode = currentNode.next;
        }

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

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

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

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

我們現(xiàn)在來(lái)看一下最后的一個(gè)方法： remove。 remove方法比起前兩個(gè)方法的話，要復(fù)雜一點(diǎn)，因?yàn)橐紤]刪減了一個(gè)元素之后，還要保持整個(gè)鏈表的連續(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，然后長(zhǎng)度減 1 即可。如果position為其他位置，那就要先拿到 要?jiǎng)h除節(jié)點(diǎn)的前一節(jié)點(diǎn) <和 要?jiǎng)h除的節(jié)點(diǎn) 然后將前一節(jié)點(diǎn)的next指向要?jiǎng)h除節(jié)點(diǎn)的next，以保持刪除節(jié)點(diǎn)后，鏈表的連續(xù)。理解了這點(diǎn)，那就基本可以理解代碼了。

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

//節(jié)點(diǎn)類(lèi)

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

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

然后再來(lái)看一下雙向鏈表這個(gè)類(lèi)：

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

比起 單鏈表， 雙向鏈表 多了一個(gè)指向尾結(jié)點(diǎn)的 this.tail。
同樣，在這里我們實(shí)現(xiàn) add、searchNode 和 remove 三個(gè)方法。先來(lái)看 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é)點(diǎn)的時(shí)候我們一如既往的需要檢查鏈表是否為空，如果鏈表為空，就將 this.head 和 this.tail 都指向新結(jié)點(diǎn)，如果不為空，那就將新結(jié)點(diǎn)添加到鏈表末尾，并將新結(jié)點(diǎn)的 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)直接拿到要訪問(wèn)的結(jié)點(diǎn)。

最后是最復(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 位置為第一個(gè)節(jié)點(diǎn)
    if (position === 1) {
        nodeToDelete = this.head;
        this.head = currentNode.next;
        if (this.head) {
            this.head.previous = null;
        } else {
            this.tail = null;
        }
    //3rd 位置為最后一個(gè)節(jié)點(diǎn)
    } else if (position === this._length) {
        this.tail = this.tail.previous;
        this.tail.next = null;
    //4th 位置為其他節(jié)點(diǎn)
    } 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方法要對(duì)傳進(jìn)來(lái)的 position 進(jìn)行判斷，分成 4 種情況，

分別為：

position非法，拋出錯(cuò)誤。

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

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

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

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

單鏈表和雙向鏈表具有以下特點(diǎn)：

可動(dòng)態(tài)分配空間，但不能隨機(jī)訪問(wèn)。

插入和刪除操作不需要移動(dòng)多個(gè)元素

每個(gè)節(jié)點(diǎn)既存儲(chǔ)數(shù)據(jù)，又同時(shí)存儲(chǔ)指向下一節(jié)點(diǎn)的地址

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