JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表和雙向循環(huán)鏈表的實(shí)現(xiàn)
雙向鏈表和普通鏈表的區(qū)別在于,在鏈表中,一個(gè)節(jié)點(diǎn)只有鏈向下一個(gè)節(jié)點(diǎn)的鏈接,而在雙向鏈表中,鏈接是雙向的:一個(gè)鏈向下一個(gè)元素,另一個(gè)鏈向前一個(gè)元素。
雙向鏈表提供了兩種迭代列表的方法:從頭到尾,或者反過來。我們也可以訪問一個(gè)特定節(jié)點(diǎn)的下一個(gè)或前一個(gè)元素。在單向鏈表中,如果迭代列表時(shí)錯(cuò)過了要找的元素,就需要回到列表起點(diǎn),重新開始迭代。這是雙向鏈表的一個(gè)優(yōu)點(diǎn)。
雙向鏈表:單向鏈表只能向著一個(gè)方向遍歷鏈表節(jié)點(diǎn),而在節(jié)點(diǎn)指針域中增加了前向指針的雙向鏈表,則可以向著兩個(gè)方向遍歷節(jié)點(diǎn)。這使得雙向鏈表也可以在任何一個(gè)節(jié)點(diǎn)遍歷整個(gè)鏈表。
function DoublyLinkedList() { var Node = function(element) { this.element = element; this.next = null; this.prev = null; }; var length = 0, head = null, tail = null; this.append = function(element){ var node = Node(element), current, previous; if(!head){ head = node; tail = node; }else{ current = head; while(current){ previous = current; current = current.next; } node.next = current; current.prev = node; previous.next = node; node.prev = previous; } length++; return true; } this.insert = function(position,element){ if(position > -1 && position < length){ var node = new Node(element), current = head, previous, index = 0; if(position === 0){ if(!head){ head = node; tail = node; }else{ node.next = current; current.prev = node; head = node; } }else if (position === length -1){ current = tail; current.next = node; node.prev = current; }else { while(index++ < position){ previous = current; current = current.next; } node.next = current; previous.next = node; current.prev = node; node.prev = previous; } length++; return true; }else{ return false; } }; this.removeAt = function(position){ if(position > -1 && position < length){ var current = head, index = 0, previous; if (position === 0) { head = current.next; if(length === 1){ tail = null; }else{ head.prev = null; } }else if(position === length - 1){ current = tail; tail = current.prev; tail.next = null; } else{ while(index++ < position){ previous = current; current = current.next; } previous.next = current.next; current.next.prev = previous; }; length-- ; return current.element; }else{ return false; } }; this.remove = function(element){ var current = head, previous; if(current.element === element){ head = current.next; } previous = current; current = current.next; while(current){ if (current.element = element) { previous.next = current.next; current.next.prev = previous; }else{ previous = current; current = current.next; } } return false; }; this.remove = function(){ if (length === 0) { return false; }; var current = head, previous; if(length === 1){ head = null; tail = null; length--; return current.element; } while(current){ previous = current; current = current.next; } previous.next = null; length--; return current.element; }; this.indexOf = function(element){ var current = head, index = 0; while(current && index++ < length){ if (current.element === element) { return index; }; current = current.next; } return false; }; this.isEmpty = function(){ return length === 0; }; this.size = function(){ return length; }; this.toString = function(){ var current = head, string = ''; while(current){ string += current.element; current = current.next; } return string; }; this.getHead = function(){ return head; }; this.getTail = function(){ return tail; }; }
雙向循環(huán)鏈表:將雙向鏈表的頭尾指針相連,就構(gòu)成了雙向循環(huán)鏈表。這種鏈表從任意一個(gè)節(jié)點(diǎn)都可以同時(shí)向兩個(gè)方向進(jìn)行節(jié)點(diǎn)遍歷,查詢節(jié)點(diǎn)的速度也是最快的。
/*雙向循環(huán)鏈表*/ function DoublyCircularLinkedList(){ var Node = function(element){ this.element = element; this.next = null; this.prev = null; }; var length = 0, head = null, tail = null; this.append = function(element){ var node = new Node(element), current, previous; if (!head) { head = node; tail = node; head.prev = tail; tail.next = head; }else{ current = head; while(current.next !== head){ previous = current; current = current.next; } current.next = node; node.next = head; node.prev = current; }; length++; return true; }; this.insert = function(position, element){ if(position >= 0 && position <= length){ var node = new Node(element), index = 0, current = head, previous; if(position === 0){ if(!head){ node.next = node; node.tail = node; head = node; tail = node; }else{ current.prev = node; node.next = current; head = node; node.prev = tail; } }else if(position === length){ current = tail; current.next = node; node.prev = current; tail = node; node.next = head; }else{ while(index++ < position){ previous = current; current = current.next; } current.prev = node; node.next = current; previous.next = node; node.prev = previous; } length++; return true; }else{ return false; } }; this.removeAt = function(position){ if(position > -1 && position < length){ var current = head, index = 0, previous; if(position === 0){ current.next.previous = tail; head = current.next; }else if(position === length - 1){ current = tail; current.prev.next = head; head.prev = current.prev; tail = current.prev; }else{ while(index++ < position){ previous = current; current = current.next; } previous.next = current.next; current.next.prev = previous; } length--; return true; }else{ return false; } }; this.remove = function(element){ var current = head, previous, indexCheck = 0; while(current && indexCheck < length){ if(current.element === element){ if(indexCheck === 0){ current.next.prev = tail; head = current.next; }else{ current.next.prev = previous; previous.next = current.next; } length--; return true; } previous = current; current = current.next; indexCheck++; } return false; }; this.remove = function(){ if(length === 0){ return false; } var current = head, previous, indexCheck = 0; if(length === 1){ head = null; tail = null; length--; return current.element; } while(indexCheck++ < length){ previous = current; current = current.next; } previous.next = head; tail = previous.next; length--; return current.element; }; this.indexOf = function(element){ var current = head, index = 0; while(current && index++ < length){ if(current.element === element){ return index; } current = current.next; } return false; }; this.toString = function(){ var current = head, indexCheck = 0, string = ''; while(current && indexCheck < length){ string += current.element; indexCheck++; current = current.next; } return string; }; this.isEmpty = function(){ return length === 0; }; this.getHead = function(){ return head; }; this.getTail = function(){ return tail; }; this.size = function(){ return length; }; }
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
- JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表
- JavaScript數(shù)據(jù)結(jié)構(gòu)之單鏈表和循環(huán)鏈表
- JavaScript數(shù)據(jù)結(jié)構(gòu)之雙向鏈表定義與使用方法示例
- 使用JavaScript實(shí)現(xiàn)鏈表的數(shù)據(jù)結(jié)構(gòu)的代碼
- JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表的實(shí)現(xiàn)
- JavaScript數(shù)據(jù)結(jié)構(gòu)鏈表知識詳解
- JavaScript數(shù)據(jù)結(jié)構(gòu)與算法之鏈表
- JavaScript實(shí)現(xiàn)的鏈表數(shù)據(jù)結(jié)構(gòu)實(shí)例
- JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表各種操作詳解
相關(guān)文章
Javascript Echarts空氣質(zhì)量地圖效果詳解
這篇文章主要介紹了詳解Javascript利用echarts畫空氣質(zhì)量地圖,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-10-10JavaScript實(shí)現(xiàn)手風(fēng)琴效果
這篇文章主要為大家詳細(xì)介紹了JavaScript實(shí)現(xiàn)手風(fēng)琴效果,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-02-02動態(tài)創(chuàng)建的表格單元格中的事件實(shí)現(xiàn)代碼
好久沒有搞網(wǎng)頁了,今天重新弄了一個(gè) ,做個(gè)動態(tài)表格,具體的實(shí)現(xiàn)代碼,大家可以自己寫吧2008-12-12uniapp和uniCloud開發(fā)中常出現(xiàn)的問題及解決匯總
使用uni 開發(fā)一段時(shí)間了,下面這篇文章主要給大家介紹了關(guān)于uniapp和uniCloud開發(fā)中常出現(xiàn)的問題及解決的相關(guān)資料,文中通過圖文介紹的非常詳細(xì),需要的朋友可以參考下2022-12-12