javascript中的鏈表結(jié)構(gòu)

1.定義

　　很多編程語言中數(shù)組的長(zhǎng)度是固定的，就是定義數(shù)組的時(shí)候需要定義數(shù)組的長(zhǎng)度，所以當(dāng)數(shù)組已經(jīng)被數(shù)據(jù)填滿的時(shí)候，需要再加入新的元素就很困難。只能說在部分變成語言中會(huì)有這種情況，在javascript中和php中數(shù)組的長(zhǎng)度是可以任意增加的。在數(shù)組中添加和刪除元素也是比較麻煩，因?yàn)橐獙?shù)組中其他元素向前或者向后平移，這個(gè)在javascript中也不是問題，javascript中有一個(gè)很方便的方法splice()方法很方便的就可以添加或刪除元素。

　　但是凡是都是相對(duì)的，javascript中的數(shù)組也有自己的問題，他們被是成了對(duì)象，與其他語言（比如c++和java）相比它的效率很低。

　　如果在實(shí)際的使用中發(fā)現(xiàn)數(shù)組的效率很慢，就可以考慮使用鏈表來代替。數(shù)組還有個(gè)優(yōu)勢(shì)是可以根據(jù)鍵值很方便的訪問數(shù)組的值，除此之外，鏈表在任何場(chǎng)合都可以代替數(shù)組。如果需要隨機(jī)地訪問元素，數(shù)組仍然是更好的選擇。

　　鏈表是由一組節(jié)點(diǎn)組成的集合。每一個(gè)節(jié)點(diǎn)都使用一個(gè)對(duì)象的引用指向它的后續(xù)借點(diǎn)。指向另外一個(gè)借點(diǎn)的引用叫做鏈。

　　數(shù)組元素靠它們的位置進(jìn)行引用，鏈表元素則是靠相互之間的關(guān)系進(jìn)行引用。在數(shù)組中會(huì)說這個(gè)元素是數(shù)組中的第幾個(gè)元素，但是在鏈表中就說這個(gè)元素是某個(gè)元素的后面一個(gè)元素。遍歷鏈表就是跟著鏈表從鏈表的頭元素（head）一直走到尾元素（但是不包含鏈表的頭借點(diǎn)，頭通常用來作為鏈表的接入點(diǎn)）。還有一個(gè)問題，鏈表的尾元素指向一個(gè)null節(jié)點(diǎn)。如下圖1

圖1

　　許多鏈表的實(shí)現(xiàn)都在鏈表前面有一個(gè)特殊的節(jié)點(diǎn)，叫做頭節(jié)點(diǎn)。最后一個(gè)節(jié)點(diǎn)指向null，所有最后再加上一個(gè)null節(jié)點(diǎn)。如下圖2

圖2

　　在鏈表中插入一個(gè)節(jié)點(diǎn)的效率很高。向鏈表中插入一個(gè)節(jié)點(diǎn)，需要修改它前面的節(jié)點(diǎn)，使其指向新加入的節(jié)點(diǎn)，而新加入的節(jié)點(diǎn)則指向前面指向的節(jié)點(diǎn)。如下圖展示的是在eggs后面加上cookies節(jié)點(diǎn)。如下圖3.

圖3

 　　從鏈表中刪除一個(gè)節(jié)點(diǎn)也很簡(jiǎn)單，將待刪除的元素的前驅(qū)節(jié)點(diǎn)指向待刪除的后續(xù)節(jié)點(diǎn)，同時(shí)將待刪除元素指向null來釋放。下圖是一個(gè)巧合刪除是的null元素前面的一個(gè)元素。如下圖4

圖4

2.代碼實(shí)現(xiàn)

　　在下面的鏈表實(shí)現(xiàn)中有兩個(gè)類。node類用來標(biāo)識(shí)節(jié)點(diǎn)，LinkedList類提供插入節(jié)點(diǎn)，刪除節(jié)點(diǎn)，顯示鏈表節(jié)點(diǎn)元素的方法，以及一些其他的輔助方法。

　　Node類包含兩個(gè)屬性，element用來保存節(jié)點(diǎn)上的數(shù)據(jù)，next用來保存指向下一個(gè)節(jié)點(diǎn)的鏈接。我們使用一個(gè)構(gòu)造函數(shù)來創(chuàng)建節(jié)點(diǎn)，改構(gòu)造函數(shù)設(shè)置了這兩個(gè)屬性的值。如下：

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

