這篇文章給大家分享的是有關(guān)JS數(shù)據(jù)結(jié)構(gòu)之鏈表的優(yōu)點(diǎn)是什么的內(nèi)容。小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，一起跟隨小編過(guò)來(lái)看看吧。
讓客戶(hù)滿(mǎn)意是我們工作的目標(biāo)，不斷超越客戶(hù)的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛(ài)。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶(hù)，將通過(guò)不懈努力成為客戶(hù)在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名與空間、虛擬空間、營(yíng)銷(xiāo)軟件、網(wǎng)站建設(shè)、故城網(wǎng)站維護(hù)、網(wǎng)站推廣。在本文中，我們將討論如何將鏈表存儲(chǔ)在數(shù)據(jù)庫(kù)中，實(shí)現(xiàn)鏈表的添加和刪除，查找以及反轉(zhuǎn)鏈表等操作。 在實(shí)現(xiàn)鏈表之前，需要知道相比數(shù)組和對(duì)象，鏈表的優(yōu)點(diǎn)是什么。
我們知道，數(shù)組中的元素以索引編號(hào)和順序存儲(chǔ)在數(shù)據(jù)庫(kù)中：
在使用數(shù)組時(shí)，在開(kāi)始或特定索引處添加/刪除元素這樣的操作可能是一項(xiàng)性能較低的任務(wù)，因?yàn)槲覀儽仨氁苿?dòng)所有其他元素的索引，造成這種原因是由數(shù)組的編號(hào)索引特性導(dǎo)致的。
使用對(duì)象可以解決上述問(wèn)題。 由于在對(duì)象中，元素存儲(chǔ)位置是隨機(jī)的，因此，在執(zhí)行諸如在開(kāi)始處或特定索引處添加/刪除元素之類(lèi)的操作時(shí)，無(wú)需移動(dòng)元素的索引：
盡管在對(duì)象中添加和刪除元素速度很快，但是從上圖可以看出，在進(jìn)行迭代操作時(shí)，對(duì)象并不是很好選擇，因?yàn)閷?duì)象的元素存儲(chǔ)在隨機(jī)位置。 因此，迭代操作可能需要很長(zhǎng)時(shí)間。 這是鏈表引出的原因。
那么什么是鏈表呢 ?
從名字本身可以看出它是一個(gè)以某種方式鏈表。 那么它是如何鏈接的，列表包含什么呢？
鏈表由具有兩個(gè)屬性的節(jié)點(diǎn)組成：數(shù)據(jù)和指針。
節(jié)點(diǎn)內(nèi)的指針指向列表中的下一個(gè)節(jié)點(diǎn)。 鏈表中的第一個(gè)節(jié)點(diǎn)稱(chēng)為head。 為了更好地理解，讓我們看一下描述鏈表圖示：
從上圖可以看出，每個(gè)節(jié)點(diǎn)都有兩個(gè)屬性，data和pointer。 指針指向列表中的下一個(gè)節(jié)點(diǎn)，最后一個(gè)節(jié)點(diǎn)的指針指向null，上圖是一個(gè)單鏈表 ?。
鏈表和對(duì)象時(shí)有很大的不同。 在鏈表中，每個(gè)節(jié)點(diǎn)都通過(guò)指針(pointer)連接到下一個(gè)節(jié)點(diǎn)。 因此，我們?cè)阪湵淼拿總€(gè)節(jié)點(diǎn)之間都有連接，而在對(duì)象中，鍵值對(duì)是隨機(jī)存儲(chǔ)的，彼此之間沒(méi)有連接。
接著，我們實(shí)現(xiàn)一個(gè)存儲(chǔ)整數(shù)的鏈表。 由于 JS 不提供內(nèi)置的鏈表支持，因此我們將使用對(duì)象和類(lèi)來(lái)實(shí)現(xiàn)鏈表 ?
重慶分公司
重慶分公司
class Node {
constructor (value) {
this.value = value
this.next = null
}
}
class LinkedList {
constructor () {
this.head = null
this.tail = this.head
this.length = 0
}
append (value) {
}
prepend (value) {
}
insert (value, index) {
}
lookup (index) {
}
remove (index) {
}
reverse () {
}
}在上面的代碼中，我們創(chuàng)建了兩個(gè)類(lèi)，一個(gè)用于來(lái)鏈表本身，一個(gè)是節(jié)點(diǎn)本身。 如我們所討論的，每個(gè)節(jié)點(diǎn)將具有兩個(gè)屬性，一個(gè)值和一個(gè)指針(對(duì)應(yīng)next 字段)。
LinkedList類(lèi)包含三個(gè)屬性，head(初始值為null)，用于存儲(chǔ)鏈表的最后一個(gè)節(jié)點(diǎn)的tail(也指向null)和用于保存鏈表長(zhǎng)度的length屬性。接著，我們來(lái)實(shí)現(xiàn)里面的方法 ?。
這個(gè)函數(shù)將一個(gè)節(jié)點(diǎn)添加到鏈表的末尾。為了實(shí)現(xiàn)這個(gè)函數(shù)，我們需要理解它需要執(zhí)行的一些操作：
從上圖中，我們可以通過(guò)以下方式實(shí)現(xiàn)append函數(shù)：
append (value) {
const newNode = new Node(value)
if (!this.head) {
this.head = newNode
this.tail = newNode
} else {
this.tail.next = newNode
this.tail = newNode
}
this.length++
}簡(jiǎn)單的對(duì)append 方法解釋一下 ?：
const linkedList1 = new LinkedList() linkedList1.append(2)
檢查head是否指向null，此時(shí)的head指向null，因此我們創(chuàng)建一個(gè)新對(duì)象，并將新對(duì)象分配給head和tail:
let node = new Node(2) this.head = newNode this.tail = newNode
現(xiàn)在，head 和tail 都指向同一個(gè)對(duì)象，這一點(diǎn)很重要，要記住。
接著，我們?cè)傧蜴湵硖砑觾蓚€(gè)值：
linkedList1.append(3) linkedList1.append(4)
現(xiàn)在，head 不指向null，所以我們進(jìn)入append函數(shù)的else分支：
this.tail.next = node
由于head 和tail 都指向同一個(gè)對(duì)象，tail的變化都會(huì)導(dǎo)致head對(duì)象的變化，這是JS 中對(duì)象的工作方式。在JavaScript中，對(duì)象是通過(guò)引用傳遞的，因此head 和tail都指向存儲(chǔ)對(duì)象的相同地址空間。上面這行代碼相當(dāng)于
this.head.next = node;
下一行：
this.tail = node
現(xiàn)在，在執(zhí)行完上面的代碼行之后，this.head.next和this.tail指向同一對(duì)象，因此，每當(dāng)我們添加新節(jié)點(diǎn)時(shí)，head對(duì)象都會(huì)自動(dòng)更新。
執(zhí)行三次append之后，linkedList1 的結(jié)構(gòu)應(yīng)該是這樣的：
head: {value: 2 , next: {value: 3, next: {value: 4,next: null}}}
tail : {value: 4, next: null}
length:3從上面的代碼中我們可以看到，鏈表的append函數(shù)的復(fù)雜度是O(1)，因?yàn)槲覀兗炔恍枰苿?dòng)索引，也不需要遍歷鏈表。
我們來(lái)看下一個(gè)函數(shù) ?
為了實(shí)現(xiàn)此函數(shù)，我們使用Node類(lèi)創(chuàng)建一個(gè)新節(jié)點(diǎn)，并將該新節(jié)點(diǎn)的下一個(gè)對(duì)象指向鏈表的head 。 接下來(lái)，我們將新節(jié)點(diǎn)分配給鏈表的head：
與append函數(shù)一樣，這個(gè)函數(shù)的復(fù)雜度也是O(1)。
prepend (value) {
const node = new Node(value)
node.next = this.head
this.head = node
this.length++
}就像append函數(shù)一樣，此函數(shù)的復(fù)雜度也為O(1)。
在實(shí)現(xiàn)此函數(shù)之前，我們先看看它的一個(gè)轉(zhuǎn)化過(guò)程。因此，出于理解目的，我們先創(chuàng)建一個(gè)值很少的鏈表，然后可視化insert函數(shù)。insert 函數(shù)接受兩個(gè)參數(shù)，值和索引:
let linkedList2 = new LinkedList() linkedList2.append(23) linkedList2.append(89) linkedList2.append(12) linkedList2.append(3)
linkedList2.insert(45,2)
第1步：
遍歷鏈表，直到到達(dá)index-1位置:
第2步：
將索引為1的節(jié)點(diǎn)的指針（在本例中為89）分配給新節(jié)點(diǎn)（在本例中為45）：
第3步：
將新節(jié)點(diǎn)(45)的next 指向給下一個(gè)節(jié)點(diǎn)(12)
這就是執(zhí)行插入操作的方式。 通過(guò)以上可視化，我們觀(guān)察到需要在index-1位置和index位置找到節(jié)點(diǎn)，以便可以在它們之間插入新節(jié)點(diǎn)。 在代碼中實(shí)現(xiàn)：
insert (value, index) {
if (index >= this.length) {
this.append(value)
}
const node = new Node(value)
const { prevNode, nextNode } = thisg.getPrevNextNodes(index)
prevNode.next = node
node.next = nextNode
this.length++
}簡(jiǎn)單分析一下上面的函數(shù)：
如果index的值大于或等于length屬性，則將操作移交給append函數(shù)。 對(duì)于else 分支，我們使用 Node 類(lèi)創(chuàng)建一個(gè)新節(jié)點(diǎn)，接下來(lái)觀(guān)察一個(gè)新函數(shù)getPrevNextNodes()，通過(guò)該函數(shù)我們可以接收prevNode和nextNode的值。getPrevNextNodes函數(shù)的實(shí)現(xiàn)如下：
getPrevNextNodes(index){
let count = 0;
let prevNode = this.head;
let nextNode = prevNode.next;
while(count < index - 1){
prevNode = prevNode.next;
nextNode = prevNode.next;
count++;
}
return {
prevNode,
nextNode
}
}通過(guò)遍歷鏈表返回在index-1位置和index位置的節(jié)點(diǎn)，并將prevNode的next屬性指向新節(jié)點(diǎn)，并將新節(jié)點(diǎn)的next屬性指向nextNode。
鏈表的插入操作的復(fù)雜度為O(n)，因?yàn)槲覀儽仨毐闅v鏈表并在index-1和index 位置搜索節(jié)點(diǎn)。 盡管復(fù)雜度為O(n)，但我們發(fā)現(xiàn)此插入操作比對(duì)數(shù)組的插入操作快得多，在數(shù)組中，我們必須將所有元素的索引移到特定索引之后，但是在鏈接中，我們僅操縱index-1 和index 位置的節(jié)點(diǎn)的下一個(gè)屬性。
實(shí)現(xiàn)了插入操作之后，刪除操作就比較容易理解，因?yàn)樗鼛缀跖c插入操作相同，當(dāng)我們從getPrevNextNodes函數(shù)獲取prevNode和nextNode值時(shí)，我們必須在remove中執(zhí)行以下操作：
remove(index){
let {previousNode,currentNode} = this.getNodes(index)
previousNode.next = currentNode.next
this.length--
}刪除操作的復(fù)雜度也為O(n)，類(lèi)似于插入操作，鏈表中的刪除操作比數(shù)組中的刪除操作要快。
雖然看起來(lái)很簡(jiǎn)單，但反轉(zhuǎn)鏈表常常是實(shí)現(xiàn)起來(lái)最令人困惑的操作，因此，在面試中會(huì)經(jīng)常詢(xún)問(wèn)這個(gè)操作。在實(shí)現(xiàn)這個(gè)函數(shù)之前，讓我們先把反轉(zhuǎn)鏈表的策略可視化一下。
為了反轉(zhuǎn)鏈表，我們需要跟蹤三個(gè)節(jié)點(diǎn)，previousNode，currentNode和nextNode。
考慮下面的鏈表:
let linkedList2 = new LinkedList() linkedList2.append(67) linkedList2.append(32) linkedList2.append(44)
第一步：
開(kāi)始，previousNode的值為null，而currentNode的值為head：
第二步：
接下來(lái)，我們將nextNode分配給currentNode.next：
第三步：
接下來(lái)，我們將currentNode.next屬性指向previousNode：
第三步：
現(xiàn)在，我們將previousNode移至currentNode，將currentNode移至nextNode：
這個(gè)過(guò)程從步驟2重復(fù)操作，一直到currentNode 等于null。
reverse (){
let previousNode = null
let currentNode = this.head
while(currentNode !== null) {
let nextNode = currentNode.next
currentNode.next = previousNode
previousNode = currentNode
currentNode = nextNode
}
this.head = previousNode
}就像我們看到的一樣，直到currentNode === null，我們一直在遍歷和移動(dòng)這些值。 最后，我們將previousNode值分配給head。
反向運(yùn)算的復(fù)雜度為O(n)。
這個(gè)操作很簡(jiǎn)單，我們只是遍歷鏈表并返回特定索引處的節(jié)點(diǎn)。這個(gè)操作的復(fù)雜度也是O(n)。
lookup(index){
let counter = 0;
let currentNode = this.head;
while(counter < index){
currentNode = currentNode.next;
counter++;
}
return currentNode;
}好了，我們已經(jīng)完成了用javascript實(shí)現(xiàn)單個(gè)鏈表的基本操作。單鏈表和雙鏈表的區(qū)別在于，雙鏈表的節(jié)點(diǎn)具有指向前一個(gè)節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)的指針。
鏈表為我們提供了快速的append（末尾添加元素）和prepend（開(kāi)頭添加元素）操作。 盡管鏈表中的插入操作的復(fù)雜度為O(n)，但比數(shù)組的插入操作要快得多。 使用數(shù)組時(shí)我們面臨的另一個(gè)問(wèn)題是大小復(fù)雜性，當(dāng)使用動(dòng)態(tài)數(shù)組時(shí)，在添加元素時(shí)，我們必須將整個(gè)數(shù)組復(fù)制到另一個(gè)地址空間，然后添加元素，而在鏈表中，我們不需要 面對(duì)這樣的問(wèn)題。
在使用對(duì)象時(shí)，我們面臨的問(wèn)題是元素在內(nèi)存中的隨機(jī)位置，而在鏈表中，節(jié)點(diǎn)是通過(guò)指針相互連接的，指針提供了一定的順序。
感謝各位的閱讀！關(guān)于“JS數(shù)據(jù)結(jié)構(gòu)之鏈表的優(yōu)點(diǎn)是什么”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！
