JavaScript實現(xiàn)單鏈表過程解析
前言：
要存儲多個元素，數(shù)組是最常用的數(shù)據(jù)結(jié)構(gòu)，但是數(shù)組也有很多缺點：
- 數(shù)組的創(chuàng)建通常要申請一段連續(xù)的內(nèi)存空間，并且大小是固定的，所以當(dāng)當(dāng)前數(shù)組不能滿足容量需求時，需要進(jìn)行擴容，（一般是申請一個更大的數(shù)組，然后將原數(shù)組中的元素復(fù)制過去）
- 在數(shù)組元素開頭或者中間位置插入數(shù)據(jù)的成本很高，需要進(jìn)行大量元素的位移。
所以要存儲多個元素，另一個選擇就是鏈表，不同于數(shù)組的是，鏈表中的元素在內(nèi)存中不必是連續(xù)的空間。鏈表的每個元素有一個存儲元素本身的節(jié)點和指向下一個元素的引用。
相對于數(shù)組，鏈表有一些優(yōu)點：
- 內(nèi)存空間不必是連續(xù)的，可以充分利用計算機的內(nèi)存，實現(xiàn)靈活的內(nèi)存動態(tài)管理。
- 鏈表不必在創(chuàng)建時就確定大小，并且大小可以無限延伸下去。
- 鏈表在插入和刪除數(shù)據(jù)的時候，事件復(fù)雜度可以達(dá)到O（1），相對數(shù)組效率高很多。
相對于數(shù)組，鏈表有一些缺點：
- 鏈表訪問任何一個位置的元素的時候，都需要從頭開始訪問，無法通過下標(biāo)直接訪問元素。
一、什么是單鏈表
那么到底什么是單鏈表呢？
它就類似于火車，火車頭規(guī)連接一個節(jié)點，節(jié)點上有乘客，并且這個節(jié)點會連接到下一個節(jié)點，依次類推，如下所示：
我們的鏈表結(jié)構(gòu)就是：
了解了直觀上的鏈表，我們再來對單鏈表進(jìn)行代碼的封裝。
二、單鏈表的封裝
首先，我們封裝一個NodeList類，用于表示鏈表結(jié)構(gòu)，在這個類里面在封裝一個內(nèi)部類Node，用于封裝每一個節(jié)點上的信息（數(shù)據(jù)和指向下一個節(jié)點的引用），然后在NodeList類中保存兩個屬性，一個是鏈表的長度，一個是鏈表中的頭結(jié)點。
如下所示：
function LinkedList(){
this.length = 0;
this.head = null;
//內(nèi)部的類
function Node(data){
this.data = data;
this.next = null;
}
}
三、單鏈表的常用操作
然后在里面添加單鏈表常用的操作。主要有：
append（element):向列表尾部添加一個項insert(position,element):向列表的特定位置插入一個項get(position):獲取對應(yīng)位置的元素indexOf(element):返回元素在列表中的索引，如果列表中沒有該元素則返回-1update(position，ele):修改某個位置的元素removeAt(position):從列表的指定位置移除一項remove(element):從列表中移除一項isEmpty():如果鏈表中不包含任何元素，返回true,如果鏈表長度大于0返回falsesize():返回鏈表包含的元素個數(shù)，與數(shù)組的length屬性相關(guān)toString():由于列表項用到了Node類，需要重寫繼承自JavaScript對象默認(rèn)的toString方法，讓其輸出元素的值
接下來們就來一個一個實現(xiàn)。
1、append(element)方法-----向列表尾部添加一個項
因為向鏈表尾部添加數(shù)據(jù)可能有兩種情況：
- 鏈表本身為空，新添加的數(shù)據(jù)是唯一的節(jié)點
- 鏈表不為空，需要向其他節(jié)點后面追加節(jié)點
所以我們就需要進(jìn)行判斷，如果鏈表為空，直接將頭結(jié)點的指針指向新節(jié)點。
如果鏈表不為空，則新建立一個臨時節(jié)點，讓它等于頭結(jié)點，并對它進(jìn)行判斷，如果它指向的節(jié)點的指針域為空，則為尾節(jié)點，將新加的節(jié)點添加到末尾，即讓尾節(jié)點的指針指向新添加的節(jié)點。如果它指向的節(jié)點的指針域不為空，則讓這個臨時節(jié)點的指針域指向下一個節(jié)點，一直循環(huán)操作到這個節(jié)點的指針域為空（即為尾節(jié)點）。然后每添加一個節(jié)點，讓鏈表的長度+1。
LinkedList.prototype.append = function(data){
var newNode = new Node(data);
// 判斷鏈表是否為空
// 1.為空
if(this.length === 0){
this.head = newNode;
}else{
//不為空
var current = this.head;
if(current.next){
current = current.next;
}
current.next = newNode;
}
this.length += 1;
}
2、toString方法-----輸出元素的值
這個比較簡單，主要是獲取每一個元素，因為獲取鏈表的任何元素都必須從第一個節(jié)點開始，所以我們可以從頭結(jié)點開始，循環(huán)遍歷每一個節(jié)點，并且取出其中的element，拼接成字符串，并將字符串返回。
LinkedList.prototype.toString = function(){
var current = this.head;
var ListStr = '';
while(current){
ListStr += current.data + ' ';
current = current.next;
}
return ListStr;
}
驗證：創(chuàng)建幾個新的節(jié)點，并打印
var list = new LinkedList();
list.append('a');
list.append('b');
list.append('c');
list.append('d');
list.append('e');
alert(list);
打印結(jié)果為：
3、insert方法-----向列表的特定位置插入一個項
實現(xiàn)在任意位置插入數(shù)據(jù)的方法，首先判斷插入的位置是否越界，然后在不越界的情況下分兩種情況，如果插入到第一個位置，則表示新添加的節(jié)點是頭，則需要將原來的頭結(jié)點作為新節(jié)點的next,再讓head指向新節(jié)點。如果插入到其他位置，則需要通過循環(huán)先找到節(jié)點位置，并在循環(huán)的過程中保存上一個節(jié)點和下一個節(jié)點，找到正確的位置后，將新節(jié)點的Next指向下一個節(jié)點，將上一個節(jié)點的next節(jié)點指向新節(jié)點。
代碼如下：
LinkedList.prototype.insert = function(position,data){
if(position<0 || position >this.length){
return false;
}
var newNode = new Node(data);
var index = 0;
if(position == 0){
newNode.next = this.head;
this.head = newNode;
}else{
while(index++ < position){
var current = this.head;
var previous = null;
previous = current;
current = current.next;
}
newNode.next = current;
previous.next = newNode;
}
this.length += 1;
return true;
}
驗證：在第1個位置插入xl,在第2個位置插入wh
list.insert(1,'xl')
list.insert(2,'wh')
alert(list)
4、get方法-----獲取對應(yīng)位置的元素
這個方法相對簡單，先對positon做越界判斷，然后通過臨時節(jié)點遍歷鏈表直到目標(biāo)位置，獲取該位置的元素。
LinkedList.prototype.get = function(position,data){
var current = this.head;
var index = 0;
if(position < 0 || position >= this.length){
return null;
}else{
while(index<position){
current = current.next;
index++;
}
return current.data;
}
}
驗證：獲取第三個位置的元素：
alert( list.get(3));
5、indexOf()方法-----返回元素在列表中的索引
首先判斷查找的元素的位置是否存在，如果不存在，返回-1。如果存在的話分兩種情況，如果返回的元素在第一個位置，則直接返回第一個位置的索引。如果返回元素在其他位置，則需要通過循環(huán)先找到節(jié)點位置，這個過程中，索引需要跟著遍歷的次數(shù)自加，找到正確元素的位置后，打印索引即為目標(biāo)位置。
LinkedList.prototype.indexOf = function(data){
var index = 0;
var current = this.head;
while(current){
if(current.data == data){
return index;
}
else{
current = current.next;
index++;
}
}
return -1;
}
}
驗證：獲取c的索引：
alert(list.indexOf('c'));
6、update方法-----修改某個位置的元素
這個方法和get方法很像，向后遍歷，當(dāng)index的值等于position時，表示找到目標(biāo)位置，將date改為目標(biāo)值：
LinkedList.prototype.update = function(position,ele){
if(position<0 || position>=this.length){
return false;
}else{
var index = 0;
var current = this.head;
while(index++ <position){
current = current.next;
}
current.data = ele;
return true;
}
}
驗證：修該第0個位置的元素為：bear
list.update(0,'bear')
alert(list)
7、removeAt方法-----從列表的指定位置移除一項
首先判斷刪除項的位置是否越界，然后在不越界的情況下，給定兩個臨時節(jié)點previous和current，previous用來保存前一個current的值，從頭節(jié)點開始遍歷，直到索引位置等于目標(biāo)位置，讓臨時節(jié)點current遍歷到目標(biāo)位置，讓臨時節(jié)點的前一個next指向下一個next。
LinkedList.prototype.removeAt = function(position,data){
var current = this.head;
var previous = null;
var index = 0;
if(position<0 || position>=this.length){
return false;
}else{
while(index++ <position){
previous = currrent;
current = current.next;
}
previous.next = current.next;
this.length -= 1;
return true;
}
}
}
驗證：移除第三個位置的元素：
list.removeAt(3)
alert(list)
8、remove方法-----從列表中移除一項
先判斷所要刪除的元素是否在鏈表中，如果不在，返回false，否則，構(gòu)建一個臨時節(jié)點，用于遍歷鏈表，如果臨時節(jié)點的data值和要刪除的元素相等，則停止遍歷，讓臨時節(jié)點的前一個next指向下一個next。這里可以在構(gòu)建一個臨時節(jié)點用于存儲前一個current的值。
LinkedList.prototype.remove = function(ele){
var current = this.head;
var previous = null;
var index = 0;
while(current.data !== ele){
previous = current;
current = current.next;
index++;
}
previous.next = current.next;
}
驗證：刪除值為xl的元素：
list.remove('xl')
alert(list)
9、isEmpty方法-----判斷鏈表是否為空
根據(jù)length判斷，如果鏈表中不包含任何元素，返回true,如果鏈表長度大于0返回false
LinkedList.prototype.isEmpty = function(){
return this.length == 0;
}
驗證：
alert(list.isEmpty())
9、size方法-----返回鏈表包含的元素個數(shù)
直接返回元素的length就是其個數(shù)。
LinkedList.prototype.size = function(){
return this.length;
}
驗證：
alert(list.size())
到此這篇關(guān)于JavaScript實現(xiàn)單鏈表過程解析的文章就介紹到這了,更多相關(guān)JavaScript實現(xiàn)單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
一些很實用且必用的小腳本代碼...2006-08-08
動態(tài)調(diào)整textarea中字體的大小代碼
用js批量輸出select事件控制textarea中字體的大小的代碼。2009-12-12
這篇文章主要為大家詳細(xì)介紹了微信小程序?qū)崿F(xiàn)一鍵回到頂部功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-07-07
這篇文章主要介紹了javascript原型鏈繼承用法,實例分析了javascript原型鏈繼承中的技巧與相關(guān)注意事項,非常具有實用價值,需要的朋友可以參考下2015-01-01
本篇文章主要介紹了微信小程序之ES6與事項助手的功能實現(xiàn)，具有一定的參考價值，有興趣的同學(xué)可以了解一下。2016-11-11
這篇文章主要為大家介紹了axios 工具函數(shù)使用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-12-12
這篇文章主要為大家介紹了GoJs節(jié)點繪圖模板go.Node使用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-04-04
這篇文章主要為大家詳細(xì)介紹了JavaScript正則表達(dá)式驗證登錄實例，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要介紹了JavaScript中Pinia是否可以代替Vuex，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
js判斷是否為數(shù)組的函數(shù): isArray()
像 Ajaxian，StackOverflow 等，搜一下，到處都在討論 isArray() 的實現(xiàn)。對于一切都是對象的 JavaScript 來說，確實有點麻煩2011-10-10