JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(三)：鏈表

更新時(shí)間：2015年06月19日 09:33:40 投稿：junjie

這篇文章主要介紹了JavaScript中數(shù)據(jù)結(jié)構(gòu)與算法(三)：鏈表,本文分別講解了單鏈表與雙鏈表以及增加節(jié)和刪除節(jié)的代碼實(shí)例,需要的朋友可以參考下

我們可以看到在javascript概念中的隊(duì)列與棧都是一種特殊的線性表的結(jié)構(gòu)，也是一種比較簡(jiǎn)單的基于數(shù)組的順序存儲(chǔ)結(jié)構(gòu)。由于javascript的解釋器針對(duì)數(shù)組都做了直接的優(yōu)化，不會(huì)存在在很多編程語言中數(shù)組固定長(zhǎng)度的問題(當(dāng)數(shù)組填滿后再添加就比較困難了，包括添加刪除，都是需要把數(shù)組中所有的元素全部都變換位置的，javascript的的數(shù)組確實(shí)直接給優(yōu)化好了，如push,pop,shift,unshift,split方法等等…)

線性表的順序存儲(chǔ)結(jié)構(gòu)，最大的缺點(diǎn)就是改變其中一個(gè)元素的排列時(shí)都會(huì)引起整個(gè)合集的變化，其原因就是在內(nèi)存中的存儲(chǔ)本來就是連貫沒有間隙的，刪除一個(gè)自然就要補(bǔ)上。針對(duì)這種結(jié)構(gòu)的優(yōu)化之后就出現(xiàn)了鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，換個(gè)思路，我們完全不關(guān)心數(shù)據(jù)的排列，我們只需要在每一個(gè)元素的內(nèi)部把下一個(gè)的數(shù)據(jù)的位置給記錄就可以了，所以用鏈接方式存儲(chǔ)的線性表簡(jiǎn)稱為鏈表，在鏈?zhǔn)浇Y(jié)構(gòu)中，數(shù)據(jù)=（信息+地址）

鏈?zhǔn)浇Y(jié)構(gòu)中，我們把地址也可以稱為“鏈”，一個(gè)數(shù)據(jù)單元就是一個(gè)節(jié)點(diǎn)，那么可以說鏈表就是一組節(jié)點(diǎn)組成的合集。每一個(gè)節(jié)點(diǎn)都有一個(gè)數(shù)據(jù)塊引用指向它的下一個(gè)節(jié)點(diǎn)

數(shù)組元素是靠位置關(guān)系做邏輯引用，鏈表則是靠每一個(gè)數(shù)據(jù)元保存引用指針關(guān)系進(jìn)行引用

這種結(jié)構(gòu)上的優(yōu)勢(shì)就非常明顯的，插入一個(gè)數(shù)據(jù)完全不需要關(guān)心其排列情況，只要把“鏈”的指向銜接上

這樣做鏈表的思路就不會(huì)局限在數(shù)組上了，我們可以用對(duì)象了，只要對(duì)象之間存在引用關(guān)系即可

鏈表一般有，單鏈表、靜態(tài)鏈表、循環(huán)鏈表、雙向鏈表

單鏈表：就是很單一的向下傳遞，每一個(gè)節(jié)點(diǎn)只記錄下一個(gè)節(jié)點(diǎn)的信息，就跟無間道中的梁朝偉一樣做臥底都是通過中間人上線與下線聯(lián)系，一旦中間人斷了，那么就無法證明自己的身份了，所以片尾有一句話："我是好人，誰知道呢？”

靜態(tài)鏈表：就是用數(shù)組描述的鏈表。也就是數(shù)組中每一個(gè)下表都是一個(gè)“節(jié)”包含了數(shù)據(jù)與指向

循環(huán)鏈表：由于單鏈表的只會(huì)往后方傳遞，所以到達(dá)尾部的時(shí)候，要回溯到首部會(huì)非常麻煩，所以把尾部節(jié)的鏈與頭連接起來形成循環(huán)

