JavaScript數據結構之鏈表的實現

2019-11-19 17:06:59

字體：大中小

來源：轉載

供稿：網友

前面樓主分別討論了數據結構棧與隊列的實現，當時所用的數據結構都是用的數組來進行實現，但是數組有的時候并不是最佳的數據結構，比如在數組中新增刪除元素的時候需要將其他元素進行移動，而在javascript中使用spit()方法不需要訪問其他元素。如果你在使用數組的時候發現很慢，就可以考慮使用鏈表。

鏈表的概念

鏈表是一種常見的數據結構。它是動態地進行存儲分配的一種結構。鏈表有一個“頭指針”變量，以head表示，它存放一個地址，指向一個元素。每個結點都使用一個對象的引用指標它的后繼，指向另一個結點的引用叫做鏈。

數組元素依靠下標（位置）來進行引用，而鏈表元素則是靠相互之間的關系來進行引用。因此鏈表的插入效率很高，下圖演示了鏈表結點d的插入過程：　

刪除過程：

基于對象的鏈表

我們定義2個類，Node類與LinkedList類，Node為結點數據，LinkedList保存操作鏈表的方法。

首先看Node類：　　

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

element用來保存結點上的數據，next用來保存指向一下結點的的鏈接。　　

LinkedList類:

function LinkedList(){     this.head = new Node('head');     this.find = find;     this.insert = insert;     this.remove = remove;     this.show = show;}

find()方法，從頭結點開始，沿著鏈表結點一直查找，直到找到與item內容相等的element則返回該結點，沒找到則返回空。

function find(item){     var currentNode = this.head;//從頭結點開始     while(currentNode.element!=item){         currentNode = currentNode.next;     }     return currentNode;//找到返回結點數據，沒找到返回null}

Insert方法。通過前面元素插入的演示可以看出，實現插入簡單四步：

1、創建結點

2、找到目標結點

3、修改目標結點的next指向鏈接

4、將目標結點的next值賦值給要插入的結點的next

function insert(newElement,item){     var newNode = new Node(newElement);     var currentNode = this.find(item);     newNode.next = currentNode.next;     currentNode.next = newNode; }

Remove()方法。刪除某一節點需要先找到被刪除結點的前結點，為此我們定義方法frontNode()：

function frontNode(item){     var currentNode = this.head;     while(currentNode.next.element!=item&¤tNode.next!=null){         currentNode = currentNode.next;     }        return currentNode;}

簡答三步：

1、創建結點

2、找到目標結點的前結點

3、修改前結點的next指向被刪除結點的n后一個結點

function remove(item){     var frontNode = this.frontNode(item);     //console.log(frontNode.element);     frontNode.next = frontNode.next.next; }

Show()方法：

function show(){     var currentNode = this.head,result;     while(currentNode.next!=null){         result += currentNode.next.element;//為了不顯示head結點         currentNode = currentNode.next;     }}

測試程序：

var list = new LinkedList();list.insert("a","head");list.insert("b","a");list.insert("c","b");console.log(list.show());list.remove("b");console.log(list.show());

輸出：

雙向鏈表

從鏈表的頭節點遍歷到尾節點很簡單，但有的時候，我們需要從后向前遍。此時我們可以通過給 Node 對象增加一個屬性，該屬性存儲指向前驅節點的鏈接。樓主用下圖來雙向鏈表的工作原理。

首先我們先給Node類增加front屬性：　　

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

當然，對應的insert()方法和remove()方法我們也需要做相應的修改：　

function insert(newElement,item){  var newNode = new Node(newElement);  var currentNode = this.find(item);  newNode.next = currentNode.next;  newNode.front = currentNode;//增加front指向前驅結點  currentNode.next = newNode;}function remove(item){    var currentNode = this.find(item);//找到需要刪除的節點  if (currentNode.next != null) {    currentNode.front.next = currentNode.next;//讓前驅節點指向需要刪除的節點的下一個節點    currentNode.next.front = currentNode.front;//讓后繼節點指向需要刪除的節點的上一個節點    currentNode.next = null;//并設置前驅與后繼的指向為空    currentNode.front = null;      }  }

反序顯示鏈表：

需要給雙向鏈表增加一個方法，用來查找最后的節點。 findLast() 方法找出了鏈表中的最后一個節點，可以免除從前往后遍歷鏈。

function findLast() {//查找鏈表的最后一個節點  var currentNode = this.head;  while (currentNode.next != null) {    currentNode = currentNode.next;  }  return currentNode;}

實現反序輸出：

function showReverse() {  var currentNode = this.head, result = "";  currentNode = this.findLast();   while(currentNode.front!=null){    result += currentNode.element + " ";    currentNode = currentNode.front;  }  return result;}

測試程序：

var list = new LinkedList();list.insert("a","head");list.insert("b","a");list.insert("c","b");console.log(list);list.remove("b");console.log(list.show());console.log(list.showReverse());

輸出：

循環鏈表

循環鏈表是另一種形式的鏈式存貯結構。它的特點是表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環。循環鏈表和單向鏈表相似，節點類型都是一樣的。唯一的區別是，在創建循環鏈表時，讓其頭節點的 next 屬性指向它本身，即：

head.next = head

這種行為會傳導至鏈表中的每個節點，使得每個節點的 next 屬性都指向鏈表的頭節點。樓主用下圖來表示循環鏈表：

修改構造方法：

function LinkedList(){  this.head = new Node('head');//初始化  this.head.next = this.head;//直接將頭節點的next指向頭節點形成循環鏈表  this.find = find;  this.frontNode = frontNode;  this.insert = insert;  this.remove = remove;  this.show = show; }

這時需要注意鏈表的輸出方法show()與find()方法，原來的方式在循環鏈表里會陷入死循環，while循環的循環條件需要修改為當循環到頭節點時退出循環。

function find(item){  var currentNode = this.head;//從頭結點開始  while(currentNode.element!=item&¤tNode.next.element!='head'){    currentNode = currentNode.next;  }  return currentNode;//找到返回結點數據，沒找到返回null}function show(){  var currentNode = this.head,result = "";  while (currentNode.next != null && currentNode.next.element != "head") {       result += currentNode.next.element + " ";    currentNode = currentNode.next;  }  return result;}

測試程序：

var list = new LinkedList();list.insert("a","head");list.insert("b","a");list.insert("c","b");console.log(list.show());list.remove("b");console.log(list.show());

測試結果：