摘要:計算機科學(xué)中最常見的兩種數(shù)據(jù)結(jié)構(gòu)是單鏈表和雙鏈表。雙向鏈表雙向鏈表具有單鏈表的所有功能,并將其擴展為在鏈表中可以進行雙向遍歷。雙向鏈表的操作我們的鏈表將包括兩個構(gòu)造函數(shù)和。與單鏈表不同,雙向鏈表包含對鏈表開頭和結(jié)尾節(jié)點的引用。
翻譯:瘋狂的技術(shù)宅
英文:https://code.tutsplus.com/art...
說明:本文翻譯自系列文章《Data Structures With JavaScript》,總共為四篇,原作者是在美國硅谷工作的工程師 Cho S. Kim 。這是本系列的第三篇。
說明:本專欄文章首發(fā)于公眾號:jingchengyideng 。
計算機科學(xué)中最常見的兩種數(shù)據(jù)結(jié)構(gòu)是單鏈表和雙鏈表。
在我學(xué)習(xí)這些數(shù)據(jù)結(jié)構(gòu)的時候,曾經(jīng)問我的同伴在生活中有沒有類似的概念。我所聽到的例子是購物清單和火車。但是我最終明白了,這些類比是不準(zhǔn)確的,購物清單更類似隊列,火車則更像是一個數(shù)組。
隨著時間的推移,我終于發(fā)現(xiàn)了一個能夠準(zhǔn)確類比單鏈表和雙向鏈表的例子:尋寶游戲。 如果你對尋寶游戲和鏈表之間的關(guān)系感到好奇,請繼續(xù)往下讀。
單鏈表在計算機科學(xué)中,單鏈表是一種數(shù)據(jù)結(jié)構(gòu),保存了一系列鏈接的節(jié)點。 每個節(jié)點中包含數(shù)據(jù)和一個可指向另一個節(jié)點的指針。
單鏈列表的節(jié)點非常類似于尋寶游戲中的步驟。 每個步驟都包含一條消息(例如“您已到達法國”)和指向下一步驟的指針(例如“訪問這些經(jīng)緯度坐標(biāo)”)。 當(dāng)我們開始對這些多帶帶的步驟進行排序并形成一系列步驟時,就是在玩一個尋寶游戲。
現(xiàn)在我們對單鏈表有了一個基本的概念,接下來討論單鏈表的操作
單鏈表的操作因為單鏈表包含節(jié)點,這兩者的構(gòu)造函數(shù)可以是兩個獨立的構(gòu)造函數(shù),所以我們需要些構(gòu)造函數(shù):Node 和 SinglyList
Nodedata 存儲數(shù)據(jù)
next 指向鏈表中下一個節(jié)點的指針
SinglyList_length 用于表示鏈表中的節(jié)點數(shù)量
head 分配一個節(jié)點作為鏈表的頭
add(value) 向鏈表中添加一個節(jié)點
searchNodeAt(position) 找到在列表中指定位置 n 上的節(jié)點
remove(position) 刪除指定位置的節(jié)點
單鏈表的實現(xiàn)在實現(xiàn)時,我們首先定義一個名為Node的構(gòu)造函數(shù),然后定義一個名為SinglyList的構(gòu)造函數(shù)。
Node 的每個實例都應(yīng)該能夠存儲數(shù)據(jù)并且能夠指向另外一個節(jié)點。 要實現(xiàn)此功能,我們將分別創(chuàng)建兩個屬性:data和next。
function Node(data) { this.data = data; this.next = null; }
下一步我們定義SinglyList:
function SinglyList() { this._length = 0; this.head = null; }
SinglyList 的每個實例有兩個屬性:_length和head。前者保存鏈表中的節(jié)點數(shù),后者指向鏈表的頭部,鏈表前面的節(jié)點。由于新創(chuàng)建的singlylist實例不包含任何節(jié)點,所以head的默認(rèn)值是null,_length的默認(rèn)值是 0。
單鏈表的方法我們需要定義可以從鏈表中添加、查找和刪除節(jié)點的方法。先從添加節(jié)點開始。
方法1/3: add(value)太棒了,現(xiàn)在我們來實現(xiàn)將節(jié)點添加到鏈表的功能。
SinglyList.prototype.add = function(value) { var node = new Node(value), currentNode = this.head; // 1st use-case: an empty list if (!currentNode) { this.head = node; this._length++; return node; } // 2nd use-case: a non-empty list while (currentNode.next) { currentNode = currentNode.next; } currentNode.next = node; this._length++; return node; };
把節(jié)點添加到鏈表會涉及很多步驟。先從方法開始。 我們使用add(value)的參數(shù)來創(chuàng)建一個節(jié)點的新實例,該節(jié)點被分配給名為node的變量。我們還聲明了一個名為currentNode的變量,并將其初始化為鏈表的_head。 如果鏈表中還沒有節(jié)點,那么head的值為null。
實現(xiàn)了這一點之后,我們將處理兩種情況。
第一種情況考慮將節(jié)點添加到空的鏈表中,如果head沒有指向任何節(jié)點的話,那么將該node指定為鏈表的頭,同時鏈表的長度加一,并返回node。
第二種情況考慮將節(jié)點添加到飛空鏈表。我們進入while循環(huán),在每次循環(huán)中,判斷currentNode.next是否指向下一個節(jié)點。(第一次循環(huán)時,CurrentNode指向鏈表的頭部。)
如果答案是否定的,我們會把currentnode.next指向新添加的節(jié)點,并返回node。
如果答案是肯定的,就進入while循環(huán)。 在循環(huán)體中,我們將currentNode重新賦值給currentNode.next。 重復(fù)這個過程,直到currentNode.next不再指向任何。換句話說,currentNode指向鏈表中的最后一個節(jié)點。
while循環(huán)結(jié)束后,使currentnode.next指向新添加的節(jié)點,同時_length加1,最后返回node。
方法2/3: searchNodeAt(position)現(xiàn)在我們可以將節(jié)點添加到鏈表中了,但是還沒有辦法找到特定位置的節(jié)點。下面添加這個功能。創(chuàng)建一個名為searchNodeAt(position) 的方法,它接受一個名為 position 的參數(shù)。這個參數(shù)是個整數(shù),用來表示鏈表中的位置n。
SinglyList.prototype.searchNodeAt = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: "Failure: non-existent node in this list."}; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: a valid position while (count < position) { currentNode = currentNode.next; count++; } return currentNode; };
在if中檢查第一種情況:參數(shù)非法。
如果傳給searchNodeAt(position)的索引是有效的,那么我們執(zhí)行第二種情況 —— while循環(huán)。 在while的每次循環(huán)中,指向頭的currentNode被重新指向鏈表中的下一個節(jié)點。
這個循環(huán)不斷執(zhí)行,一直到count等于position。
方法3/3: remove(position)最后一個方法是remove(position)。
SinglyList.prototype.remove = function(position) { var currentNode = this.head, length = this._length, count = 0, message = {failure: "Failure: non-existent node in this list."}, beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (position < 0 || position > length) { throw new Error(message.failure); } // 2nd use-case: the first node is removed if (position === 1) { this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; return deletedNode; } // 3rd use-case: any other node is removed while (count < position) { beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; } beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; };
我們要實現(xiàn)的remove(position)涉及三種情況:
無效的位置作為參數(shù)傳遞。
第一個位置(鏈表的的`head)作為參數(shù)的傳遞。
一個合法的位置(不是第一個位置)作為參數(shù)的傳遞。
前兩種情況是最簡單的處理。 關(guān)于第一種情況,如果鏈表為空或傳入的位置不存在,則會拋出錯誤。
第二種情況處理鏈表中第一個節(jié)點的刪除,這也是頭節(jié)點。 如果是這種情況,就執(zhí)行下面的邏輯:
頭被重新賦值給currentNode.next。
deletedNode指向currentNode。
currentNode被重新賦值為null。
將的鏈表的長度減1。
返回deletedNode。
第三種情況是最難理解的。 其復(fù)雜性在于我們要在每一次循環(huán)中操作兩個節(jié)點的必要性。 在每次循環(huán)中,需要處理要刪除的節(jié)點和它前面的節(jié)點。當(dāng)循環(huán)到要被刪除的位置的節(jié)點時,循環(huán)終止。
在這一點上,我們涉及到三個節(jié)點:
beforeNodeToDelete, nodeToDelete, 和 deletedNode。刪除nodeToDelete之前,必須先把它的next的值賦給beforeNodeToDelete的next,如果不清楚這一步驟的目的,可以提醒自己有一個節(jié)點負(fù)責(zé)鏈接其前后的其他節(jié)點,只需要刪除這個節(jié)點,就可以把鏈表斷開。
接下來,我們將deletedNode賦值給nodeToDelete。 然后我們將nodeToDelete的值設(shè)置為null,將列表的長度減1,最后返回deletedNode。
單向鏈表的完整實現(xiàn)以下是單向鏈表的完整實現(xiàn):
function Node(data) { this.data = data; this.next = null; } function SinglyList() { this._length = 0; this.head = null; } SinglyList.prototype.add = function(value) { var node = new Node(value), currentNode = this.head; // 1st use-case: an empty list if (!currentNode) { this.head = node; this._length++; return node; } // 2nd use-case: a non-empty list while (currentNode.next) { currentNode = currentNode.next; } currentNode.next = node; this._length++; return node; }; SinglyList.prototype.searchNodeAt = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: "Failure: non-existent node in this list."}; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: a valid position while (count < position) { currentNode = currentNode.next; count++; } return currentNode; }; SinglyList.prototype.remove = function(position) { var currentNode = this.head, length = this._length, count = 0, message = {failure: "Failure: non-existent node in this list."}, beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (position < 0 || position > length) { throw new Error(message.failure); } // 2nd use-case: the first node is removed if (position === 1) { this.head = currentNode.next; deletedNode = currentNode; currentNode = null; this._length--; return deletedNode; } // 3rd use-case: any other node is removed while (count < position) { beforeNodeToDelete = currentNode; nodeToDelete = currentNode.next; count++; } beforeNodeToDelete.next = nodeToDelete.next; deletedNode = nodeToDelete; nodeToDelete = null; this._length--; return deletedNode; };從單鏈表到雙鏈表
我們已經(jīng)完整的實現(xiàn)了單鏈表,這真是極好的?,F(xiàn)在可以在一個占用費連續(xù)的空間的鏈表結(jié)構(gòu)中,進行添加、刪除和查找節(jié)點的操作了。
然而現(xiàn)在所有的操作都是從鏈表的起始位置開始,并運行到鏈表的結(jié)尾。換句話說,它們是單向的。
可能在某些情況下我們希望操作是雙向的。如果你考慮了這種可能性,那么你剛才就是描述了一個雙向鏈表。
雙向鏈表雙向鏈表具有單鏈表的所有功能,并將其擴展為在鏈表中可以進行雙向遍歷。 換句話說,我們可從鏈表中第一個節(jié)點遍歷到到最后一個節(jié)點;也可以從最后一個節(jié)點遍歷到第一個節(jié)點。
在本節(jié)中,我們將重點關(guān)注雙向鏈表和單鏈列表之間的差異。
雙向鏈表的操作我們的鏈表將包括兩個構(gòu)造函數(shù):Node和DoublyList??纯此麄兪窃鯓舆\作的。
Nodedata 存儲數(shù)據(jù)。
next 指向鏈表中下一個節(jié)點的指針。
previous 指向鏈表中前一個節(jié)點的指針。
DoublyList_length 保存鏈表中節(jié)點的個數(shù)
head 指定一個節(jié)點作為鏈表的頭節(jié)點
tail 指定一個節(jié)點作為鏈表的尾節(jié)點
add(value) 向鏈表中添加一個節(jié)點
searchNodeAt(position) 找到在列表中指定位置 n 上的節(jié)點
remove(position) 刪除鏈表中指定位置上的節(jié)點
雙向鏈表的實現(xiàn)現(xiàn)在開始寫代碼!
在實現(xiàn)中,將會創(chuàng)建一個名為Node的構(gòu)造函數(shù):
function Node(value) { this.data = value; this.previous = null; this.next = null; }
想要實現(xiàn)雙向鏈表的雙向遍歷,我們需要指向鏈表兩個方向的屬性。這些屬性被命名為previous和next。
接下來,我們需要實現(xiàn)DoublyList并添加三個屬性:_length,head和tail。
與單鏈表不同,雙向鏈表包含對鏈表開頭和結(jié)尾節(jié)點的引用。 由于DoublyList剛被實例化時并不包含任何節(jié)點,所以head和tail的默認(rèn)值都被設(shè)置為null。
function DoublyList() { this._length = 0; this.head = null; this.tail = null; }雙向鏈表的方法
接下來我們討論以下方法:add(value), remove(position), 和 searchNodeAt(position)。所有這些方法都用于單鏈表; 然而,它們必須備重寫為可以雙向遍歷。
方法1/3 add(value)DoublyList.prototype.add = function(value) { var node = new Node(value); if (this._length) { this.tail.next = node; node.previous = this.tail; this.tail = node; } else { this.head = node; this.tail = node; } this._length++; return node; };
在這個方法中,存在兩種可能。首先,如果鏈表是空的,則給它的head 和tail分配節(jié)點。其次,如果鏈表中已經(jīng)存在節(jié)點,則查找鏈表的尾部并把心節(jié)點分配給tail.next;同樣,我們需要配置新的尾部以供進行雙向遍歷。換句話說,我們需要把tail.previous設(shè)置為原來的尾部。
方法2/3 searchNodeAt(position)searchNodeAt(position)的實現(xiàn)與單鏈表相同。 如果你忘記了如何實現(xiàn)它,請通過下面的代碼回憶:
DoublyList.prototype.searchNodeAt = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: "Failure: non-existent node in this list."}; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: a valid position while (count < position) { currentNode = currentNode.next; count++; } return currentNode; };方法3/3 remove(position)
理解這個方法是最具挑戰(zhàn)性的。我先寫出代碼,然后再解釋它。
DoublyList.prototype.remove = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: "Failure: non-existent node in this list."}, beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: the first node is removed if (position === 1) { this.head = currentNode.next; // 2nd use-case: there is a second node if (!this.head) { this.head.previous = null; // 2nd use-case: there is no second node } else { this.tail = null; } // 3rd use-case: the last node is removed } else if (position === this._length) { this.tail = this.tail.previous; this.tail.next = null; // 4th use-case: a middle node is removed } else { while (count < position) { currentNode = currentNode.next; count++; } beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; } this._length--; return message.success; };
remove(position) 處理以下四種情況:
如果remove(position)的參數(shù)傳遞的位置存在, 將會拋出一個錯誤。
如果remove(position)的參數(shù)傳遞的位置是鏈表的第一個節(jié)點(head),將把head賦值給deletedNode ,然后把head重新分配到鏈表中的下一個節(jié)點。 此時,我們必須考慮鏈表中否存在多個節(jié)點。 如果答案為否,頭部將被分配為null,之后進入if-else語句的if部分。 在if的代碼中,還必須將tail設(shè)置為null —— 換句話說,我們返回到一個空的雙向鏈表的初始狀態(tài)。如果刪除列表中的第一個節(jié)點,并且鏈表中存在多個節(jié)點,那么我們輸入if-else語句的else部分。 在這種情況下,我們必須正確地將head的previous屬性設(shè)置為null —— 在鏈表的頭前面是沒有節(jié)點的。
如果remove(position)的參數(shù)傳遞的位置是鏈表的尾部,首先把tail賦值給deletedNode,然后tail被重新賦值為尾部之前的那個節(jié)點,最后新尾部后面沒有其他節(jié)點,需要將其next值設(shè)置為null。
這里發(fā)生了很多事情,所以我將重點關(guān)注邏輯,而不是每一行代碼。 一旦CurrentNode指向的節(jié)點是將要被remove(position)刪除的節(jié)點時,就退出while循環(huán)。這時我們把nodeToDelete之后的節(jié)點重新賦值給beforeNodeToDelete.next。相應(yīng)的,
把nodeToDelete之前的節(jié)點重新賦值給afterNodeToDelete.previous?!獡Q句話說,我們把指向已刪除節(jié)點的指針,改為指向正確的節(jié)點。最后,把nodeToDelete 賦值為null。
最后,把鏈表的長度減1,返回deletedNode。
雙向鏈表的完整實現(xiàn)function Node(value) { this.data = value; this.previous = null; this.next = null; } function DoublyList() { this._length = 0; this.head = null; this.tail = null; } DoublyList.prototype.add = function(value) { var node = new Node(value); if (this._length) { this.tail.next = node; node.previous = this.tail; this.tail = node; } else { this.head = node; this.tail = node; } this._length++; return node; }; DoublyList.prototype.searchNodeAt = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: "Failure: non-existent node in this list."}; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: a valid position while (count < position) { currentNode = currentNode.next; count++; } return currentNode; }; DoublyList.prototype.remove = function(position) { var currentNode = this.head, length = this._length, count = 1, message = {failure: "Failure: non-existent node in this list."}, beforeNodeToDelete = null, nodeToDelete = null, deletedNode = null; // 1st use-case: an invalid position if (length === 0 || position < 1 || position > length) { throw new Error(message.failure); } // 2nd use-case: the first node is removed if (position === 1) { this.head = currentNode.next; // 2nd use-case: there is a second node if (!this.head) { this.head.previous = null; // 2nd use-case: there is no second node } else { this.tail = null; } // 3rd use-case: the last node is removed } else if (position === this._length) { this.tail = this.tail.previous; this.tail.next = null; // 4th use-case: a middle node is removed } else { while (count < position) { currentNode = currentNode.next; count++; } beforeNodeToDelete = currentNode.previous; nodeToDelete = currentNode; afterNodeToDelete = currentNode.next; beforeNodeToDelete.next = afterNodeToDelete; afterNodeToDelete.previous = beforeNodeToDelete; deletedNode = nodeToDelete; nodeToDelete = null; } this._length--; return message.success; };總結(jié)
本文中已經(jīng)介紹了很多信息。 如果其中任何地方看起來令人困惑,就再讀一遍并查看代碼。如果它最終對你有所幫助,我會感到自豪。你剛剛揭開了一個單鏈表和雙向鏈表的秘密,可以把這些數(shù)據(jù)結(jié)構(gòu)添加到自己的編碼工具彈藥庫中!
歡迎掃描二維碼關(guān)注公眾號,每天推送我翻譯的技術(shù)文章。
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://systransis.cn/yun/84362.html
摘要:創(chuàng)建雙向鏈表創(chuàng)建節(jié)點繼承添加前繼指針初始化雙向鏈表對鏈表最后一個元素進行引用插入操作尾插法任意位置添加元素刪除操作刪除特定位置的元素查詢操作查詢元素的位置查詢尾部元素修改操作清空雙向鏈表雙向鏈表對象轉(zhuǎn)為字符串 線性表 (List):零個或者多個數(shù)據(jù)元素的有限序列。線性表是一個序列,具有一對一的關(guān)系,而不能具備一對多的關(guān)系。線性表要求有限性,數(shù)據(jù)類型也要相同。本文參考的主要是大話數(shù)據(jù)結(jié)構(gòu)...
摘要:實現(xiàn)移除給定的元素要移除的元素返回值表示移除成功方法說明移除單向鏈表中某個位置的元素。的前端樂園原文鏈接寒假前端學(xué)習(xí)學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法二鏈表 本系列的第一篇文章: 學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法(一),棧與隊列第二篇文章:學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法(二):鏈表第三篇文章:學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法(三):集合第四篇文章:學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與...
摘要:循環(huán)鏈表可以像單向鏈表引用,也可以像雙向鏈表有雙向引用。以下就以如何創(chuàng)建棧數(shù)據(jù)結(jié)構(gòu)為例。 循環(huán)鏈表可以像單向鏈表引用,也可以像雙向鏈表有雙向引用。性能上也跟雙向鏈表差不多,如果position大于length/2,那就可以從尾部開始迭代,可以減少迭代的元素。唯一的區(qū)別在于最后一個元素指向下一個元素的指針(tail.next)不是undefine,而是第一個元素(head)。接下來來看一...
摘要:鏈表鏈表存儲有序的元素集合,但不同于數(shù)組,鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。鏈表又包括單向鏈表和雙向鏈表雙向鏈表雙向鏈表與單向鏈表很是相像。但在雙向鏈表中,還有指向上一個節(jié)點的鏈接,是雙向的。 鏈表 鏈表存儲有序的元素集合,但不同于數(shù)組,鏈表中的元素在內(nèi)存中并不是連續(xù)放置的。每個元素由一個存儲元素本事的節(jié)點和一個指向下一個元素的引用組成。相對于傳統(tǒng)的數(shù)組,鏈表的一個好處在于,添加或...
2017-07-28 前端日報 精選 React的新引擎—React Fiber是什么?Chromeless 讓 Chrome 自動化變得簡單【譯】JavaScript屬性名稱中的隱藏信息前端測試框架 JestES6中的JavaScript工廠函數(shù)Why Composition is Harder with ClassesGET READY: A NEW V8 IS COMING, NODE.JS...
閱讀 2992·2023-04-26 01:32
閱讀 1589·2021-09-13 10:37
閱讀 2333·2019-08-30 15:56
閱讀 1722·2019-08-30 14:00
閱讀 3105·2019-08-30 12:44
閱讀 1996·2019-08-26 12:20
閱讀 1105·2019-08-23 16:29
閱讀 3275·2019-08-23 14:44