雙向鏈表：針對(duì)單鏈表的優(yōu)化，讓每一個(gè)節(jié)都能知道前后是誰，所以除了后指針域還會(huì)存在一個(gè)前指針域，這樣提高了查找的效率，不過帶來了一些在設(shè)計(jì)上的復(fù)雜度，總體來說就是空間換時(shí)間了

綜合下，其實(shí)鏈表就是線性表中針對(duì)順序存儲(chǔ)結(jié)構(gòu)的一種優(yōu)化手段，但是在javascript語言中由于數(shù)組的特殊性（自動(dòng)更新引用位置），所以我們可以采用對(duì)象的方式做鏈表存儲(chǔ)的結(jié)構(gòu)

單鏈表

我們實(shí)現(xiàn)一個(gè)最簡(jiǎn)單的鏈表關(guān)系

function createLinkList() {
  var _this = {},
    prev = null;
  return {
    add: function(val) {
      //保存當(dāng)前的引用
      prev = {
        data: val,
        next: prev || null
      }
    }
  }
}
var linksList = createLinkList(); 
linksList.add("arron1"); 
linksList.add("arron2"); 
linksList.add("arron3");
//node節(jié)的next鏈就是 -arron3-arron2-arron1

通過node對(duì)象的next去直引用下一個(gè)node對(duì)象，初步是實(shí)現(xiàn)了通過鏈表的引用，這種鏈?zhǔn)剿悸穓Query的異步deferred中的then方法，還有日本的cho45的jsderferre中都有用到。這個(gè)實(shí)現(xiàn)上還有一個(gè)最關(guān)鍵的問題，我們?cè)趺磩?dòng)態(tài)插入數(shù)據(jù)到執(zhí)行的節(jié)之后？

所以我們必須要設(shè)計(jì)一個(gè)遍歷的方法，用來搜索這個(gè)node鏈上的數(shù)據(jù)，然后找出這個(gè)對(duì)應(yīng)的數(shù)據(jù)把新的節(jié)插入到當(dāng)前的鏈中，并改寫位置記錄

//在鏈表中找到對(duì)應(yīng)的節(jié)
var findNode = function createFindNode(currNode) {
  return function(key){
    //循環(huán)找到執(zhí)行的節(jié)，如果沒有返回本身
    while (currNode.data != key) {
      currNode = currNode.next;
    }
    return currNode;        
  }
}(headNode);

這就是一個(gè)查找當(dāng)前節(jié)的一個(gè)方法，通過傳遞原始的頭部headNode節(jié)去一直往下查找next，直到找到對(duì)應(yīng)的節(jié)信息

這里是用curry方法實(shí)現(xiàn)的

那么插入節(jié)的的時(shí)候，針對(duì)鏈表地址的換算關(guān)系這是這樣

a-b-c-d的鏈表中，如果要在c(c.next->d)后面插入一個(gè)f

a-b-c-f-d ,那么c,next->f , f.next-d

通過insert方法增加節(jié)

//創(chuàng)建節(jié)
function createNode(data) {
  this.data = data;
  this.next = null;
}
//初始化頭部節(jié)
//從headNode開始形成一條鏈條
//通過next銜接
var headNode = new createNode("head");

//在鏈表中找到對(duì)應(yīng)的節(jié)
var findNode = function createFindNode(currNode) {
  return function(key){
    //循環(huán)找到執(zhí)行的節(jié)，如果沒有返回本身
    while (currNode.data != key) {
      currNode = currNode.next;
    }
    return currNode;        
  }
}(headNode);

//插入一個(gè)新節(jié)
this.insert = function(data, key) {
  //創(chuàng)建一個(gè)新節(jié)
  var newNode = new createNode(data);
  //在鏈條中找到對(duì)應(yīng)的數(shù)據(jù)節(jié)
  //然后把新加入的掛進(jìn)去
  var current = findNode(key);
  //插入新的接，更改引用關(guān)系
  //1:a-b-c-d
  //2:a-b-n-c-d
  newNode.next = current.next;
  current.next = newNode;
};

