摘要:循環鏈表可以像單向鏈表引用,也可以像雙向鏈表有雙向引用。以下就以如何創建棧數據結構為例。
循環鏈表可以像單向鏈表引用,也可以像雙向鏈表有雙向引用。性能上也跟雙向鏈表差不多,如果position大于length/2,那就可以從尾部開始迭代,可以減少迭代的元素。唯一的區別在于最后一個元素指向下一個元素的指針(tail.next)不是undefine,而是第一個元素(head)。接下來來看一下循環鏈表的代碼
循環鏈表 創建循環鏈表class CircularLinkedList extends LinkedList { constructor(equalsFn = defaultEquals) { super(equalsFn); }添加操作 尾插法
push(element) { const node = new Node(element); let current; if (this.head == null) { this.head = node; } else { current = this.getElementAt(this.size() - 1); current.next = node; } // set node.next to head - to have circular list node.next = this.head; this.count++; }任意位置添加元素
insert(element, index) { if (index >= 0 && index <= this.count) { const node = new Node(element); let current = this.head; if (index === 0) { if (this.head == null) { // if no node in list this.head = node; node.next = this.head; } else { node.next = current; current = this.getElementAt(this.size()); // update last element this.head = node; current.next = this.head; } } else { const previous = this.getElementAt(index - 1); node.next = previous.next; previous.next = node; } this.count++; return true; } return false; }刪除操作 刪除任意位置元素
removeAt(index) { if (index >= 0 && index < this.count) { let current = this.head; if (index === 0) { if (this.size() === 1) { this.head = undefined; } else { const removed = this.head; current = this.getElementAt(this.size() - 1); this.head = this.head.next; current.next = this.head; current = removed; } } else { // no need to update last element for circular list const previous = this.getElementAt(index - 1); current = previous.next; previous.next = current.next; } this.count--; return current.element; } return undefined; } }
有序鏈表是指保持元素有序的;鏈表結構,除了使用排序算法之外,我們還可以將元素插入到正確的位置來保證鏈表的有序性。
有序鏈表 創建有序鏈表const Compare = { LESS_THAN: -1, BIGGER_THAN: 1, EQUALS: 0 }; function defaultCompare(a, b) { if (a === b) { return Compare.EQUALS; } return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN; }; function defaultEquals(a, b) { return a === b; }; class SortedLinkedList extends LinkedList { constructor(equalsFn = defaultEquals, compareFn = defaultCompare) { super(equalsFn); this.equalsFn = equalsFn; this.compareFn = compareFn; };查詢操作
getIndexNextSortedElement(element) { let current = this.head; let i = 0; for (; i < this.size() && current; i++) { const comp = this.compareFn(element, current.element); if (comp === Compare.LESS_THAN) { return i; } current = current.next; } return i; } }添加操作 尾插法
push(element) { if (this.isEmpty()) { super.push(element); } else { const index = this.getIndexNextSortedElement(element); super.insert(element, index); } }任意位置有序添加元素
insert(element, index = 0) { if (this.isEmpty()) { return super.insert(element, index === 0 ? index : 0); } const pos = this.getIndexNextSortedElement(element); return super.insert(element, pos); }
以上就是常見的四種鏈表結構,當然我們也可以使用鏈表實現其他數據結構,例如棧,隊列,雙向隊列。以下就以如何創建棧數據結構為例。
鏈表創建棧數據結構class StackLinkedList { constructor() { this.items = new DoublyLinkedList(); } push(element) { this.items.push(element); } pop() { if (this.isEmpty()) { return undefined; } const result = this.items.removeAt(this.size() - 1); return result; } peek() { if (this.isEmpty()) { return undefined; } return this.items.getElementAt(this.size() - 1).element; } isEmpty() { return this.items.isEmpty(); } size() { return this.items.size(); } clear() { this.items.clear(); } toString() { return this.items.toString(); } }總結
鏈表相對數組最大的優點就是無需移動鏈表中的元素,就能輕松的添加和移除元素,所以需要實現添加和移除元素操作時,最好的選擇是鏈表而非數組。
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/106819.html
摘要:每個線性表上的數據最多只有前和后兩個方向。數組鏈表隊列棧等就是線性表結構。非線性表數據之間并不是簡單的前后關系。不包含任何元素的棧稱為空棧。移除棧頂的元素,同時返回被移除的元素。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 前言 基礎知識就像是一座大樓的地基,它決定了我們的技術高度。 我們應該多掌握一些可移值的...
摘要:一般我們都構造雙向循環鏈表。循環鏈表的操作和單鏈表的操作基本一致,差別僅僅在于算法中的循環條件有所不同。單向循環鏈表雙向循環鏈表單向循環鏈表是在單鏈表基礎上,將最后一個節點的指針指向鏈表頭。 維基百科 雙向鏈表也叫雙鏈表,是鏈表的一種,它的每個數據結點中都有兩個指針,分別指向直接后繼和直接前驅。所以,從雙向鏈表中的任意一個結點開始,都可以很方便地訪問它的前驅結點和后繼結點。一般我們都構...
摘要:每個元素由一個存儲元素本身的節點和一個指向下一個元素的引用也稱指針或鏈接組成。相對于傳統的數組,鏈表的一個好處在于,添加或移除元素的時候不需要移動其他元素。然而,鏈表需要使用指針,因此實現鏈表時需要額外注意。 本篇主要有三部分 什么是鏈表 鏈表的實現 鏈表的變種 源碼地址:https://github.com/yhtx1997/S... 另外,今天2019年2月18日上午發現 20...
閱讀 2861·2021-10-14 09:50
閱讀 1218·2021-10-08 10:21
閱讀 3646·2021-10-08 10:16
閱讀 3063·2021-09-27 14:02
閱讀 3135·2021-09-23 11:21
閱讀 2109·2021-09-07 10:17
閱讀 407·2019-08-30 14:00
閱讀 2105·2019-08-29 17:26