JavaScript中資料結構與演算法(三)：鍊錶_javascript技巧-js教程-PHP中文網

我們可以看到在javascript概念中的佇列與堆疊都是一種特殊的線性表的結構，也是一種比較簡單的基於陣列的順序儲存結構。由於javascript的解釋器針對數組都做了直接的優化，不會存在在很多程式語言中數組固定長度的問題(當數組填滿後再添加就比較困難了，包括添加刪除，都是需要把數組中所有的元素全部都變換位置的，javascript的的陣列確實直接給優化好了，如push,pop,shift,unshift,split方法等等…)

線性表的順序儲存結構，最大的缺點就是改變其中一個元素的排列時都會引起整個合集的變化，其原因就是在內存中的存儲本來就是連貫沒有間隙的，刪除一個自然就要補上。針對這種結構的最佳化之後就出現了鍊式儲存結構，換個思路，我們完全不關心資料的排列，我們只需要在每一個元素的內部把下一個的資料的位置給記錄就可以了，所以用連結方式儲存的線性表簡稱為鍊錶，在鍊式結構中，資料=（資訊位址）

鍊式結構中，我們把位址也可以稱為“鏈”，一個資料單元就是一個節點，那麼可以說鍊錶就是一組節點組成的集合。每一個節點都有一個資料塊引用指向它的下一個節點

陣列元素是靠位置關係做邏輯引用，鍊錶則是靠每一個資料元保存引用指標關係來引用

這種結構上的優勢就非常明顯的，插入一個資料完全不需要關心其排列情況，只要把「鏈」的指向銜接上

這樣做鍊錶的思路就不會局限在數組上了，我們可以用對象了，只要對象之間存在引用關係即可

鍊錶一般有，單鍊錶、靜態鍊錶、循環鍊錶、雙向鍊錶

單鍊錶：就是很單一的向下傳遞，每一個節點只記錄下一個節點的信息，就跟無間道中的梁朝偉一樣做臥底都是透過中間人上線與下線聯繫，一旦中間人斷了，那麼就無法證明自己的身分了，所以片尾有一句話：「我是好人，誰知道呢？」

靜態鍊錶：就是用陣列來描述的鍊錶。也就是數組中每一個下表都是一個「節」包含了資料與指向

循環鍊錶：由於單鍊錶的只會往後方傳遞，所以到達尾部的時候，要回溯到首部會非常麻煩，所以把尾部節的鏈與頭連接起來形成循環

雙向鍊錶：針對單鍊錶的最佳化，讓每一個節都能知道前後是誰，所以除了後指針域還會存在一個前指針域，這樣提高了查找的效率，不過帶來了一些在設計上的複雜度，整體來說就是空間換時間了

綜合下，其實鍊錶就是線性表中針對順序儲存結構的一種最佳化手段，但是在javascript語言中由於數組的特殊性（自動更新引用位置），所以我們可以採用對象的方式做鍊錶存儲的結構

單鍊錶

我們實作一個最簡單的鍊錶關係

function createLinkList() {
  var _this = {},
    prev = null;
  return {
    add: function(val) {
      //保存当前的引用
      prev = {
        data: val,
        next: prev || null
      }
    }
  }
}
var linksList = createLinkList(); 
linksList.add("arron1"); 
linksList.add("arron2"); 
linksList.add("arron3");
//node节的next链就是 -arron3-arron2-arron1

登入後複製

透過node物件的next去直引用下一個node對象，初步是實現了透過鍊錶的引用，這種鍊式思路jQuery的異步deferred中的then方法，還有日本的cho45的jsderferre中都有用到。這個實作上還有一個最關鍵的問題，我們怎麼動態插入資料到執行的節之後？

所以我們必須要設計一個遍歷的方法，用來搜尋這個node鏈上的數據，然後找出這個對應的數據把新的節插入到當前的鏈中，並改寫位置記錄

//在链表中找到对应的节
var findNode = function createFindNode(currNode) {
  return function(key){
    //循环找到执行的节，如果没有返回本身
    while (currNode.data != key) {
      currNode = currNode.next;
    }
    return currNode;        
  }
}(headNode);

登入後複製