首先分離出createNode節(jié)的構(gòu)建，在初始化的時(shí)候先創(chuàng)建一個(gè)頭部節(jié)對(duì)象用來做節(jié)開頭的初始化對(duì)象

在insert增加節(jié)方法中，通過對(duì)headNode鏈的一個(gè)查找，找到對(duì)應(yīng)的節(jié)，把新的節(jié)給加后之后，最后就是修改一下鏈的關(guān)系

如何從鏈表中刪除一個(gè)節(jié)點(diǎn)？

由于鏈表的特殊性，我們a->b->c->d ，如果要?jiǎng)h除c那么就必須修改b.next->c為 b.next->d，所以找到前一個(gè)節(jié)修改其鏈表next地址，這個(gè)有點(diǎn)像dom操作中removeChild找到其父節(jié)點(diǎn)調(diào)用移除子節(jié)點(diǎn)

同樣的我們也在remove方法的設(shè)計(jì)中，需要設(shè)計(jì)一個(gè)遍歷往上回溯一個(gè)父節(jié)點(diǎn)即可

//找到前一個(gè)節(jié)
var findPrevious = function(currNode) {
  return function(key){
    while (!(currNode.next == null) &&
      (currNode.next.data != key)) {
      currNode = currNode.next;
    }
    return currNode;      
  }
}(headNode);

//插入方法
this.remove = function(key) {
  var prevNode = findPrevious(key);
  if (!(prevNode.next == null)) {
    //修改鏈表關(guān)系
    prevNode.next = prevNode.next.next;
  }
};

測(cè)試代碼：

<!doctype html><button id="test1">插入多條數(shù)據(jù)</button>
<button id="test2">刪除Russellville數(shù)據(jù)</button><div id="listshow"><br /></div><script type="text/javascript">
 //////////
 //創(chuàng)建鏈表 //
 //////////
 function createLinkList() {

 //創(chuàng)建節(jié)
 function createNode(data) {
  this.data = data;
  this.next = null;
 }

 //初始化頭部節(jié)
 //從headNode開始形成一條鏈條
 //通過next銜接
 var headNode = new createNode("head");

 //在鏈表中找到對(duì)應(yīng)的節(jié)
 var findNode = function createFindNode(currNode) {
  return function(key) {
  //循環(huán)找到執(zhí)行的節(jié)，如果沒有返回本身
  while (currNode.data != key) {
   currNode = currNode.next;
  }
  return currNode;
  }
 }(headNode);

 //找到前一個(gè)節(jié)
 var findPrevious = function(currNode) {
  return function(key) {
  while (!(currNode.next == null) &&
   (currNode.next.data != key)) {
   currNode = currNode.next;
  }
  return currNode;
  }
 }(headNode);


 //插入一個(gè)新節(jié)
 this.insert = function(data, key) {
  //創(chuàng)建一個(gè)新節(jié)
  var newNode = new createNode(data);
  //在鏈條中找到對(duì)應(yīng)的數(shù)據(jù)節(jié)
  //然后把新加入的掛進(jìn)去
  var current = findNode(key);
  //插入新的接，更改引用關(guān)系
  //1:a-b-c-d
  //2:a-b-n-c-d
  newNode.next = current.next;
  current.next = newNode;
 };

 //插入方法
 this.remove = function(key) {
  var prevNode = findPrevious(key);
  if (!(prevNode.next == null)) {
  //修改鏈表關(guān)系
  prevNode.next = prevNode.next.next;
  }
 };


 this.display = function(fn) {
  var currNode = headNode;
  while (!(currNode.next == null)) {
  currNode = currNode.next;
  fn(currNode.data)
  }
 };

 }


 var cities = new createLinkList();

 function create() {
 var text = '';
 cities.display(function(data) {
  text += '-' + data;
 });
 var div = document.createElement('div')
 div.innerHTML = text;
 document.getElementById("listshow").appendChild(div)
 }

 document.getElementById("test1").onclick = function() {
 cities.insert("Conway", "head");
 cities.insert("Russellville", "Conway");
 cities.insert("Carlisle", "Russellville");
 cities.insert("Alma", "Carlisle");
 create();
 }

 document.getElementById("test2").onclick = function() {
 cities.remove("Russellville");
 create()
 }

