鍊錶是一種常見的資料結構。它是動態地進行儲存分配的一種結構。本文主要介紹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&¤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 物件增加一個屬性,該屬性儲存指向前驅節點的連結。樓主用下圖來雙向鍊錶的工作原理。
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 屬性指向它本身,即:
這種行為會傳導至鍊錶中的每個節點,使得每個節點的next 屬性都指向鍊錶的頭節點。樓主用下圖表示循環鍊錶:
修改
: 这时需要注意链表的输出方法show()与find()方法,原来的方式在循环链表里会陷入死循环,while循环的循环条件需要修改为当循环到头节点时退出循环。 测试程序: 测试结果: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;
}
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());
以上是JavaScript資料結構之鍊錶的實作方法介紹(圖文)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

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

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

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

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

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

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

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

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


熱AI工具

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

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

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

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

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

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

ZendStudio 13.5.1 Mac
強大的PHP整合開發環境

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

PhpStorm Mac 版本
最新(2018.2.1 )專業的PHP整合開發工具