常用數據結構的 JavaScript 實現代碼[每日前端夜話0xED]

  • 2019 年 11 月 23 日
  • 筆記

正文共：4074 字

預計閱讀時間：13 分鐘

作者：Paul Ryan

翻譯：瘋狂的技術宅

來源：logrocket

我們要談論的是什麼？

在 JavaScript 中數據結構通常總是被忽略，或者接觸得不多。但是對於許多大廠而言，一般都需要你深刻了解如何管理數據。掌握數據結構也能夠在解決問題時為你的工作提供幫助。

在本文中，我們將要討論並實現的數據結構是：

  • 棧
  • 隊列
  • 鏈表
  • 哈希表
  • 樹

棧

第一個數據結構是棧。它與隊列非常相似，你之前可能聽說過調用棧，這是 JavaScript 用於處理事件的方法。

棧看起來像這樣：

棧的可視化表示

最後一個存入棧里的項目將是第一個被移除的項目。這被稱為後進先出（LIFO）。Web 瀏覽器中的後退按鈕就是一個很好的例子：將你查看的每個頁面添加到棧中，當你單擊「返回」時，將從棧中彈出當前頁面（最後添加的頁面）。

理論足夠多了。接下來看一些代碼：

 1class Stack {   2  constructor() {   3    // 創建棧結構，這是一個空對象   4    this.stack = {}   5  }   6  // 把一個值壓入棧的頂部   7  push(value) {   8   9  }  10  // 彈出棧頂的值並返回  11  pop() {  12  13  }  14  15  // 讀取棧中的最後一個值，但是不刪除  16  peek() {  17  18  }  19}

我已經對上面的代碼進行了注釋，現在咱們一起對其進行實現。第一種方法是 push。

先思考一下需要這個方法做的事情：

  • 我們需要接受一個值
  • 然後將該值添加到棧的頂部
  • 還應該跟蹤棧的長度，以便知道棧的索引

如果你能夠先自己嘗試一下，那就太好了，完整的 push 方法實現如下：

 1class Stack {   2  constructor() {   3    this._storage = {};   4    this._length = 0; // 這是棧的大小   5  }   6   7  push(value) {   8    // 將值添加到棧頂   9    this._storage[this._length] = value;  10    // 因為增加了一個值，所以也應該將長度加1  11    this._length++;  12  }  13  /// .....  14}

我敢打賭，這比你想像的要容易。有許多類似這樣的結構，它們聽起來比實際上要複雜得多。

現在是 pop 方法。pop 方法的目標是刪除最後一個添加到棧中的值，然後返回它。如果可以的話，請先自己嘗試實現：

 1class Stack {   2  constructor() {   3    this._storage = {};   4    this._length = 0;   5  }   6   7  pop() {   8    // we first get the last val so we have it to return   9    const lastVal = this._storage[--this._length]  10    // now remove the item which is the length - 1  11    delete this._storage[--this._length]  12    // decrement the length  13    this._length--;  14    // now return the last value  15    return lastVal  16  }  17}

酷！快要完成了。最後一個是 peek 函數，該函數查看棧中的最後一項。這是最簡單的功能：只需要返回最後一個值。實現是：

 1class Stack {   2  constructor() {   3    this._storage = {};   4    this._length = 0;   5  }   6  /*   7  * Adds a new value at the end of the stack   8  * @param {*} value the value to push   9  */  10  11  peek() {  12    const lastVal = this._storage[--this._length]  13    return lastVal  14  }  15}

所以它與 pop 方法非常相似，但不刪除最後一項。

Yes！第一個數據結構已經實現。接着是隊列，隊列與棧非常相似。

隊列

接下來討論隊列——希望棧在你的腦子仍然記得很清楚，因為它和隊列非常相似。棧和隊列之間的主要區別在於隊列是先進先出（FIFO）。

可以用圖形這樣表示：

隊列的可視化表示

所以兩個主要方法是 enqueue 與 dequeue。數據被添加到隊尾，並從隊首移除。為了更好的理解它，下面開始實現隊列。

核心代碼結構如下所示：

 1class Queue {   2  constructor() {   3    // 與前面類似，我們為數據結構提供了一個對象   4    // 並且還有一個變量來保存長度   5    this.queue = {}   6    this.length = 0   7    // 這是一個跟蹤頭部的新變量   8    this.head = 0   9  }  10  11  enqueue(value) {  12  13  }  14  15  dequeue() {  16  17  }  18  19  peek() {  20  21  }  22}

首先實現 enqueue 方法。其目的是向隊尾添加一個項目。

1enqueue(value) {  2  // 使用 value 參數將 length + head 的鍵添加到對象  3  this.queue[this.length + this.head] = value;  4  this.length++  5}

這是一個非常簡單的方法，可以在隊列的末尾添加一個值，但是你可能會對this.queue[this.length + this.head] = value;感到困惑。

假設隊列看起來像這樣的 {14 : 'randomVal'}。在添加這個內容時，我們希望的下一個值為 15，所以應該是 length(1) + head(14)，即為 15。

下一個要實現的是 dequeue ：

1dequeue() {  2  // 獲取第一個值的引用，以便將其返回  3  const firstVal = this.queue[this.head]  4  // 現在將其從隊列中刪除  5  delete this.queue[this.head]  6  this.length--;  7  // 最終增加我們的頭成為下一個節點  8  this.head++;  9}

最後要實現的是 peek 方法，非常簡單：

1peek() {  2  // 只需要把值返回即可  3  return this.queue[this.head];  4}

隊列實現完畢。

鏈表

先讓我們討論一下強大的鏈表。這比上面的結構要複雜得多。

可能你第一個問題是為什麼要使用鏈表？鏈表主要用於沒有動態大小調整數組的語言。鏈表按順序組織項目，一個項目指向下一個項目。

鏈表中的每個節點都有一個 data 值和一個 next 值。下圖中 5 是 data 值，next 值指向下一個節點，即值為 10 的節點。

在視覺上，它看起來像這樣：

鏈表的可視化表示

在一個對象中，上面的 LinkedList 看起來像下面的樣子

對象中的鏈表

你會看到最後一個值 1 的 next 值為 null，因為這是 LinkedList 的結尾。

那麼該如何實現呢？

讓我們創建一個具有值 1、 2 和 37的 LinkedList。

 1const myLinkedList = {   2    head: {   3        value: 1   4        next: {   5            value: 2   6            next: {   7                value: 37   8                next: null   9            }  10        }  11    }  12};

現在我們知道了該怎樣手動創建 LinkedList，但是還需要編碼實現 LinkedList 的方法。

首先要注意的是，LinkedList 只是一堆嵌套對象！

當構造一個 LinkedList 時，我們需要一個 head 和一個 tail，它們最初都會指向頭部（因為 head 是第一個也是最後一個）。

1class LinkedList {  2  constructor(value) {  3    this.head = {value, next: null}  4    this.tail = this.head  5  }  6}

第一個要實現的方法是 insert ，該方法用來在鏈表的末尾插入一個值。

1// insert 將添加到鏈接列表的末尾  2insert(value) {  3  /* 創建一個節點 */  4  const node = {value, next: null}  5  /* 把 tail 的 next 屬性設置為新節點的引用 */  6  this.tail.next = node;  7  /* 新節點現在是尾節點 */  8  this.tail = node;  9}

上面最混亂的一行可能是 this.tail.next = node。之所以這樣做，是因為當添加一個新節點時，我們還希望當前的 tail 指向新的 node，該節點將成為新的 tail。第一次插入 node 時，頭部的 next 指針將指向新節點，就像在構造函數中那樣，在其中設置了 this.tail = this.head。

你還可以到這個網站來查看圖形化的演示，這將幫你了解插入的過程（按 esc 擺脫煩人的彈出窗口）。

下一個方法是刪除節點。我們首先要決定參數是值（ value） 還是對節點（node）的引用（在面試中，最好先問問面試官）。我們的代碼中傳遞了一個「值」。按值從列表中刪除節點是一個緩慢的過程，因為必須要遍歷整個列表才能找到值。

我這樣做是這樣的：

 1removeNode(val) {   2  /* 從 head 開始 */   3  let currentNode = this.head   4  /* 我們需要保留對上一個節點的引用 */   5  let previousNode   6  /* 當存在一個節點時，意味着沒有到達尾部 */   7  while(currentNode) {   8     /* 如果發現自己想要的那個值，那麼就退出循環 */   9     if(currentNode.value === val) {  10        break;  11     }  12    /* 沒有找到值就將 currentNode 設置為 previousNode */  13    previousNode = currentNode  14    /* 得到下一個節點並將其分配給currentNode  */  15    currentNode = currentNode.next  16  }  17  /* 返回undefined，因為沒有找到具有該值的節點  */  18  if (currentNode=== null) {  19    return false;  20  }  21  22  // 如果節點是 head ，那麼將 head 設置為下一個值  23  頭節點的  24  if (currentNode === this.head) {  25    this.head = this.head.next;  26    return;  27  }  28  /* 通過將節點設置為前面的節點來刪除節點 */  29  previousNode.next = currentNode.next  30}

removeNode 方法使我們對 LinkedList 的工作方式有了很好的了解。

所以再次說明一下，首先將變量 currentNode 設置為 LinkedList 的 head，因為這是第一個節點。然後創建一個名為 previousNode 的佔位符變量，該變量將在 while 循環中使用。從條件 currentNode 開始 while 循環，只要存在 currentNode，就會一直運行。

在 while 循環中第一步是檢查是否有值。如果不是，則將 previousNode 設置為 currentNode，並將 currentNode 設置為列表中的下一個節點。繼續進行此過程，直到找到我需要找的值或遍歷完節點為止。

在 while 循環之後，如果沒有 currentNode，則返回 false，這意味着沒有找到任何節點。如果確實存在一個 currentNode，則檢查的 currentNode 是否為 head。如果是的話就把 LinkedList 的 head 設置為第二個節點，它將成為 head。

最後，如果 currentNode 不是頭，就把 previousNode 設置為指向 currentNode 前面的 node，這將會從對象中刪除 currentNode。

另一個常用的方法（面試官可能還會問你）是 removeTail 。這個方法如其所言，只是去掉了 LinkedList 的尾節點。這比上面的方法容易得多，但工作原理類似。

我建議你先自己嘗試一下，然後再看下面的代碼（為了使其更複雜一點，我們在構造函數中不使用 tail）：

 1removeTail() {   2  let currentNode = this.head;   3  let previousNode;   4  while (currentNode) {   5    /* 尾部是唯一沒有下一個值的節點，所以如果不存在下一個值，那麼該節點就是尾部 */   6    if (!currentNode.next) {   7      break;   8    }   9    // 獲取先前節點的引用  10    previousNode = currentNode;  11    // 移至下一個節點  12    currentNode = currentNode.next;  13  }  14  // 要刪除尾部，將 previousNode.next 設置為 null  15  previousNode.next = null;  16}

這些就是 LinkedList 的一些主要方法。鏈表還有各種方法，但是利用以上學到的知識，你應該能夠自己實現它們。

哈希表

接下來是強大的哈希表。

哈希表是一種實現關聯數組的數據結構，這意味着它把鍵映射到值。JavaScript 對象就是一個「哈希表」，因為它存儲鍵值對。

在視覺上，可以這樣表示：

哈希表的可視化表示

在討論如何實現哈希表之前，需要討論討論哈希函數的重要性。哈希函數的核心概念是它接受任意大小的輸入並返回固定長度的哈希值。

1hashThis('i want to hash this') => 7

哈希函數可能非常複雜或直接。GitHub 上的每個文件都經過了哈希處理，這使得每個文件的查找都非常快。哈希函數背後的核心思想是，給定相同的輸入將返回相同的輸出。

在介紹了哈希功能之後，該討論一下如何實現哈希表了。

將要討論的三個操作是 insert、get最後是 remove。

實現哈希表的核心代碼如下：

 1class HashTable {   2  constructor(size) {   3    // 定義哈希表的大小，將在哈希函數中使用   4    this.size = size;   5    this.storage = [];   6  }   7  insert(key, value) { }   8  get() {}   9  remove() {}  10  // 這是計算散列密鑰的方式  11  myHashingFunction(str, n) {  12    let sum = 0;  13    for (let i = 0; i < str.length; i++) {  14      sum += str.charCodeAt(i) * 3;  15    }  16    return sum % n;  17  }  18}

現在解決第一個方法，即 insert。insert 到哈希表中的代碼如下（為簡單起見，此方法將簡單的處理衝突問題）：

 1insert(key, value) {   2  // 得到數組中的索引   3  const index = this.myHashingFunction(key, this.size);   4  // 處理衝突 - 如果哈希函數為不同的鍵返回相同的索引，   5  // 在複雜的哈希函數中，很可能發生衝突   6  if (!this.storage[index]) {   7    this.storage[index] = [];   8  }   9  // push 新的鍵值對  10  this.storage[index].push([key, value]);  11}

像這樣調用 insert 方法：

1const myHT = new HashTable(5);  2myHT.insert("a", 1);  3myHT.insert("b", 2);

你認為我們的哈希表會是什麼樣的？

哈希表示例代碼

你可以看到鍵值對已插入到表中的索引 1 和 4 處。

現在實現從哈希表中刪除

 1remove(key) {   2    // 首先要獲取 key 的索引，請記住，   3    // 哈希函數將始終為同一 key 返回相同的索引   4    const index = this.myHashingFunction(key, this.size);   5    // 記住我們在一個索引處可以有多個數組（不太可能）   6    let arrayAtIndex = this.storage[index];   7    if (arrayAtIndex) {   8      // 遍歷該索引處的所有數組   9      for (let i = 0; i < arrayAtIndex.length; i++) {  10        // get the pair (a, 1)  11        let pair = arrayAtIndex[i];  12        // 檢查 key 是否與參數 key 匹配  13        if (pair[0] === key) {  14          delete arrayAtIndex[i];  15          // 工作已經完成，所以要退出循環  16          break;  17        }  18      }  19    }  20}

最後是 get 方法。這和 remove 方法一樣，但是這次，我們返回 pair 而不是刪除它。

 1 get(key) {   2    const index = this.myHashingFunction(key, this.size);   3    let arrayAtIndex = this.storage[index];   4    if (arrayAtIndex) {   5      for (let i = 0; i < arrayAtIndex.length; i++) {   6        const pair = arrayAtIndex[i];   7        if (pair[0] === key) {   8          return pair[1];   9        }  10      }  11    }  12  }

我認為不需要執行這個操作，因為它的作用與 remove 方法相同。

你可以認為它並不像最初看起來那樣複雜。這是一種到處使用的數據結構，也是是一個很好理解的結構！

二叉搜索樹

最後一個數據結構是臭名昭著的二叉搜索樹。

在二叉搜索樹中，每個節點具有零個、一個或兩個子節點。左邊的稱為左子節點，右邊的稱為右子節點。在二叉搜索樹中，左側的子項必須小於右側的子項。

你可以像這樣描繪一個二叉搜索樹：

二進制搜索樹的可視化表示

樹的核心類如下：

 1class Tree {   2   constructor(value) {   3     this.root = null   4   }   5   6   add(value) {   7    // 我們將在下面實現   8   }   9  10}

我們還將創建一個 Node 類來代表每個節點。

1class Node {  2  constructor(value, left = null, right = null) {  3    this.value = value;  4    this.left = left;  5    this.right = right;  6  }  7}

下面實現 add 方法。我已經對代碼進行了注釋，但是如果你發現使你感到困惑，請記住，我們要做的只是從根開始並檢查每個節點的 left 和 right。

 1add(value) {   2    // 如果沒有根，那麼就創建一個   3    if (this.root === null) {   4      this.root = new Node(value);   5      return;   6    }   7    let current = this.root;   8    // keep looping   9    while (true) {  10      // 如果當前值大於傳入的值，則向左  11      if (current.value > value) {  12        // 如果存在左子節點，則再次進行循環  13        if (current.left) {  14          current = current.left;  15        } else {  16          current.left = new Node(value);  17          return;  18        }  19      }  20      // 值較小，所以我們走對了  21      else {  22        // 向右  23        // 如果存在左子節點，則再次運行循環  24        if (current.right) {  25          current = current.right;  26        } else {  27          current.right = new Node(value);  28          return;  29        }  30      }  31    }  32}

測試新的 add 方法：

1const t = new Tree();  2t.add(2);  3t.add(5);  4t.add(3);

現在樹看起來是這樣：

二叉搜索樹示例

為了更好的理解，讓我們實現一個檢查樹中是否包含值的方法。

 1contains(value) {   2  // 獲取根節點   3  let current = this.root;   4  // 當存在節點時   5  while (current) {   6    // 檢查當前節點是否為該值   7    if (value === current.value) {   8      return true; // 退出函數   9    }  10    // 通過將我們的值與 current.value 進行比較來決定下一個當前節點  11    // 如果小則往左，否則往右  12    current = value < current.value ? current.left : current.right;  13  }  14  return false;  15}

Add 和 Contains 是二進制搜索樹的兩個核心方法。對這兩種方法的了解可以使你更好地解決日常工作中的問題。

總結

我已經在本文中介紹了很多內容，並且掌握這些知識後在面試中將使你處於有利位置。希望你能夠學到一些東西，並能夠輕鬆地通過技術面試（尤其是討厭的白板面試）。

原文：https://blog.logrocket.com/know-your-javascript-data-structures/

VirMach 便宜 VPS

QNews

QNews