搜尋
首頁web前端js教程JavaScript資料結構之鍊錶的實作方法介紹(圖文)

鍊錶是一種常見的資料結構。它是動態地進行儲存分配的一種結構。本文主要介紹JavaScript資料結構中鍊錶的實現,具有很好的參考價值。下面跟著小編一起來看下吧

前面樓主分別討論了資料結構棧與佇列的實現,當時所用的資料結構都是用的陣列來進行實現,但是陣列有的時候並不是最佳的資料結構,例如在陣列中新增刪除元素的時候需要將其他元素進行移動,而在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&&currentNode.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&&currentNode.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());

测试结果:

以上是JavaScript資料結構之鍊錶的實作方法介紹(圖文)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
Python vs. JavaScript:開發環境和工具Python vs. JavaScript:開發環境和工具Apr 26, 2025 am 12:09 AM

Python和JavaScript在開發環境上的選擇都很重要。 1)Python的開發環境包括PyCharm、JupyterNotebook和Anaconda,適合數據科學和快速原型開發。 2)JavaScript的開發環境包括Node.js、VSCode和Webpack,適用於前端和後端開發。根據項目需求選擇合適的工具可以提高開發效率和項目成功率。

JavaScript是用C編寫的嗎?檢查證據JavaScript是用C編寫的嗎?檢查證據Apr 25, 2025 am 12:15 AM

是的,JavaScript的引擎核心是用C語言編寫的。 1)C語言提供了高效性能和底層控制,適合JavaScript引擎的開發。 2)以V8引擎為例,其核心用C 編寫,結合了C的效率和麵向對象特性。 3)JavaScript引擎的工作原理包括解析、編譯和執行,C語言在這些過程中發揮關鍵作用。

JavaScript的角色:使網絡交互和動態JavaScript的角色:使網絡交互和動態Apr 24, 2025 am 12:12 AM

JavaScript是現代網站的核心,因為它增強了網頁的交互性和動態性。 1)它允許在不刷新頁面的情況下改變內容,2)通過DOMAPI操作網頁,3)支持複雜的交互效果如動畫和拖放,4)優化性能和最佳實踐提高用戶體驗。

C和JavaScript:連接解釋C和JavaScript:連接解釋Apr 23, 2025 am 12:07 AM

C 和JavaScript通過WebAssembly實現互操作性。 1)C 代碼編譯成WebAssembly模塊,引入到JavaScript環境中,增強計算能力。 2)在遊戲開發中,C 處理物理引擎和圖形渲染,JavaScript負責遊戲邏輯和用戶界面。

從網站到應用程序:JavaScript的不同應用從網站到應用程序:JavaScript的不同應用Apr 22, 2025 am 12:02 AM

JavaScript在網站、移動應用、桌面應用和服務器端編程中均有廣泛應用。 1)在網站開發中,JavaScript與HTML、CSS一起操作DOM,實現動態效果,並支持如jQuery、React等框架。 2)通過ReactNative和Ionic,JavaScript用於開發跨平台移動應用。 3)Electron框架使JavaScript能構建桌面應用。 4)Node.js讓JavaScript在服務器端運行,支持高並發請求。

Python vs. JavaScript:比較用例和應用程序Python vs. JavaScript:比較用例和應用程序Apr 21, 2025 am 12:01 AM

Python更適合數據科學和自動化,JavaScript更適合前端和全棧開發。 1.Python在數據科學和機器學習中表現出色,使用NumPy、Pandas等庫進行數據處理和建模。 2.Python在自動化和腳本編寫方面簡潔高效。 3.JavaScript在前端開發中不可或缺,用於構建動態網頁和單頁面應用。 4.JavaScript通過Node.js在後端開發中發揮作用,支持全棧開發。

C/C在JavaScript口譯員和編譯器中的作用C/C在JavaScript口譯員和編譯器中的作用Apr 20, 2025 am 12:01 AM

C和C 在JavaScript引擎中扮演了至关重要的角色,主要用于实现解释器和JIT编译器。1)C 用于解析JavaScript源码并生成抽象语法树。2)C 负责生成和执行字节码。3)C 实现JIT编译器,在运行时优化和编译热点代码,显著提高JavaScript的执行效率。

JavaScript在行動中:現實世界中的示例和項目JavaScript在行動中:現實世界中的示例和項目Apr 19, 2025 am 12:13 AM

JavaScript在現實世界中的應用包括前端和後端開發。 1)通過構建TODO列表應用展示前端應用,涉及DOM操作和事件處理。 2)通過Node.js和Express構建RESTfulAPI展示後端應用。

See all articles

熱AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover

AI Clothes Remover

用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool

Undress AI Tool

免費脫衣圖片

Clothoff.io

Clothoff.io

AI脫衣器

Video Face Swap

Video Face Swap

使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱工具

記事本++7.3.1

記事本++7.3.1

好用且免費的程式碼編輯器

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

將Eclipse與SAP NetWeaver應用伺服器整合。

ZendStudio 13.5.1 Mac

ZendStudio 13.5.1 Mac

強大的PHP整合開發環境

MantisBT

MantisBT

Mantis是一個易於部署的基於Web的缺陷追蹤工具,用於幫助產品缺陷追蹤。它需要PHP、MySQL和一個Web伺服器。請查看我們的演示和託管服務。

PhpStorm Mac 版本

PhpStorm Mac 版本

最新(2018.2.1 )專業的PHP整合開發工具