</script>

雙鏈表

原理跟單鏈表是一樣的，無非就是給每一個(gè)節(jié)增加一個(gè)前鏈表的指針

增加節(jié)

//插入一個(gè)新節(jié)
this.insert = function(data, key) {
  //創(chuàng)建一個(gè)新節(jié)
  var newNode = new createNode(data);
  //在鏈條中找到對(duì)應(yīng)的數(shù)據(jù)節(jié)
  //然后把新加入的掛進(jìn)去
  var current = findNode(headNode,key);
  //插入新的接，更改引用關(guān)系
  newNode.next   = current.next;
  newNode.previous = current
  current.next   = newNode;
};

刪除節(jié)

this.remove = function(key) {
  var currNode = findNode(headNode,key);
  if (!(currNode.next == null)) {
    currNode.previous.next = currNode.next;
    currNode.next.previous = currNode.previous;
    currNode.next     = null;
    currNode.previous   = null;
  }
};

在刪除操作中有一個(gè)明顯的優(yōu)化：不需要找到父節(jié)了，因?yàn)殡p鏈表的雙向引用所以效率比單鏈要高

測(cè)試代碼：

<!doctype html><button id="test1">插入多條數(shù)據(jù)</button>
<button id="test2">刪除Russellville數(shù)據(jù)</button><div id="listshow"><br /></div><script type="text/javascript">

 //////////
 //創(chuàng)建鏈表 //
 //////////
 function createLinkList() {

 //創(chuàng)建節(jié)
 function createNode(data) {
  this.data = data;
  this.next = null;
  this.previous = null
 }

   //初始化頭部節(jié)
 //從headNode開始形成一條鏈條
 //通過next銜接
 var headNode = new createNode("head");

 //在鏈表中找到對(duì)應(yīng)的數(shù)據(jù)
 var findNode = function(currNode, key) {
  //循環(huán)找到執(zhí)行的節(jié)，如果沒有返回本身
  while (currNode.data != key) {
  currNode = currNode.next;
  }
  return currNode;
 }

 //插入一個(gè)新節(jié)
 this.insert = function(data, key) {
  //創(chuàng)建一個(gè)新節(jié)
  var newNode = new createNode(data);
  //在鏈條中找到對(duì)應(yīng)的數(shù)據(jù)節(jié)
  //然后把新加入的掛進(jìn)去
  var current = findNode(headNode,key);
  //插入新的接，更改引用關(guān)系
  newNode.next   = current.next;
  newNode.previous = current
  current.next   = newNode;
 };

 this.remove = function(key) {
  var currNode = findNode(headNode,key);
  if (!(currNode.next == null)) {
  currNode.previous.next = currNode.next;
  currNode.next.previous = currNode.previous;
  currNode.next     = null;
  currNode.previous   = null;
  }
 };

 this.display = function(fn) {
  var currNode = headNode;
  while (!(currNode.next == null)) {
  currNode = currNode.next;
  fn(currNode.data)
  }
 };

 }


 var cities = new createLinkList();

 function create() {
 var text = '';
 cities.display(function(data) {
  text += '-' + data;
 });
 var div = document.createElement('div')
 div.innerHTML = text;
 document.getElementById("listshow").appendChild(div)
 }

 document.getElementById("test1").onclick = function() {
 cities.insert("Conway", "head");
 cities.insert("Russellville", "Conway");
 cities.insert("Carlisle", "Russellville");
 cities.insert("Alma", "Carlisle");
 create();
 }

 document.getElementById("test2").onclick = function() {
 cities.remove("Russellville");
 create()
 }


</script>

git代碼下載：https://github.com/JsAaron/data_structure.git

您可能感興趣的文章: