摘要:類表示要加入鏈表的項(xiàng)。循環(huán)鏈表和普通鏈表之間唯一的區(qū)別在于,最后一個(gè)元素指向下一個(gè)元素的指針不是引用,而是指向第一個(gè)元素。這里就不進(jìn)行代碼實(shí)現(xiàn)了,大家可以結(jié)合上面的單向鏈表和雙向鏈表自己實(shí)現(xiàn)一個(gè)循環(huán)鏈表。
一、定義 1.1 概念
前面我們學(xué)習(xí)了數(shù)組這種數(shù)據(jù)結(jié)構(gòu)。數(shù)組(或者也可以稱為列表)是一種非常簡(jiǎn)單的存儲(chǔ)數(shù)據(jù)序列的數(shù)據(jù)結(jié)構(gòu)。在這一節(jié),我們要學(xué)習(xí)如何實(shí)現(xiàn)和使用鏈表這種動(dòng)態(tài)的數(shù)據(jù)結(jié)構(gòu),這意味著我們可以從中任意添加或移除項(xiàng),它會(huì)按需進(jìn)行擴(kuò)容。
要存儲(chǔ)多個(gè)元素,數(shù)組(或列表)可能是最常用的數(shù)據(jù)結(jié)構(gòu),它提供了一個(gè)便利的[]語(yǔ)法來訪問它的元素。然而,這種數(shù)據(jù)結(jié)構(gòu)有一個(gè)缺點(diǎn):(在大多數(shù)強(qiáng)類型語(yǔ)言中)數(shù)組的大小是固定的,需要預(yù)先分配,從數(shù)組的起點(diǎn)或中間插入或移除項(xiàng)的成本很高,因?yàn)樾枰苿?dòng)元素。
(注意:在JavaScript中數(shù)組的大小隨時(shí)可變,不需要預(yù)先定義長(zhǎng)度)
鏈表存儲(chǔ)有序的元素集合,但不同于數(shù)組,鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個(gè)元素由一個(gè)存儲(chǔ)元素本身的節(jié)點(diǎn)和一個(gè)指向下一個(gè)元素的引用(也稱指針或鏈接)組成。
相對(duì)于傳統(tǒng)的數(shù)組,鏈表的一個(gè)好處在于,添加或刪除元素的時(shí)候不需要移動(dòng)其他元素。然而,鏈表需要使用指針,因此實(shí)現(xiàn)鏈表時(shí)需要額外注意。數(shù)組的另一個(gè)細(xì)節(jié)是可以直接訪問任何位置的元素,而想要訪問鏈表中間的一個(gè)元素,需要從起點(diǎn)(表頭)開始迭代列表直到找到所需的元素。
火車可以當(dāng)做生活中一個(gè)典型的鏈表的例子。一列火車是由一系列車廂組成的。每節(jié)車廂都相互連接。你很容易分離一節(jié)車廂,改變它的位置,添加或移除它。
1.2 分類鏈表最常用的有三類:
單向鏈表
雙向鏈表
循環(huán)鏈表
二、鏈表的實(shí)現(xiàn) 2.1 單向鏈表創(chuàng)建單向鏈表類:
// SinglyLinkedList function SinglyLinkedList () { function Node (element) { this.element = element; this.next = null; } var length = 0; var head = null; this.append = function (element) {}; this.insert = function (position, element) {}; this.removeAt = function (position) {}; this.remove = function (element) {}; this.indexOf = function (element) {}; this.isEmpty = function () {}; this.size = function () {}; this.getHead = function () {}; this.toString = function () {}; this.print = function () {}; }
SinglyLinkedList需要一個(gè)輔助類Node。Node類表示要加入鏈表的項(xiàng)。它包含一個(gè)element屬性,即要添加到鏈表的值,以及一個(gè)next屬性,即指向鏈表中下一個(gè)節(jié)點(diǎn)項(xiàng)的指針。
鏈表里面有一些聲明的輔助方法:
append(element):向鏈表尾部添加新項(xiàng)
insert(position, element):向鏈表的特定位置插入一個(gè)新的項(xiàng)
removeAt(position):從鏈表的特定位置移除一項(xiàng)
remove(element):從鏈表中移除一項(xiàng)
indexOf(element):返回元素在鏈表中的索引。如果鏈表中沒有該元素則返回-1
isEmpty():如果鏈表中不包含任何元素,返回true,如果鏈表長(zhǎng)度大于0,返回false
size():返回鏈表包含的元素個(gè)數(shù),與數(shù)組的length屬性類似
getHead():返回鏈表的第一個(gè)元素
toString():由于鏈表使用了Node類,就需要重寫繼承自JavaScript對(duì)象默認(rèn)的toString()方法,讓其只輸出元素的值
print():打印鏈表的所有元素
下面我們來一一實(shí)現(xiàn)這些輔助方法:
// 向鏈表尾部添加一個(gè)新的項(xiàng) this.append = function (element) { var node = new Node(element); var currentNode = head; // 判斷是否為空鏈表 if (currentNode === null) { // 空鏈表 head = node; } else { // 從head開始一直找到最后一個(gè)node while (currentNode.next) { // 后面還有node currentNode = currentNode.next; } currentNode.next = node; } length++; }; // 向鏈表特定位置插入一個(gè)新的項(xiàng) this.insert = function (position, element) { if (position < 0 && position > length) { // 越界 return false; } else { var node = new Node(element); var index = 0; var currentNode = head; var previousNode; if (position === 0) { node.next = currentNode; head = node; } else { while (index < position) { index++; previousNode = currentNode; currentNode = currentNode.next; } previousNode.next = node; node.next = currentNode; } length++; return true; } }; // 從鏈表的特定位置移除一項(xiàng) this.removeAt = function (position) { if (position < 0 && position >= length || length === 0) { // 越界 return false; } else { var currentNode = head; var index = 0; var previousNode; if (position === 0) { head = currentNode.next; } else { while (index < position) { index++; previousNode = currentNode; currentNode = currentNode.next; } previousNode.next = currentNode.next; } length--; return true; } }; // 從鏈表的特定位置移除一項(xiàng) this.removeAt = function (position) { if (position < 0 && position >= length || length === 0) { // 越界 return false; } else { var currentNode = head; var index = 0; var previousNode; if (position === 0) { head = currentNode.next; } else { while (index < position) { index++; previousNode = currentNode; currentNode = currentNode.next; } previousNode.next = currentNode.next; } length--; return true; } }; // 從鏈表中移除指定項(xiàng) this.remove = function (element) { var index = this.indexOf(element); return this.removeAt(index); }; // 返回元素在鏈表的索引,如果鏈表中沒有該元素則返回-1 this.indexOf = function (element) { var currentNode = head; var index = 0; while (currentNode) { if (currentNode.element === element) { return index; } index++; currentNode = currentNode.next; } return -1; }; // 如果鏈表中不包含任何元素,返回true,如果鏈表長(zhǎng)度大于0,返回false this.isEmpty = function () { return length == 0; }; // 返回鏈表包含的元素個(gè)數(shù),與數(shù)組的length屬性類似 this.size = function () { return length; }; // 獲取鏈表頭部元素 this.getHead = function () { return head.element; }; // 由于鏈表使用了Node類,就需要重寫繼承自JavaScript對(duì)象默認(rèn)的toString()方法,讓其只輸出元素的值 this.toString = function () { var currentNode = head; var string = ""; while (currentNode) { string += "," + currentNode.element; currentNode = currentNode.next; } return string.slice(1); }; this.print = function () { console.log(this.toString()); };
創(chuàng)建單向鏈表實(shí)例進(jìn)行測(cè)試:
// 創(chuàng)建單向鏈表實(shí)例 var singlyLinked = new SinglyLinkedList(); console.log(singlyLinked.removeAt(0)); // true console.log(singlyLinked.isEmpty()); // true singlyLinked.append("Tom"); singlyLinked.append("Peter"); singlyLinked.append("Paul"); singlyLinked.print(); // "Tom,Peter,Paul" singlyLinked.insert(0, "Susan"); singlyLinked.print(); // "Susan,Tom,Peter,Paul" singlyLinked.insert(1, "Jack"); singlyLinked.print(); // "Susan,Jack,Tom,Peter,Paul" console.log(singlyLinked.getHead()); // "Susan" console.log(singlyLinked.isEmpty()); // false console.log(singlyLinked.indexOf("Peter")); // 3 console.log(singlyLinked.indexOf("Cris")); // -1 singlyLinked.remove("Tom"); singlyLinked.removeAt(2); singlyLinked.print(); // "Susan,Jack,Paul"2.2 雙向鏈表
雙向鏈表和普通鏈表的區(qū)別在于,在普通鏈表中,一個(gè)節(jié)點(diǎn)只有鏈向下一個(gè)節(jié)點(diǎn)的鏈接,而在雙向鏈表中,鏈接是雙向的:一個(gè)鏈向下一個(gè)元素,另一個(gè)鏈向前一個(gè)元素。
創(chuàng)建雙向鏈表類:
// 創(chuàng)建雙向鏈表DoublyLinkedList類 function DoublyLinkedList () { function Node (element) { this.element = element; this.next = null; this.prev = null; // 新增 } var length = 0; var head = null; var tail = null; // 新增 }
可以看到,雙向鏈表在Node類里有prev屬性(一個(gè)新指針),在DoublyLinkedList類里也有用來保存對(duì)列表最后一項(xiàng)的引用的tail屬性。
雙向鏈表提供了兩種迭代列表的方法:從頭到尾,或者從尾到頭。我們可以訪問一個(gè)特定節(jié)點(diǎn)的下一個(gè)或前一個(gè)元素。
在單向鏈表中,如果迭代鏈表時(shí)錯(cuò)過了要找的元素,就需要回到鏈表起點(diǎn),重新開始迭代。在雙向鏈表中,可以從任一節(jié)點(diǎn),向前或向后迭代,這是雙向鏈表的一個(gè)優(yōu)點(diǎn)。
實(shí)現(xiàn)雙向鏈表的輔助方法:
// 向鏈表尾部添加一個(gè)新的項(xiàng) this.append = function (element) { var node = new Node(element); var currentNode = tail; // 判斷是否為空鏈表 if (currentNode === null) { // 空鏈表 head = node; tail = node; } else { currentNode.next = node; node.prev = currentNode; tail = node; } length++; }; // 向鏈表特定位置插入一個(gè)新的項(xiàng) this.insert = function (position, element) { if (position < 0 && position > length) { // 越界 return false; } else { var node = new Node(element); var index = 0; var currentNode = head; var previousNode; if (position === 0) { if (!head) { head = node; tail = node; } else { node.next = currentNode; currentNode.prev = node; head = node; } } else if (position === length) { this.append(element); } else { while (index < position) { index++; previousNode = currentNode; currentNode = currentNode.next; } previousNode.next = node; node.next = currentNode; node.prev = previousNode; currentNode.prev = node; } length++; return true; } }; // 從鏈表的特定位置移除一項(xiàng) this.removeAt = function (position) { if (position < 0 && position >= length || length === 0) { // 越界 return false; } else { var currentNode = head; var index = 0; var previousNode; if (position === 0) { // 移除第一項(xiàng) if (length === 1) { head = null; tail = null; } else { head = currentNode.next; head.prev = null; } } else if (position === length - 1) { // 移除最后一項(xiàng) if (length === 1) { head = null; tail = null; } else { currentNode = tail; tail = currentNode.prev; tail.next = null; } } else { while (index < position) { index++; previousNode = currentNode; currentNode = currentNode.next; } previousNode.next = currentNode.next; previousNode = currentNode.next.prev; } length--; return true; } }; // 從鏈表中移除指定項(xiàng) this.remove = function (element) { var index = this.indexOf(element); return this.removeAt(index); }; // 返回元素在鏈表的索引,如果鏈表中沒有該元素則返回-1 this.indexOf = function (element) { var currentNode = head; var index = 0; while (currentNode) { if (currentNode.element === element) { return index; } index++; currentNode = currentNode.next; } return -1; }; // 如果鏈表中不包含任何元素,返回true,如果鏈表長(zhǎng)度大于0,返回false this.isEmpty = function () { return length == 0; }; // 返回鏈表包含的元素個(gè)數(shù),與數(shù)組的length屬性類似 this.size = function () { return length; }; // 獲取鏈表頭部元素 this.getHead = function () { return head.element; }; // 由于鏈表使用了Node類,就需要重寫繼承自JavaScript對(duì)象默認(rèn)的toString()方法,讓其只輸出元素的值 this.toString = function () { var currentNode = head; var string = ""; while (currentNode) { string += "," + currentNode.element; currentNode = currentNode.next; } return string.slice(1); }; this.print = function () { console.log(this.toString()); };
創(chuàng)建雙向鏈表實(shí)例進(jìn)行測(cè)試:
// 創(chuàng)建雙向鏈表 var doublyLinked = new DoublyLinkedList(); console.log(doublyLinked.isEmpty()); // true doublyLinked.append("Tom"); doublyLinked.append("Peter"); doublyLinked.append("Paul"); doublyLinked.print(); // "Tom,Peter,Paul" doublyLinked.insert(0, "Susan"); doublyLinked.print(); // "Susan,Tom,Peter,Paul" doublyLinked.insert(1, "Jack"); doublyLinked.print(); // "Susan,Jack,Tom,Peter,Paul" console.log(doublyLinked.getHead()); // "Susan" console.log(doublyLinked.isEmpty()); // false console.log(doublyLinked.indexOf("Peter")); // 3 console.log(doublyLinked.indexOf("Cris")); // -1 doublyLinked.remove("Tom"); doublyLinked.removeAt(2); doublyLinked.print(); // "Susan,Jack,Paul"2.3 循環(huán)鏈表
循環(huán)鏈表可以像單向鏈表一樣只有單向引用,也可以像雙向鏈表一樣有雙向引用。循環(huán)鏈表和普通鏈表之間唯一的區(qū)別在于,最后一個(gè)元素指向下一個(gè)元素的指針(next)不是引用null,而是指向第一個(gè)元素(head)。這里就不進(jìn)行代碼實(shí)現(xiàn)了,大家可以結(jié)合上面的單向鏈表和雙向鏈表自己實(shí)現(xiàn)一個(gè)循環(huán)鏈表。
三、結(jié)束本文會(huì)同步到我的個(gè)人博客,完整代碼可以到我的github倉(cāng)庫(kù)查看,如果對(duì)你有幫助的話歡迎點(diǎn)一個(gè)Star~~
歡迎關(guān)注我的公眾號(hào)文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/96564.html
摘要:給定一個(gè)鏈表,一個(gè)范圍在內(nèi)的索引號(hào),和一個(gè)數(shù)據(jù),這個(gè)函數(shù)會(huì)生成一個(gè)新的節(jié)點(diǎn)并插入到指定的索引位置,并始終返回鏈表的頭。的返回值一定是個(gè)鏈表,我們把它賦值給就行。但這個(gè)例子的邊界情況是返回值不同如果,返回新節(jié)點(diǎn)。 TL;DR 插入第 N 個(gè)節(jié)點(diǎn)。系列目錄見 前言和目錄 。 需求 實(shí)現(xiàn)一個(gè) insertNth() 方法,在鏈表的第 N 個(gè)索引處插入一個(gè)新節(jié)點(diǎn)。 insertNth() 可以...
摘要:月下半旬攻略道題,目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題,所以后面會(huì)調(diào)整自己,在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí),攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題,目前已攻略 100 題。 一 目錄 不折騰的前端,和咸魚有什么區(qū)別...
摘要:記錄壓縮列表總共占用的字節(jié)數(shù),在對(duì)壓縮列表進(jìn)行內(nèi)存重分配時(shí)使用個(gè)字節(jié)。為十六進(jìn)制值,標(biāo)記一個(gè)壓縮列表的末尾具體的數(shù)據(jù)存放在中。占用或字節(jié)表示當(dāng)前存儲(chǔ)數(shù)據(jù)的類型與數(shù)據(jù)的長(zhǎng)度。在學(xué)習(xí)的同時(shí),如果沒有經(jīng)過自己的思考,收效甚微。 baiyan全部視頻:https://segmentfault.com/a/11... 為什么需要ziplist 乍一看標(biāo)題,我們可能還不知道ziplist是何許人也...
摘要:一簡(jiǎn)介內(nèi)部是通過雙向鏈表存儲(chǔ)的,提供順序訪問。繼承了,實(shí)現(xiàn)在迭代器上的隨機(jī)訪問。四總結(jié)本節(jié)分析了的源碼的用法。實(shí)現(xiàn)了接口,內(nèi)部通過鏈表實(shí)現(xiàn),能夠?qū)崿F(xiàn)鏈表隊(duì)列棧和雙端隊(duì)列等數(shù)據(jù)結(jié)構(gòu)的功能。 一、LinkedList簡(jiǎn)介 LinkedList內(nèi)部是通過雙向鏈表存儲(chǔ)的,提供順序訪問。繼承了AbstractSequentialList,實(shí)現(xiàn)在迭代器上的隨機(jī)訪問。并且,還實(shí)現(xiàn)了List、Dequ...
摘要:全部視頻每日學(xué)習(xí)記錄使用錄像設(shè)備記錄每天的學(xué)習(xí)字典是啥,即字典,也被稱為哈希表。通常情況下,一個(gè)長(zhǎng)這樣在這個(gè)哈希表中,每個(gè)存儲(chǔ)單元被稱為一個(gè)桶。完成之后,新哈希表就會(huì)被置為,為線上提供服務(wù)。 baiyan 全部視頻:【每日學(xué)習(xí)記錄】使用錄像設(shè)備記錄每天的學(xué)習(xí) 字典是啥 dict,即字典,也被稱為哈希表hashtable。在redis的五大數(shù)據(jù)結(jié)構(gòu)中,有如下兩種情形會(huì)使用dict結(jié)構(gòu): ...
閱讀 844·2023-04-25 21:21
閱讀 3226·2021-11-24 09:39
閱讀 3067·2021-09-02 15:41
閱讀 1993·2021-08-26 14:13
閱讀 1827·2019-08-30 11:18
閱讀 2768·2019-08-29 16:25
閱讀 507·2019-08-28 18:27
閱讀 1580·2019-08-28 18:17