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