這篇文章主要介紹了JavaScript基于對象的鏈表怎么定義的相關(guān)知識,內(nèi)容詳細易懂,操作簡單快捷,具有一定借鑒價值,相信大家閱讀完這篇JavaScript基于對象的鏈表怎么定義文章都會有所收獲,下面我們一起來看看吧。
鏈表的概念
鏈表是一種常見的數(shù)據(jù)結(jié)構(gòu)。它是動態(tài)地進行存儲分配的一種結(jié)構(gòu)。鏈表有一個“頭指針”變量,以head表示,它存放一個地址,指向一個元素。每個結(jié)點都使用一個對象的引用指標它的后繼,指向另一個結(jié)點的引用叫做鏈。
數(shù)組元素依靠下標(位置)來進行引用,而鏈表元素則是靠相互之間的關(guān)系來進行引用。因此鏈表的插入效率很高,下圖演示了鏈表結(jié)點d的插入過程:
刪除過程:
基于對象的鏈表
我們定義2個類,Node類與LinkedList類,Node為結(jié)點數(shù)據(jù),LinkedList保存操作鏈表的方法。
首先看Node類:
function Node(element){ this.element = element; this.next = null; }
element用來保存結(jié)點上的數(shù)據(jù),next用來保存指向一下結(jié)點的的鏈接?! ?/p>
LinkedList類:
function LinkedList(){ this.head = new Node('head'); this.find = find; this.insert = insert; this.remove = remove; this.show = show; }
find()方法,從頭結(jié)點開始,沿著鏈表結(jié)點一直查找,直到找到與item內(nèi)容相等的element則返回該結(jié)點,沒找到則返回空。
function find(item){ var currentNode = this.head;//從頭結(jié)點開始 while(currentNode.element!=item){ currentNode = currentNode.next; } return currentNode;//找到返回結(jié)點數(shù)據(jù),沒找到返回null }
Insert方法。通過前面元素插入的演示可以看出,實現(xiàn)插入簡單四步:
1、創(chuàng)建結(jié)點
2、找到目標結(jié)點
3、修改目標結(jié)點的next指向鏈接
4、將目標結(jié)點的next值賦值給要插入的結(jié)點的next
function insert(newElement,item){ var newNode = new Node(newElement); var currentNode = this.find(item); newNode.next = currentNode.next; currentNode.next = newNode; }
Remove()方法。刪除某一節(jié)點需要先找到被刪除結(jié)點的前結(jié)點,為此我們定義方法frontNode():
function frontNode(item){ var currentNode = this.head; while(currentNode.next.element!=item&¤tNode.next!=null){ currentNode = currentNode.next; } return currentNode; }
簡答三步:
1、創(chuàng)建結(jié)點
2、找到目標結(jié)點的前結(jié)點
3、修改前結(jié)點的next指向被刪除結(jié)點的n后一個結(jié)點
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結(jié)點 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());
輸出:
雙向鏈表
從鏈表的頭節(jié)點遍歷到尾節(jié)點很簡單,但有的時候,我們需要從后向前遍。此時我們可以通過給 Node 對象增加一個屬性,該屬性存儲指向前驅(qū)節(jié)點的鏈接。
首先我們先給Node類增加front屬性:
function Node(element){ this.element = element; this.next = null; this.front = null; }
當(dāng)然,對應(yīng)的insert()方法和remove()方法我們也需要做相應(yīng)的修改:
function insert(newElement,item){ var newNode = new Node(newElement); var currentNode = this.find(item); newNode.next = currentNode.next; newNode.front = currentNode;//增加front指向前驅(qū)結(jié)點 currentNode.next = newNode; } function remove(item){ var currentNode = this.find(item);//找到需要刪除的節(jié)點 if (currentNode.next != null) { currentNode.front.next = currentNode.next;//讓前驅(qū)節(jié)點指向需要刪除的節(jié)點的下一個節(jié)點 currentNode.next.front = currentNode.front;//讓后繼節(jié)點指向需要刪除的節(jié)點的上一個節(jié)點 currentNode.next = null;//并設(shè)置前驅(qū)與后繼的指向為空 currentNode.front = null; } }
反序顯示鏈表:
需要給雙向鏈表增加一個方法,用來查找最后的節(jié)點。 findLast() 方法找出了鏈表中的最后一個節(jié)點,可以免除從前往后遍歷鏈。
function findLast() {//查找鏈表的最后一個節(jié)點 var currentNode = this.head; while (currentNode.next != null) { currentNode = currentNode.next; } return currentNode; }
實現(xiàn)反序輸出:
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());
輸出:
循環(huán)鏈表
循環(huán)鏈表是另一種形式的鏈式存貯結(jié)構(gòu)。它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點,整個鏈表形成一個環(huán)。循環(huán)鏈表和單向鏈表相似,節(jié)點類型都是一樣的。唯一的區(qū)別是,在創(chuàng)建循環(huán)鏈表時,讓其頭節(jié)點的 next 屬性指向它本身,即:
head.next = head
這種行為會傳導(dǎo)至鏈表中的每個節(jié)點,使得每個節(jié)點的 next 屬性都指向鏈表的頭節(jié)點。
修改構(gòu)造方法:
function LinkedList(){ this.head = new Node('head');//初始化 this.head.next = this.head;//直接將頭節(jié)點的next指向頭節(jié)點形成循環(huán)鏈表 this.find = find; this.frontNode = frontNode; this.insert = insert; this.remove = remove; this.show = show; }
這時需要注意鏈表的輸出方法show()與find()方法,原來的方式在循環(huán)鏈表里會陷入死循環(huán),while循環(huán)的循環(huán)條件需要修改為當(dāng)循環(huán)到頭節(jié)點時退出循環(huán)。
function find(item){ var currentNode = this.head;//從頭結(jié)點開始 while(currentNode.element!=item&¤tNode.next.element!='head'){ currentNode = currentNode.next; } return currentNode;//找到返回結(jié)點數(shù)據(jù),沒找到返回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());
測試結(jié)果:
關(guān)于“JavaScript基于對象的鏈表怎么定義”這篇文章的內(nèi)容就介紹到這里,感謝各位的閱讀!相信大家對“JavaScript基于對象的鏈表怎么定義”知識都有一定的了解,大家如果還想學(xué)習(xí)更多知識,歡迎關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。