本文實例講述了JS中的算法與數據結構之鏈表(Linked-list)。分享給大家供大家參考，具體如下：
前面我們討論了如何使用棧、隊列進行存數數據，他們其實都是列表的一種，底層存儲的數據的數據結構都是數組。
但是數組不總是最佳的數據結構，因為，在很多編程語言中，數組的長度都是固定的，如果數組已被數據填滿，再要加入新的元素是非常困難的。而且，對于數組的刪除和添加操作，通常需要將數組中的其他元素向前或者向后平移，這些操作也是十分繁瑣的。
然而，JS中數組卻不存在上述問題，主要是因為他們被實現了成了對象，但是與其他語言相比（比如C或Java），那么它的效率會低很多。
這時候，我們可以考慮使用鏈表(Linked-list) 來替代它，除了對數據的隨機訪問，鏈表幾乎可以在任何可以使用一維數組的情況中。如果你正巧在使用C或者Java等高級語言，你會發現鏈表的表現要優于數組很多。
鏈表其實有許多的種類：單向鏈表、雙向鏈表、單向循環鏈表和雙向循環鏈表，接下來，我們基于對象來實現一個單向鏈表，因為它的使用最為廣泛。
首先，要實現鏈表，我們先搞懂一些鏈表的基本東西，因為這很重要！
鏈表是一組節點組成的集合，每個節點都使用一個對象的引用來指向它的后一個節點。指向另一節點的引用講做鏈。下面我畫了一個簡單的鏈接結構圖，方便大家理解。
鏈表結構圖
其中，data中保存著數據，next保存著下一個鏈表的引用。上圖中，我們說 data2 跟在 data1 后面，而不是說 data2 是鏈表中的第二個元素。上圖，值得注意的是，我們將鏈表的尾元素指向了 null 節點，表示鏈接結束的位置。
由于鏈表的起始點的確定比較麻煩，因此很多鏈表的實現都會在鏈表的最前面添加一個特殊的節點，稱為 頭節點，表示鏈表的頭部。進過改造，鏈表就成了如下的樣子：
有頭節點的鏈表
向鏈表中插入一個節點的效率很高，需要修改它前面的節點(前驅)，使其指向新加入的節點，而將新節點指向原來前驅節點指向的節點即可。下面我將用圖片演示如何在 data2 節點 后面插入 data4 節點。
插入節點
同樣，從鏈表中刪除一個節點，也很簡單。只需將待刪節點的前驅節點指向待刪節點的，同時將待刪節點指向null，那么節點就刪除成功了。下面我們用圖片演示如何從鏈表中刪除 data4 節點。
刪除節點
我們設計鏈表包含兩個類，一個是 Node 類用來表示節點，另一個事 LinkedList 類提供插入節點、刪除節點等一些操作。
Node類
Node類包含連個屬性： element 用來保存節點上的數據，next 用來保存指向下一個節點的鏈接，具體實現如下：
//節點function Node(element) { this.element = element; //當前節點的元素 this.next = null; //下一個節點鏈接}LinkedList類
LinkedList類提供了對鏈表進行操作的方法，包括插入刪除節點，查找給定的值等。值得注意的是，它只有一個屬性，那就是使用一個 Node 對象來保存該鏈表的頭節點。
它的構造函數的實現如下：
//鏈表類function LList () { this.head = new Node( 'head' ); //頭節點 this.find = find; //查找節點 this.insert = insert; //插入節點 this.remove = remove; //刪除節點 this.findPrev = findPrev; //查找前一個節點 this.display = display; //顯示鏈表}head節點的next屬性初始化為 null ，當有新元素插入時，next會指向新的元素。
接下來，我們來看看具體方法的實現。
insert：向鏈表插入一個節點
我們先分析分析insert方法，想要插入一個節點，我們必須明確要在哪個節點的前面或后面插入。我們先來看看，如何在一個已知節點的后面插入一個節點。
在一個已知節點后插入新節點，我們首先得找到該節點，為此，我們需要一個 find 方法用來遍歷鏈表，查找給定的數據。如果找到，該方法就返回保存該數據的節點。那么，我們先實現 find 方法。
find：查找給定節點
//查找給定節點function find ( item ) { var currNode = this.head; while ( currNode.element != item ){ currNode = currNode.next; } return currNode;}find 方法同時展示了如何在鏈表上移動。首先，創建一個新節點，將鏈表的頭節點賦給這個新創建的節點，然后在鏈表上循環，如果當前節點的 element 屬性和我們要找的信息不符，就將當前節點移動到下一個節點，如果查找成功，該方法返回包含該數據的節點；否則，就會返回null。
一旦找到了節點，我們就可以將新的節點插入到鏈表中了，將新節點的 next 屬性設置為后面節點的 next 屬性對應的值，然后設置后面節點的 next 屬性指向新的節點，具體實現如下：
//插入節點function insert ( newElement , item ) { var newNode = new Node( newElement ); var currNode = this.find( item ); newNode.next = currNode.next; currNode.next = newNode;}現在我們可以測試我們的鏈表了。等等，我們先來定義一個 display 方法顯示鏈表的元素，不然我們怎么知道對不對呢？
display：顯示鏈表
//顯示鏈表元素function display () { var currNode = this.head; while ( !(currNode.next == null) ){ console.log( currNode.next.element ); currNode = currNode.next; }}實現原理同上，將頭節點賦給一個新的變量，然后循環鏈表，直到當前節點的 next 屬性為 null 時停止循環，我們循環過程中將每個節點的數據打印出來就好了。
var fruits = new LList();fruits.insert('Apple' , 'head');fruits.insert('Banana' , 'Apple');fruits.insert('Pear' , 'Banana');console.log(fruits.display()); // Apple // Banana // Pearremove：從鏈表中刪除一個節點
從鏈表中刪除節點時，我們先要找個待刪除節點的前一個節點，找到后，我們修改它的 next 屬性，使其不在指向待刪除的節點，而是待刪除節點的下一個節點。那么，我們就得需要定義一個 findPrevious 方法遍歷鏈表，檢查每一個節點的下一個節點是否存儲待刪除的數據。如果找到，返回該節點，這樣就可以修改它的 next 屬性了。 findPrevious 的實現如下：//查找帶刪除節點的前一個節點function findPrev( item ) { var currNode = this.head; while ( !( currNode.next == null) && ( currNode.next.element != item )){ currNode = currNode.next; } return currNode;}這樣，remove 方法的實現也就迎刃而解了
//刪除節點function remove ( item ) { var prevNode = this.findPrev( item ); if( !( prevNode.next == null ) ){ prevNode.next = prevNode.next.next; }}我們接著寫一段測試程序，測試一下 remove 方法：
// 接著上面的代碼，我們再添加一個水果fruits.insert('Grape' , 'Pear');console.log(fruits.display()); // Apple // Banana // Pear // Grape// 我們把香蕉吃掉fruits.remove('Banana');console.log(fruits.display()); // Apple // Pear // GrapeGreat！成功了，現在你已經可以實現一個基本的單向鏈表了。
盡管從鏈表的頭節點遍歷鏈表很簡單，但是反過來，從后向前遍歷卻不容易。我們可以通過給Node類增加一個previous屬性，讓其指向前驅節點的鏈接，這樣就形成了雙向鏈表，如下圖：
雙向鏈表
此時，向鏈表插入一個節點就要更改節點的前驅和后繼了，但是刪除節點的效率提高了，不再需要尋找待刪除節點的前驅節點了。
要實現雙向鏈表，首先需要給 Node 類增加一個 previous 屬性：
//節點類function Node(element) { this.element = element; //當前節點的元素 this.next = null; //下一個節點鏈接 this.previous = null; //上一個節點鏈接}雙向鏈表的 insert 方法與單鏈表相似，但需要設置新節點的 previous 屬性，使其指向該節點的前驅，定義如下：
//插入節點function insert ( newElement , item ) { var newNode = new Node( newElement ); var currNode = this.find( item ); newNode.next = currNode.next; newNode.previous = currNode; currNode.next = newNode;}雙向鏈表的刪除 remove 方法比單鏈表效率高，不需要查找前驅節點，只要找出待刪除節點，然后將該節點的前驅 next 屬性指向待刪除節點的后繼，設置該節點后繼 previous 屬性，指向待刪除節點的前驅即可。定義如下：
//刪除節點function remove ( item ) { var currNode = this.find ( item ); if( !( currNode.next == null ) ){ currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; }}還有一些反向顯示鏈表 dispReverse，查找鏈表最后一個元素 findLast 等方法，相信你已經有了思路，這里我給出一個基本雙向鏈表的完成代碼，供大家參考。
//節點 function Node(element) { this.element = element; //當前節點的元素 this.next = null; //下一個節點鏈接 this.previous = null; //上一個節點鏈接}//鏈表類function LList () { this.head = new Node( 'head' ); this.find = find; this.findLast = findLast; this.insert = insert; this.remove = remove; this.display = display; this.dispReverse = dispReverse;}//查找元素function find ( item ) { var currNode = this.head; while ( currNode.element != item ){ currNode = currNode.next; } return currNode;}//查找鏈表中的最后一個元素function findLast () { var currNode = this.head; while ( !( currNode.next == null )){ currNode = currNode.next; } return currNode;}//插入節點function insert ( newElement , item ) { var newNode = new Node( newElement ); var currNode = this.find( item ); newNode.next = currNode.next; newNode.previous = currNode; currNode.next = newNode;}//顯示鏈表元素function display () { var currNode = this.head; while ( !(currNode.next == null) ){ console.debug( currNode.next.element ); currNode = currNode.next; }}//反向顯示鏈表元素function dispReverse () { var currNode = this.findLast(); while ( !( currNode.previous == null )){ console.log( currNode.element ); currNode = currNode.previous; }}//刪除節點function remove ( item ) { var currNode = this.find ( item ); if( !( currNode.next == null ) ){ currNode.previous.next = currNode.next; currNode.next.previous = currNode.previous; currNode.next = null; currNode.previous = null; }}var fruits = new LList();fruits.insert('Apple' , 'head');fruits.insert('Banana' , 'Apple');fruits.insert('Pear' , 'Banana');fruits.insert('Grape' , 'Pear');console.log( fruits.display() ); // Apple // Banana // Pear // Grape console.log( fruits.dispReverse() ); // Grape // Pear // Banana // Apple循環鏈表和單鏈表相似，節點類型都是一樣，唯一的區別是，在創建循環鏈表的時候，讓其頭節點的 next 屬性執行它本身，即
head.next = head;
這種行為會導致鏈表中每個節點的 next 屬性都指向鏈表的頭節點，換句話說，也就是鏈表的尾節點指向了頭節點，形成了一個循環鏈表，如下圖所示：
循環鏈表
原理相信你已經懂了，循環鏈表這里就不貼代碼了，相信你自己能獨立完成！
至此，我們對鏈表有了比較深刻的認識，如果想讓我們的鏈表更加健全，我們還可發揮自己的思維，給鏈表添加比如向前移動幾個節點，向后移動幾個節點，顯示當前節點等方法，大家一起加油！
希望本文所述對大家JavaScript程序設計有所幫助。
新聞熱點
疑難解答
