摘要：最近在看數(shù)據(jù)結(jié)構(gòu)與算法，但是一直搞不明白在代碼中的實(shí)現(xiàn)。今天結(jié)合找到的一些資料總結(jié)一下鏈表在中的實(shí)現(xiàn)。這種結(jié)構(gòu)允許在迭代期間有效地從序列中的任何位置插入或刪除元素。

最近在看js數(shù)據(jù)結(jié)構(gòu)與算法，但是一直搞不明白在代碼中的實(shí)現(xiàn)。今天結(jié)合找到的一些資料總結(jié)一下鏈表在js中的實(shí)現(xiàn)。
首先說(shuō)下鏈表，在計(jì)算機(jī)科學(xué)中, 一個(gè)鏈表是數(shù)據(jù)元素的線(xiàn)性集合, 元素的線(xiàn)性順序不是由它們?cè)趦?nèi)存中的物理位置給出的。相反，每個(gè)元素指向下一個(gè)元素。它是由一組節(jié)點(diǎn)組成的數(shù)據(jù)結(jié)構(gòu),這些節(jié)點(diǎn)一起表示序列。在最簡(jiǎn)單的形式下，每個(gè)節(jié)點(diǎn)由數(shù)據(jù)和到序列中下一個(gè)節(jié)點(diǎn)的引用(換句話(huà)說(shuō)，鏈接)組成。這種結(jié)構(gòu)允許在迭代期間有效地從序列中的任何位置插入或刪除元素。關(guān)于鏈表更多的說(shuō)明請(qǐng)參考鏈接描述

大致了解了鏈表的概念之后我們就看下鏈表在js代碼中的實(shí)現(xiàn)：

單向鏈表

//這里element存放的是該節(jié)點(diǎn)上的數(shù)據(jù)，next存放的是指向下一個(gè)節(jié)點(diǎn)的鏈接
function Node(element){
    this.element = element;
    this.next = null;
}
//接下來(lái)構(gòu)建一個(gè)List類(lèi)
function List(node){
    this.node = new Node(node);
    //查找節(jié)點(diǎn)
    this.find = function(target){
        var current = this.node;
        while(current.element != target){
            current = current.next;
            if(!current){
                return false;
            }
        }
        return current;
    };
    //插入節(jié)點(diǎn)
    this.insert = function(newNode, target){
        var newnode = new Node(newNode);
        var current = this.find(target);
        newnode.next = current.next;
        current.next = newnode;
    };
    //查找前一個(gè)節(jié)點(diǎn)
    this.findPre = function(item){
        var current = this.node;
        while(!current.next && current.next.element != item){
            current = current.next; 
        }
        return current;
    };
    //刪除節(jié)點(diǎn)
    this.delete = function(target){
        var deltarget = this.find(target); 
        this.findPre(deltarget).next = deltarget.next;
    };
}

執(zhí)行查找節(jié)點(diǎn)操作，可見(jiàn)如下輸出：

執(zhí)行插入節(jié)點(diǎn)操作，可見(jiàn)：

執(zhí)行刪除節(jié)點(diǎn)操作，可見(jiàn)：

雙向鏈表

在計(jì)算機(jī)科學(xué)中, 一個(gè)雙向鏈表(doubly linked list) 是由一組稱(chēng)為節(jié)點(diǎn)的順序鏈接記錄組成的鏈接數(shù)據(jù)結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)包含兩個(gè)字段，稱(chēng)為鏈接，它們是對(duì)節(jié)點(diǎn)序列中上一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的引用。開(kāi)始節(jié)點(diǎn)和結(jié)束節(jié)點(diǎn)的上一個(gè)鏈接和下一個(gè)鏈接分別指向某種終止節(jié)點(diǎn)，通常是前哨節(jié)點(diǎn)或null，以方便遍歷列表。如果只有一個(gè)前哨節(jié)點(diǎn)，則列表通過(guò)前哨節(jié)點(diǎn)循環(huán)鏈接。它可以被概念化為兩個(gè)由相同數(shù)據(jù)項(xiàng)組成的單鏈表，但順序相反。

function Node(element){
    this.pre = null;
    this.element = element;
    this.next = null;
}
function List(node){
    this.node = new Node(node);
    this.find = function(target){
        var current = this.node;
        while(current.element != target){
            current = current.next;
            if(current == null){
                return false;
            }
        }
        return current;
    };
    this.insert = function(newNode, target){
        var target = this.find(target);
        var newNode = new Node(newNode);
        newNode.next = target.next;
        newNode.pre = target;
        target.next = newNode;
    };
    this.delete = function(delNode){
        var delNode = this.find(delNode);
        delNode.next.pre = delNode.pre;
        delNode.pre.next = delNode.next;
    };
}
var list = new List("a");
list.insert("b", "a");
list.insert("c", "b");
list.delete("b");
console.log(list);