　　LinkedList類提供了對(duì)鏈表進(jìn)行操作的方法，該類的功能包含插入節(jié)點(diǎn)，在鏈表中查找給定的節(jié)點(diǎn)。該類也有一個(gè)構(gòu)造函數(shù)，鏈表只有一個(gè)屬性，那就是使用一個(gè)node對(duì)象來保存該鏈表的頭結(jié)點(diǎn)，代碼如下：

function LList(){
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    //this.remove = remove;
    this.display = display;
}

　　head節(jié)點(diǎn)的next屬性被初始華為null，當(dāng)有新元素插入時(shí)，next會(huì)指向新的元素。

　　插入節(jié)點(diǎn)的方法是insert，該方法向鏈表中插入新節(jié)點(diǎn)的時(shí)候，需要明確指出在那個(gè)節(jié)點(diǎn)的前面或者后面插入。這里先討論在一個(gè)已知節(jié)點(diǎn)的后面插入元素。在元素后面插入元素的時(shí)候不，需要先找到“后面”的節(jié)點(diǎn)。為此創(chuàng)建一個(gè)輔助方法find()，該方法遍歷鏈表，查找指定的數(shù)據(jù)，如果找到該數(shù)據(jù)，就返回保存該數(shù)據(jù)的節(jié)點(diǎn)，find()方法的實(shí)現(xiàn)的代碼如下：

function find(item){
    var currNode = this.head;
    while (currNode.element != item){
        currNode = currNode.next;
    }
    return currNode;
}

　　find()方法演示了如何在鏈表上移動(dòng)。首先創(chuàng)建一個(gè)新節(jié)點(diǎn)，并將鏈表的頭節(jié)點(diǎn)賦給這個(gè)新創(chuàng)建的節(jié)點(diǎn)。然后再鏈表上進(jìn)行循環(huán)，如果當(dāng)前節(jié)點(diǎn)的element屬性和我們要找的信息不符合，就從當(dāng)前節(jié)點(diǎn)移動(dòng)到下一個(gè)節(jié)點(diǎn)。如果查找成功個(gè)，該方法返回包含該數(shù)據(jù)的節(jié)點(diǎn)，否則返回null。

　　一旦找到“后面”的節(jié)點(diǎn)，就可以將新節(jié)點(diǎn)插入鏈表了。首先，將新節(jié)點(diǎn)的next屬性設(shè)置為“后面”節(jié)點(diǎn)對(duì)應(yīng)的值，然后設(shè)置“后面”節(jié)點(diǎn)的next屬性指向新的節(jié)點(diǎn)，insert()定義如下：

//插入一個(gè)元素
function insert(newElement, item){
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

　　最后，我們定義一個(gè)打印鏈表元素的方法，如下：

function display(){
    var currNode = this.head;
    while (!(currNode.next == null)){
        document.write(currNode.next.element + ' ');
        currNode = currNode.next;
    }
}

　　這個(gè)方法首先將鏈表的頭賦給一個(gè)變量，然后循環(huán)遍歷鏈表，當(dāng)前節(jié)點(diǎn)的next屬性為null的時(shí)候循環(huán)結(jié)束。為了只顯示包含數(shù)據(jù)的節(jié)點(diǎn)，我們使用currNode.next.element表達(dá)式來訪問節(jié)點(diǎn)中的數(shù)據(jù)。

　　最后我們用下面的代碼來測(cè)試鏈表。在鏈表中保存幾個(gè)美國(guó)城市"Conway"，"Russellville"，"Alma"并將他們打印出來，完整代碼如下：

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

function LList(){
    this.head = new Node('head');
    this.find = find;
    this.insert = insert;
    //this.remove = remove;
    this.display = display;
}

function find(item){
    var currNode = this.head;
    while (currNode.element != item){
        currNode = currNode.next;
    }
    return currNode;
}

//插入一個(gè)元素
function insert(newElement, item){
    var newNode = new Node(newElement);
    var current = this.find(item);
    newNode.next = current.next;
    current.next = newNode;
}

function display(){
    var currNode = this.head;
    while (!(currNode.next == null)){
        document.write(currNode.next.element + ' ');
        currNode = currNode.next;
    }
}


//測(cè)試程序
var cities = new LList();
cities.insert("Conway", "head");
cities.insert("Russellville", "Conway");
cities.insert("Alma", "Russellville");
cities.display();

最后輸出的結(jié)果如下：