理解JavaScript中的數(shù)據(jù)結(jié)構(gòu)(鏈表)
對于 JS 初學者，理解鏈表可能是一項比較困難的任務，因為 JS 沒有提供內(nèi)置的鏈表。在像 JS 這樣的高級語言中，我們需要從頭開始實現(xiàn)此數(shù)據(jù)結(jié)構(gòu)，如果你不熟悉此數(shù)據(jù)結(jié)構(gòu)的工作方式，則實現(xiàn)部分會變得更加困難 ?。
在本文中，我們將討論如何將鏈表存儲在數(shù)據(jù)庫中，實現(xiàn)鏈表的添加和刪除，查找以及反轉(zhuǎn)鏈表等操作。在實現(xiàn)鏈表之前，需要知道相比數(shù)組和對象，鏈表的優(yōu)點是什么。
我們知道，數(shù)組中的元素以索引編號和順序存儲在數(shù)據(jù)庫中：
在使用數(shù)組時，在開始或特定索引處添加/刪除元素這樣的操作可能是一項性能較低的任務，因為我們必須移動所有其他元素的索引，造成這種原因是由數(shù)組的編號索引特性導致的。
使用對象可以解決上述問題。由于在對象中，元素存儲位置是隨機的，因此，在執(zhí)行諸如在開始處或特定索引處添加/刪除元素之類的操作時，無需移動元素的索引：
盡管在對象中添加和刪除元素速度很快，但是從上圖可以看出，在進行迭代操作時，對象并不是最佳選擇，因為對象的元素存儲在隨機位置。因此，迭代操作可能需要很長時間。這是鏈表引出的原因。
那么什么是鏈表呢 ?
從名字本身可以看出它是一個以某種方式鏈表。那么它是如何鏈接的，列表包含什么呢?
鏈表由具有兩個屬性的節(jié)點組成：數(shù)據(jù)和指針。
節(jié)點內(nèi)的指針指向列表中的下一個節(jié)點。鏈表中的第一個節(jié)點稱為head。為了更好地理解，讓我們看一下描述鏈表圖示：
從上圖可以看出，每個節(jié)點都有兩個屬性，data和pointer。指針指向列表中的下一個節(jié)點，最后一個節(jié)點的指針指向null，上圖是一個單鏈表 ?。
鏈表和對象時有很大的不同。在鏈表中，每個節(jié)點都通過指針(pointer)連接到下一個節(jié)點。因此，我們在鏈表的每個節(jié)點之間都有連接，而在對象中，鍵值對是隨機存儲的，彼此之間沒有連接。
本文由小智翻譯，歡迎關(guān)注《大遷世界》
接著，我們實現(xiàn)一個存儲整數(shù)的鏈表。由于 JS 不提供內(nèi)置的鏈表支持，因此我們將使用對象和類來實現(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)建了兩個類，一個用于來鏈表本身，一個是節(jié)點本身。如我們所討論的，每個節(jié)點將具有兩個屬性，一個值和一個指針(對應 next 字段)。
LinkedList類包含三個屬性，head(初始值為null)，用于存儲鏈表的最后一個節(jié)點的tail(也指向null)和用于保存鏈表長度的length屬性。接著，我們來實現(xiàn)里面的方法 ?。
append (按順序添加值)
這個函數(shù)將一個節(jié)點添加到鏈表的末尾。為了實現(xiàn)這個函數(shù)，我們需要理解它需要執(zhí)行的一些操作：
從上圖中，我們可以通過以下方式實現(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++
- }
簡單的對 append 方法解釋一下 ?：
- const linkedList1 = new LinkedList()
- linkedList1.append(2)
檢查head是否指向null，此時的head指向null，因此我們創(chuàng)建一個新對象，并將新對象分配給head和tail:
- let node = new Node(2)
- this.head = newNode
- this.tail = newNode
現(xiàn)在，head 和 tail 都指向同一個對象，這一點很重要，要記住。
接著，我們再向鏈表添加兩個值：
- linkedList1.append(3)
- linkedList1.append(4)
現(xiàn)在，head 不指向null，所以我們進入append函數(shù)的else分支：
- this.tail.next = node
由于head 和tail 都指向同一個對象，tail的變化都會導致head對象的變化，這是JS 中對象的工作方式。在JavaScript中，對象是通過引用傳遞的，因此 head 和tail都指向存儲對象的相同地址空間。上面這行代碼相當于
- this.head.next = node;
下一行：
- this.tail = node
現(xiàn)在，在執(zhí)行完上面的代碼行之后，this.head.next和this.tail指向同一對象，因此，每當我們添加新節(jié)點時，head對象都會自動更新。
執(zhí)行三次append之后，linkedList1 的結(jié)構(gòu)應該是這樣的：
- head: {value: 2 , next: {value: 3, next: {value: 4,next: null}}}
- tail : {value: 4, next: null}
- length:3
從上面的代碼中我們可以看到，鏈表的append函數(shù)的復雜度是O(1)，因為我們既不需要移動索引，也不需要遍歷鏈表。
我們來看下一個函數(shù) ?
prepend (將值添加到鏈表的開頭)
為了實現(xiàn)此函數(shù)，我們使用Node類創(chuàng)建一個新節(jié)點，并將該新節(jié)點的下一個對象指向鏈表的head 。接下來，我們將新節(jié)點分配給鏈表的head：
與append函數(shù)一樣，這個函數(shù)的復雜度也是O(1)。
- prepend (value) {
- const node = new Node(value)
- node.next = this.head
- this.head = node
- this.length++
就像append函數(shù)一樣，此函數(shù)的復雜度也為O(1)。
insert (在特定索引處添加值)
在實現(xiàn)此函數(shù)之前，我們先看看它的一個轉(zhuǎn)化過程。因此，出于理解目的，我們先創(chuàng)建一個值很少的鏈表，然后可視化insert函數(shù)。insert 函數(shù)接受兩個參數(shù)，值和索引:
- let linkedList2 = new LinkedList()
- linkedList2.append(23)
- linkedList2.append(89)
- linkedList2.append(12)
- linkedList2.append(3)
- linkedList2.insert(45,2)
第1步：
遍歷鏈表，直到到達index-1位置:
第2步：
將索引為1的節(jié)點的指針(在本例中為89)分配給新節(jié)點(在本例中為45)：
第3步：
將新節(jié)點(45)的 next 指向給下一個節(jié)點(12)
這就是執(zhí)行插入操作的方式。通過以上可視化，我們觀察到需要在index-1位置和index位置找到節(jié)點，以便可以在它們之間插入新節(jié)點。在代碼中實現(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++
- }
簡單分析一下上面的函數(shù)：
如果index的值大于或等于length屬性，則將操作移交給append函數(shù)。對于 else 分支，我們使用 Node 類創(chuàng)建一個新節(jié)點，接下來觀察一個新函數(shù)getPrevNextNodes()，通過該函數(shù)我們可以接收prevNode和nextNode的值。getPrevNextNodes函數(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
- }
- }
通過遍歷鏈表返回在index-1位置和index位置的節(jié)點，并將prevNode的next屬性指向新節(jié)點，并將新節(jié)點的next屬性指向nextNode。
鏈表的插入操作的復雜度為 O(n)，因為我們必須遍歷鏈表并在index-1和 index 位置搜索節(jié)點。盡管復雜度為O(n)，但我們發(fā)現(xiàn)此插入操作比對數(shù)組的插入操作快得多，在數(shù)組中，我們必須將所有元素的索引移到特定索引之后，但是在鏈接中，我們僅操縱 index-1 和index 位置的節(jié)點的下一個屬性。
remove (刪除特定索引處的元素)
實現(xiàn)了插入操作之后，刪除操作就比較容易理解，因為它幾乎與插入操作相同，當我們從getPrevNextNodes函數(shù)獲取prevNode和nextNode值時，我們必須在remove中執(zhí)行以下操作：
- remove(index){
- let {previousNode,currentNode} = this.getNodes(index)
- previousNode.next = currentNode.next
- this.length--
- }
刪除操作的復雜度也為 O(n)，類似于插入操作，鏈表中的刪除操作比數(shù)組中的刪除操作要快。
reverse (反轉(zhuǎn)鏈表)
雖然看起來很簡單，但反轉(zhuǎn)鏈表常常是實現(xiàn)起來最令人困惑的操作，因此，在面試中會經(jīng)常詢問這個操作。在實現(xiàn)這個函數(shù)之前，讓我們先把反轉(zhuǎn)鏈表的策略可視化一下。
為了反轉(zhuǎn)鏈表，我們需要跟蹤三個節(jié)點，previousNode，currentNode和nextNode。
考慮下面的鏈表:
- let linkedList2 = new LinkedList()
- linkedList2.append(67)
- linkedList2.append(32)
- linkedList2.append(44)
第一步：
開始，previousNode的值為null，而currentNode的值為head：
第二步：
接下來，我們將nextNode分配給currentNode.next：
第三步：
接下來，我們將currentNode.next屬性指向previousNode：
第三步：
現(xiàn)在，我們將previousNode移至currentNode，將currentNode移至nextNode：
這個過程從步驟2重復操作，一直到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，我們一直在遍歷和移動這些值。最后，我們將previousNode值分配給head。
反向運算的復雜度為O(n)。
查找 (查找特定索引的值)
這個操作很簡單，我們只是遍歷鏈表并返回特定索引處的節(jié)點。這個操作的復雜度也是O(n)。
- lookup(index){
- let counter = 0;
- let currentNode = this.head;
- while(counter < index){
- currentNode = currentNode.next;
- counter++;
- }
- return currentNode;
- }
好了，我們已經(jīng)完成了用javascript實現(xiàn)單個鏈表的基本操作。單鏈表和雙鏈表的區(qū)別在于，雙鏈表的節(jié)點具有指向前一個節(jié)點和下一個節(jié)點的指針。
總結(jié)
鏈表為我們提供了快速的append(末尾添加元素)和prepend(開頭添加元素)操作。盡管鏈表中的插入操作的復雜度為O(n)，但比數(shù)組的插入操作要快得多。使用數(shù)組時我們面臨的另一個問題是大小復雜性，當使用動態(tài)數(shù)組時，在添加元素時，我們必須將整個數(shù)組復制到另一個地址空間，然后添加元素，而在鏈表中，我們不需要 面對這樣的問題。
在使用對象時，我們面臨的問題是元素在內(nèi)存中的隨機位置，而在鏈表中，節(jié)點是通過指針相互連接的，指針提供了一定的順序。
我是小智，我們下期見!
作者：Vivek Bisht 譯者：前端小智 來源：soshace
原文：https://blog.soshace.com/understanding-data-structures-in-javascript-linked-lists/
本文轉(zhuǎn)載自微信公眾號「大遷世界」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系大遷世界公眾號。
