本文主要介紹了JavaScript資料結構之單鍊錶、循環鍊錶,詳細的介紹了JavaScript如何實現單鍊錶、循環鍊錶,有興趣的可以了解一下,希望能幫助到大家。
進入正題,關於鍊錶的資料結構知識,這裡簡單介紹下:
鍊錶是一種物理儲存單元上非線性、非連續性的資料結構(它在資料邏輯上是線性的),它的每個節點由兩個域組成:資料域和指標域。資料域中儲存實際數據,指標域則儲存指標訊息,指向鍊錶中的下一個元素或上一個元素。正是由於指標的存在,鍊錶的儲存在物理單元是非連續性的。
鍊錶的優點和缺點同樣明顯。和線性表相比,鍊錶在新增和刪除節點上的效率更高,因為其只需要修改指標資訊即可完成操作,而不是像線性表(陣列)那樣需要移動元素。同樣的,鍊錶的長度在理論上也是無限的(在記憶體容量範圍內),並且可以動態變化長度,相比線性表優勢很大。 對應的,由於線性表無法隨機存取節點,只能透過指標順著鍊錶進行遍歷查詢來訪問,故其存取資料元素的效率比較低。
下面是JS部分
這裡面封裝了的常用方法及描述:
描述 | |
---|---|
新增結點element | |
向位置position處插入結點element | |
依照索引值position刪除結點 | |
搜尋並刪除給定結點element | |
刪除鍊錶中最後一個結點 | |
找出並傳回給定結點element的索引值 | |
判斷鍊錶是否為空 | |
# 取得鍊錶長度 | ##toString() |
getHead() | |
getTail() | |
function LinkedList(){ /*节点定义*/ var Node = function(element){ this.element = element; //存放节点内容 this.next = null; //指针 } var length = 0, //存放链表长度 head = null; //头指针 this.append = function(element){ var node = new Node(element), current; //操作所用指针 if (!head){ head = node; }else { current = head; while(current.next){ current = current.next; } current.next = node; } length++; return true; }; this.insert = function(position, element){ if (position >= 0 && position <= length) { var node = new Node(element), current = head, previous, index = 0; if(position === 0){ node.next = current; head = node; }else{ while(index++ < position){ previous = current; current = current.next; } node.next = current; previous.next = node; } length++; return true; }else{ return false; } }; this.removeAt = function(position){ if(position > -1 && position < length){ var current = head, previous, index = 0; if (position === 0) { head = current.next; }else{ while (index++ < position){ previous = current; current = current.next; } previous.next = current.next; }; length--; return current.element; }else{ return null; } }; this.remove = function(element){ var current = head, previous; if(element === current.element){ head = current.next; length--; return true; } previous = current; current = current.next; while(current){ if(element === current.element){ previous.next = current.next; length--; return true; }else{ previous = current; current = current.next; } } return false; }; this.remove = function(){ if(length < 1){ return false; } var current = head, previous; if(length == 1){ head = null; length--; return current.element; } while(current.next !== null){ previous = current; current = current.next; } previous.next = null; length--; return current.element; }; this.indexOf = function(element){ var current = head, index = 0; while(current){ if(element === current.element){ return index; } 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; } }
循環鍊錶:在單鍊錶的基礎上,將尾節點的指標指向頭結點,就構成了一個循環鍊錶。環形鍊錶從任一個節點開始,都可以遍歷整個鍊錶。
function CircularLinkedList(){ var Node = function(element){ this.element = element; this.next = null; } var length = 0, head = null; this.append = function(element){ var node = new Node(element), current; if (!head) { head = node; node.next = head; }else{ current = head; while(current.next !== head){ current = current.next; } current.next = node; node.next = head; }; length++; return true; }; this.insert = function(position, element){ if(position > -1 && position < length){ var node = new Node(element), index = 0, current = head, previous; if (position === 0) { node.next = head; head = node; }else{ while(index++ < position){ previous = current; current = current.next; } previous.next = node; node.next = current; }; length++; return true; }else{ return false; } }; this.removeAt = function(position){ if(position > -1 && position < length){ var current = head, previous, index = 0; if (position === 0) { head = current.next; }else{ while (index++ < position){ previous = current; current = current.next; } previous.next = current.next; }; length--; return current.element; }else{ return null; } }; this.remove = function (element){ var current = head, previous, indexCheck = 0; while(current && indexCheck < length){ if(current.element === element){ if(indexCheck == 0){ head = current.next; length--; return true; }else{ previous.next = current.next; length--; return true; } }else{ 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; length--; return current.element; } while(indexCheck++ < length){ previous = current; current = current.next; } previous.next = head; length--; return current.element; }; this.indexOf = function(element){ var current = head, index = 0; while(current && index < length){ if(current.element === element){ return index; }else{ index++; current = current.next; } } return false; }; this.isEmpty = function(){ return length === 0; }; this.size = function(){ return length; }; this.toString = function(){ var current = head, string = '', indexCheck = 0; while(current && indexCheck < length){ string += current.element; current = current.next; indexCheck++; } return string; }; }
使用方法:
#在類別外部擴充方法:
相關推薦:
JavaScript資料結構中雙向鍊錶的使用定義的範例
JavaScript資料結構之二元查找樹的定義與表示方法詳解
以上是JavaScript資料結構之單鍊錶與循環鍊錶實例分享的詳細內容。更多資訊請關注PHP中文網其他相關文章!