鏈表(Linked-list)
前面我們討論了如何使用棧狼钮、隊列進(jìn)行存數(shù)數(shù)據(jù)碳柱，他們其實都是列表的一種捡絮，底層存儲的數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)都是數(shù)組熬芜。
但是數(shù)組不總是最佳的數(shù)據(jù)結(jié)構(gòu)，因為福稳，在很多編程語言中涎拉，數(shù)組的長度都是固定的，如果數(shù)組已被數(shù)據(jù)填滿的圆，再要加入新的元素是非常困難的鼓拧。而且，對于數(shù)組的刪除和添加操作越妈，通常需要將數(shù)組中的其他元素向前或者向后平移季俩，這些操作也是十分繁瑣的。
然而梅掠，JS中數(shù)組卻不存在上述問題酌住，主要是因為他們被實現(xiàn)了成了對象店归，但是與其他語言相比（比如C或Java），那么它的效率會低很多酪我。
這時候消痛，我們可以考慮使用鏈表(Linked-list) 來替代它，除了對數(shù)據(jù)的隨機(jī)訪問都哭，鏈表幾乎可以在任何可以使用一維數(shù)組的情況中秩伞。如果你正巧在使用C或者Java等高級語言，你會發(fā)現(xiàn)鏈表的表現(xiàn)要優(yōu)于數(shù)組很多欺矫。
鏈表其實有許多的種類：單向鏈表纱新、雙向鏈表、單向循環(huán)鏈表和雙向循環(huán)鏈表穆趴，接下來怒炸，我們基于對象來實現(xiàn)一個單向鏈表，因為它的使用最為廣泛毡代。
鏈表的定義
首先阅羹，要實現(xiàn)鏈表，我們先搞懂一些鏈表的基本東西教寂，因為這很重要捏鱼！
鏈表是一組節(jié)點組成的集合，每個節(jié)點都使用一個對象的引用來指向它的后一個節(jié)點酪耕。指向另一節(jié)點的引用講做鏈导梆。下面我畫了一個簡單的鏈接結(jié)構(gòu)圖，方便大家理解迂烁。
其中看尼，data中保存著數(shù)據(jù)，next保存著下一個鏈表的引用盟步。上圖中藏斩，我們說 data2 跟在 data1 后面，而不是說 data2 是鏈表中的第二個元素却盘。上圖狰域，值得注意的是，我們將鏈表的尾元素指向了 null 節(jié)點黄橘，表示鏈接結(jié)束的位置兆览。
由于鏈表的起始點的確定比較麻煩，因此很多鏈表的實現(xiàn)都會在鏈表的最前面添加一個特殊的節(jié)點塞关，稱為 頭節(jié)點抬探，表示鏈表的頭部。進(jìn)過改造帆赢，鏈表就成了如下的樣子：
向鏈表中插入一個節(jié)點的效率很高小压，需要修改它前面的節(jié)點(前驅(qū))砰左，使其指向新加入的節(jié)點，而將新節(jié)點指向原來前驅(qū)節(jié)點指向的節(jié)點即可场航。下面我將用圖片演示如何在 data2 節(jié)點 后面插入 data4 節(jié)點缠导。
同樣，從鏈表中刪除一個節(jié)點溉痢，也很簡單僻造。只需將待刪節(jié)點的前驅(qū)節(jié)點指向待刪節(jié)點的，同時將待刪節(jié)點指向null孩饼，那么節(jié)點就刪除成功了髓削。下面我們用圖片演示如何從鏈表中刪除 data4 節(jié)點。
鏈表的設(shè)計
我們設(shè)計鏈表包含兩個類镀娶，一個是 Node 類用來表示節(jié)點立膛，另一個事 LinkedList 類提供插入節(jié)點、刪除節(jié)點等一些操作梯码。
Node類
Node類包含連個屬性： element 用來保存節(jié)點上的數(shù)據(jù)宝泵，next 用來保存指向下一個節(jié)點的鏈接，具體實現(xiàn)如下：
//節(jié)點
function Node(element) {
this.element = element; //當(dāng)前節(jié)點的元素
this.next = null; //下一個節(jié)點鏈接
}
LinkedList類
LinkedList類提供了對鏈表進(jìn)行操作的方法轩娶，包括插入刪除節(jié)點儿奶，查找給定的值等。值得注意的是鳄抒，它只有一個
屬性闯捎，那就是使用一個 Node 對象來保存該鏈表的頭節(jié)點。
它的構(gòu)造函數(shù)的實現(xiàn)如下：
//鏈表類
function LList () {
this.head = new Node( 'head' ); //頭節(jié)點
this.find = find; //查找節(jié)點
this.insert = insert; //插入節(jié)點
this.remove = remove; //刪除節(jié)點
this.findPrev = findPrev; //查找前一個節(jié)點
this.display = display; //顯示鏈表
}
head節(jié)點的next屬性初始化為 null 许溅，當(dāng)有新元素插入時瓤鼻，next會指向新的元素。
接下來贤重，我們來看看具體方法的實現(xiàn)茬祷。
insert：向鏈表插入一個節(jié)點
我們先分析分析insert方法，想要插入一個節(jié)點游桩，我們必須明確要在哪個節(jié)點的前面或后面插入牲迫。我們先來看看耐朴，如何在一個已知節(jié)點的后面插入一個節(jié)點借卧。
在一個已知節(jié)點后插入新節(jié)點，我們首先得找到該節(jié)點筛峭，為此铐刘，我們需要一個 find 方法用來遍歷鏈表，查找給定的數(shù)據(jù)影晓。如果找到镰吵，該方法就返回保存該數(shù)據(jù)的節(jié)點檩禾。那么，我們先實現(xiàn) find 方法疤祭。
find：查找給定節(jié)點
//查找給定節(jié)點
function find ( item ) {
var currNode = this.head;
while ( currNode.element != item ){
currNode = currNode.next;
}
return currNode;
}
find 方法同時展示了如何在鏈表上移動盼产。首先，創(chuàng)建一個新節(jié)點勺馆，將鏈表的頭節(jié)點賦給這個新創(chuàng)建的節(jié)點戏售，然后在鏈表上循環(huán)，如果當(dāng)前節(jié)點的 element 屬性和我們要找的信息不符草穆，就將當(dāng)前節(jié)點移動到下一個節(jié)點灌灾，如果查找成功，該方法返回包含該數(shù)據(jù)的節(jié)點悲柱；否則锋喜，就會返回null。
一旦找到了節(jié)點豌鸡，我們就可以將新的節(jié)點插入到鏈表中了嘿般，將新節(jié)點的 next 屬性設(shè)置為后面節(jié)點的 next 屬性對應(yīng)的值，然后設(shè)置后面節(jié)點的 next 屬性指向新的節(jié)點涯冠，具體實現(xiàn)如下：
//插入節(jié)點
function insert ( newElement , item ) {
var newNode = new Node( newElement );
var currNode = this.find( item );
newNode.next = currNode.next;
currNode.next = newNode;
}
現(xiàn)在我們可以測試我們的鏈表了博个。等等，我們先來定義一個 display 方法顯示鏈表的元素功偿，不然我們怎么知道對不對呢盆佣？
display：顯示鏈表
//顯示鏈表元素
function display () {
var currNode = this.head;
while ( !(currNode.next == null) ){
console.log( currNode.next.element );
currNode = currNode.next;
}
}
實現(xiàn)原理同上，將頭節(jié)點賦給一個新的變量械荷，然后循環(huán)鏈表瀑构，直到當(dāng)前節(jié)點的 next 屬性為 null 時停止循環(huán)，我們循環(huán)過程中將每個節(jié)點的數(shù)據(jù)打印出來就好了介袜。
var fruits = new LList();
fruits.insert('Apple' , 'head');
fruits.insert('Banana' , 'Apple');
fruits.insert('Pear' , 'Banana');
console.log(fruits.display()); // Apple
// Banana
// Pear
remove：從鏈表中刪除一個節(jié)點
從鏈表中刪除節(jié)點時蛮粮，我們先要找個待刪除節(jié)點的前一個節(jié)點，找到后颤诀，我們修改它的 next 屬性字旭，使其不在指向待刪除的節(jié)點，而是待刪除節(jié)點的下一個節(jié)點崖叫。那么遗淳，我們就得需要定義一個 findPrevious 方法遍歷鏈表，檢查每一個節(jié)點的下一個節(jié)點是否存儲待刪除的數(shù)據(jù)心傀。如果找到屈暗，返回該節(jié)點，這樣就可以修改它的 next 屬性了。 findPrevious 的實現(xiàn)如下：
//查找?guī)h除節(jié)點的前一個節(jié)點
function findPrev( item ) {
var currNode = this.head;
while ( !( currNode.next == null) && ( currNode.next.element != item )){
currNode = currNode.next;
}
return currNode;
}
這樣养叛，remove 方法的實現(xiàn)也就迎刃而解了
//刪除節(jié)點
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
// Grape
Great弃甥！成功了爽室，現(xiàn)在你已經(jīng)可以實現(xiàn)一個基本的單向鏈表了。
雙向鏈表
盡管從鏈表的頭節(jié)點遍歷鏈表很簡單淆攻，但是反過來肮之，從后向前遍歷卻不容易。我們可以通過給Node類增加一個previous屬性卜录，讓其指向前驅(qū)節(jié)點的鏈接戈擒，這樣就形成了雙向鏈表，如下圖：
此時艰毒，向鏈表插入一個節(jié)點就要更改節(jié)點的前驅(qū)和后繼了筐高，但是刪除節(jié)點的效率提高了，不再需要尋找待刪除節(jié)點的前驅(qū)節(jié)點了丑瞧。
雙向鏈表的實現(xiàn)
要實現(xiàn)雙向鏈表柑土，首先需要給 Node 類增加一個 previous 屬性：
//節(jié)點類
function Node(element) {
this.element = element; //當(dāng)前節(jié)點的元素
this.next = null; //下一個節(jié)點鏈接
this.previous = null; //上一個節(jié)點鏈接
}
雙向鏈表的 insert 方法與單鏈表相似，但需要設(shè)置新節(jié)點的 previous 屬性绊汹，使其指向該節(jié)點的前驅(qū)稽屏，定義如下：
//插入節(jié)點
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 方法比單鏈表效率高，不需要查找前驅(qū)節(jié)點西乖，只要找出待刪除節(jié)點狐榔，然后將該節(jié)點的前驅(qū) next 屬性指向待刪除節(jié)點的后繼，設(shè)置該節(jié)點后繼 previous 屬性获雕，指向待刪除節(jié)點的前驅(qū)即可薄腻。定義如下：
//刪除節(jié)點
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 等方法届案，相信你已經(jīng)有了思路庵楷，這里我給出一個基本雙向鏈表的完成代碼，供大家參考楣颠。
//節(jié)點
function Node(element) {
this.element = element; //當(dāng)前節(jié)點的元素
this.next = null; //下一個節(jié)點鏈接
this.previous = null; //上一個節(jié)點鏈接
}
//鏈表類
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;
}
//插入節(jié)點
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;
}
}
//刪除節(jié)點
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
循環(huán)鏈表
循環(huán)鏈表和單鏈表相似尽纽，節(jié)點類型都是一樣，唯一的區(qū)別是童漩，在創(chuàng)建循環(huán)鏈表的時候弄贿，讓其頭節(jié)點的 next 屬性執(zhí)行它本身，即
head.next = head;
這種行為會導(dǎo)致鏈表中每個節(jié)點的 next 屬性都指向鏈表的頭節(jié)點睁冬，換句話說挎春，也就是鏈表的尾節(jié)點指向了頭節(jié)點看疙，形成了一個循環(huán)鏈表豆拨，如下圖所示：
原理相信你已經(jīng)懂了直奋，循環(huán)鏈表這里就不貼代碼了，相信你自己能獨立完成施禾！
至此脚线，我們對鏈表有了比較深刻的認(rèn)識，如果想讓我們的鏈表更加健全弥搞，我們還可發(fā)揮自己的思維邮绿，給鏈表添加比如向前移動幾個節(jié)點，向后移動幾個節(jié)點攀例，顯示當(dāng)前節(jié)點等方法船逮，大家一起加油！