這是一個查找當前節的一個方法，透過傳遞原始的頭部headNode節去一直往下查找next，直到找到對應的節資訊

這裡是用curry方法實作的

那麼插入節的時候，針對鍊錶位址的換算關係這是這樣

a-b-c-d的鍊錶中，如果要在c(c.next->d)後面插入一個f

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

透過insert方法增加節

//创建节
function createNode(data) {
  this.data = data;
  this.next = null;
}
//初始化头部节
//从headNode开始形成一条链条
//通过next衔接
var headNode = new createNode("head");

//在链表中找到对应的节
var findNode = function createFindNode(currNode) {
  return function(key){
    //循环找到执行的节，如果没有返回本身
    while (currNode.data != key) {
      currNode = currNode.next;
    }
    return currNode;        
  }
}(headNode);

//插入一个新节
this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(key);
  //插入新的接，更改引用关系
  //1:a-b-c-d
  //2:a-b-n-c-d
  newNode.next = current.next;
  current.next = newNode;
};

登入後複製

首先分离出createNode节的构建，在初始化的时候先创建一个头部节对象用来做节开头的初始化对象

在insert增加节方法中，通过对headNode链的一个查找，找到对应的节，把新的节给加后之后，最后就是修改一下链的关系

如何从链表中删除一个节点？

由于链表的特殊性，我们a->b->c->d ，如果要删除c那么就必须修改b.next->c为 b.next->d，所以找到前一个节修改其链表next地址，这个有点像dom操作中removeChild找到其父节点调用移除子节点

同样的我们也在remove方法的设计中，需要设计一个遍历往上回溯一个父节点即可

//找到前一个节
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)) {
    //修改链表关系
    prevNode.next = prevNode.next.next;
  }
};

登入後複製

测试代码：

<!doctype html><button id="test1">插入多条数据</button>
<button id="test2">删除Russellville数据</button><div id="listshow"><br /></div><script type="text/javascript">
 //////////
 //创建链表 //
 //////////
 function createLinkList() {

 //创建节
 function createNode(data) {
  this.data = data;
  this.next = null;
 }

 //初始化头部节
 //从headNode开始形成一条链条
 //通过next衔接
 var headNode = new createNode("head");

 //在链表中找到对应的节
 var findNode = function createFindNode(currNode) {
  return function(key) {
  //循环找到执行的节，如果没有返回本身
  while (currNode.data != key) {
   currNode = currNode.next;
  }
  return currNode;
  }
 }(headNode);

 //找到前一个节
 var findPrevious = function(currNode) {
  return function(key) {
  while (!(currNode.next == null) &&
   (currNode.next.data != key)) {
   currNode = currNode.next;
  }
  return currNode;
  }
 }(headNode);


 //插入一个新节
 this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(key);
  //插入新的接，更改引用关系
  //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)) {
  //修改链表关系
  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>

登入後複製

双链表

原理跟单链表是一样的，无非就是给每一个节增加一个前链表的指针

增加节

//插入一个新节
this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(headNode,key);
  //插入新的接，更改引用关系
  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;
  }
};

登入後複製

在删除操作中有一个明显的优化：不需要找到父节了，因为双链表的双向引用所以效率比单链要高

测试代码：

<!doctype html><button id="test1">插入多条数据</button>
<button id="test2">删除Russellville数据</button><div id="listshow"><br /></div><script type="text/javascript">

 //////////
 //创建链表 //
 //////////
 function createLinkList() {

 //创建节
 function createNode(data) {
  this.data = data;
  this.next = null;
  this.previous = null
 }

   //初始化头部节
 //从headNode开始形成一条链条
 //通过next衔接
 var headNode = new createNode("head");

 //在链表中找到对应的数据
 var findNode = function(currNode, key) {
  //循环找到执行的节，如果没有返回本身
  while (currNode.data != key) {
  currNode = currNode.next;
  }
  return currNode;
 }

 //插入一个新节
 this.insert = function(data, key) {
  //创建一个新节
  var newNode = new createNode(data);
  //在链条中找到对应的数据节
  //然后把新加入的挂进去
  var current = findNode(headNode,key);
  //插入新的接，更改引用关系
  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