JavaScript如何實現(xiàn)常用數(shù)據(jù)結(jié)構(gòu)

這篇文章將為大家詳細講解有關JavaScript如何實現(xiàn)常用數(shù)據(jù)結(jié)構(gòu)，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。

10年的新華網(wǎng)站建設經(jīng)驗，針對設計、前端、開發(fā)、售后、文案、推廣等六對一服務，響應快，48小時及時工作處理。成都營銷網(wǎng)站建設的優(yōu)勢是能夠根據(jù)用戶設備顯示端的尺寸不同，自動調(diào)整新華建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設計，從而大程度地提升瀏覽體驗。成都創(chuàng)新互聯(lián)公司從事“新華網(wǎng)站設計”,“新華網(wǎng)站推廣”以來，每個客戶項目都認真落實執(zhí)行。

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

在本文中，我們將要討論并實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)是：

• 棧

• 隊列

• 鏈表

• 哈希表

• 樹

棧

第一個數(shù)據(jù)結(jié)構(gòu)是棧。它與隊列非常相似，你之前可能聽說過調(diào)用棧，這是 JavaScript 用于處理事件的方法。

?？雌饋硐襁@樣：

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

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

class Stack {
  constructor() {
    // 創(chuàng)建棧結(jié)構(gòu)，這是一個空對象
    this.stack = {}
  }
  // 把一個值壓入棧的頂部
  push(value) {

  }
  // 彈出棧頂?shù)闹挡⒎祷?
  pop() {

  }

  // 讀取棧中的最后一個值，但是不刪除
  peek() {

  }
}

我已經(jīng)對上面的代碼進行了注釋，現(xiàn)在咱們一起對其進行實現(xiàn)。第一種方法是 push。

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

• 我們需要接受一個值

• 然后將該值添加到棧的頂部

• 還應該跟蹤棧的長度，以便知道棧的索引

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

class Stack {
  constructor() {
    this._storage = {};
    this._length = 0; // 這是棧的大小
  }

  push(value) {
    // 將值添加到棧頂
    this._storage[this._length] = value;
    // 因為增加了一個值，所以也應該將長度加1
    this._length++;
  }
  /// .....
}

我敢打賭，這比你想象的要容易。有許多類似這樣的結(jié)構(gòu)，它們聽起來比實際上要復雜得多。

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

class Stack {
  constructor() {
    this._storage = {};
    this._length = 0;
  }

  pop() {
    // we first get the last val so we have it to return
    const lastVal = this._storage[--this._length]
    // now remove the item which is the length - 1 
    delete this._storage[--this._length]
    // decrement the length
    this._length--;
    // now return the last value
    return lastVal
  }
}

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

class Stack {
  constructor() {
    this._storage = {};
    this._length = 0;
  }
  /*
  * Adds a new value at the end of the stack
  * @param {*} value the value to push
  */

  peek() {
    const lastVal = this._storage[--this._length]
    return lastVal
  }
}

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

Yes！第一個數(shù)據(jù)結(jié)構(gòu)已經(jīng)實現(xiàn)。接著是隊列，隊列與棧非常相似。

隊列

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

可以用圖形這樣表示：

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

核心代碼結(jié)構(gòu)如下所示：

class Queue {
  constructor() {
    // 與前面類似，我們?yōu)閿?shù)據(jù)結(jié)構(gòu)提供了一個對象
    // 并且還有一個變量來保存長度
    this.queue = {}
    this.length = 0
    // 這是一個跟蹤頭部的新變量
    this.head = 0
  }

  enqueue(value) {

  }

  dequeue() {

  }

  peek() {

  }
}

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

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

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

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

下一個要實現(xiàn)的是 dequeue ：

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

最后要實現(xiàn)的是 peek 方法，非常簡單：

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

隊列實現(xiàn)完畢。

鏈表

先讓我們討論一下強大的鏈表。這比上面的結(jié)構(gòu)要復雜得多。

可能你第一個問題是為什么要使用鏈表？鏈表主要用于沒有動態(tài)大小調(diào)整數(shù)組的語言。鏈表按順序組織項目，一個項目指向下一個項目。

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

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

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

你會看到最后一個值 1 的 next 值為 null，因為這是 LinkedList 的結(jié)尾。

那么該如何實現(xiàn)呢？

讓我們創(chuàng)建一個具有值 1、 2 和  37的 LinkedList。

const myLinkedList = {
    head: {
        value: 1
        next: {
            value: 2           
            next: {
                value: 37
                next: null
            }
        }
    }
};

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

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

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

class LinkedList {
  constructor(value) {
    this.head = {value, next: null}
    this.tail = this.head
  }
}

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

// insert 將添加到鏈接列表的末尾
insert(value) {
  /* 創(chuàng)建一個節(jié)點 */
  const node = {value, next: null}
  /* 把 tail 的 next 屬性設置為新節(jié)點的引用 */
  this.tail.next = node;
  /* 新節(jié)點現(xiàn)在是尾節(jié)點 */
  this.tail = node;
}

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

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

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

我這樣做是這樣的：

removeNode(val) {
  /* 從 head 開始 */
  let currentNode = this.head
  /* 我們需要保留對上一個節(jié)點的引用 */
  let previousNode
  /* 當存在一個節(jié)點時，意味著沒有到達尾部 */
  while(currentNode) {
     /* 如果發(fā)現(xiàn)自己想要的那個值，那么就退出循環(huán) */
     if(currentNode.value === val) {
        break;
     }
    /* 沒有找到值就將 currentNode 設置為 previousNode */
    previousNode = currentNode
    /* 得到下一個節(jié)點并將其分配給currentNode  */
    currentNode = currentNode.next
  }
  /* 返回undefined，因為沒有找到具有該值的節(jié)點  */
  if (currentNode=== null) {
    return false;
  }

  // 如果節(jié)點是 head ，那么將 head 設置為下一個值
  頭節(jié)點的
  if (currentNode === this.head) {
    this.head = this.head.next;
    return;
  }
  /* 通過將節(jié)點設置為前面的節(jié)點來刪除節(jié)點 */  
  previousNode.next = currentNode.next
}

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

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

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

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

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

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

我建議你先自己嘗試一下，然后再看下面的代碼（為了使其更復雜一點，我們在構(gòu)造函數(shù)中不使用 tail）：

removeTail() {
  let currentNode = this.head;
  let previousNode;
  while (currentNode) {
    /* 尾部是唯一沒有下一個值的節(jié)點，所以如果不存在下一個值，那么該節(jié)點就是尾部 */
    if (!currentNode.next) {
      break;
    }
    // 獲取先前節(jié)點的引用
    previousNode = currentNode;
    // 移至下一個節(jié)點
    currentNode = currentNode.next;
  }
  // 要刪除尾部，將 previousNode.next 設置為 null
  previousNode.next = null;
}

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

哈希表

接下來是強大的哈希表。

哈希表是一種實現(xiàn)關聯(lián)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，這意味著它把鍵映射到值。 JavaScript 對象就是一個“哈希表”，因為它存儲鍵值對。

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

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

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

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

在介紹了哈希功能之后，該討論一下如何實現(xiàn)哈希表了。

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

實現(xiàn)哈希表的核心代碼如下：

class HashTable {
  constructor(size) {
    // 定義哈希表的大小，將在哈希函數(shù)中使用
    this.size = size;
    this.storage = [];
  }
  insert(key, value) { }
  get() {}
  remove() {}
  // 這是計算散列密鑰的方式
  myHashingFunction(str, n) {
    let sum = 0;
    for (let i = 0; i < str.length; i++) {
      sum += str.charCodeAt(i) * 3;
    }
    return sum % n;
  }
}

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

insert(key, value) {
  // 得到數(shù)組中的索引
  const index = this.myHashingFunction(key, this.size);
  // 處理沖突 - 如果哈希函數(shù)為不同的鍵返回相同的索引，
  // 在復雜的哈希函數(shù)中，很可能發(fā)生沖突
  if (!this.storage[index]) {
    this.storage[index] = [];
  }
  // push 新的鍵值對
  this.storage[index].push([key, value]);
}

像這樣調(diào)用 insert 方法：

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

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

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

現(xiàn)在實現(xiàn)從哈希表中刪除

remove(key) {
    // 首先要獲取 key 的索引，請記住，
    // 哈希函數(shù)將始終為同一 key 返回相同的索引
    const index = this.myHashingFunction(key, this.size);
    // 記住我們在一個索引處可以有多個數(shù)組（不太可能）
    let arrayAtIndex = this.storage[index];
    if (arrayAtIndex) {
      // 遍歷該索引處的所有數(shù)組
      for (let i = 0; i < arrayAtIndex.length; i++) {
        // get the pair (a, 1)
        let pair = arrayAtIndex[i];
        // 檢查 key 是否與參數(shù) key 匹配
        if (pair[0] === key) {
          delete arrayAtIndex[i];
          // 工作已經(jīng)完成，所以要退出循環(huán)
          break;
        }
      }
    }
}

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

 get(key) {
    const index = this.myHashingFunction(key, this.size);
    let arrayAtIndex = this.storage[index];
    if (arrayAtIndex) {
      for (let i = 0; i < arrayAtIndex.length; i++) {
        const pair = arrayAtIndex[i];
        if (pair[0] === key) {
          return pair[1];
        }
      }
    }
  }

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

你可以認為它并不像最初看起來那樣復雜。這是一種到處使用的數(shù)據(jù)結(jié)構(gòu)，也是是一個很好理解的結(jié)構(gòu)！

二叉搜索樹

最后一個數(shù)據(jù)結(jié)構(gòu)是臭名昭著的二叉搜索樹。

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

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

樹的核心類如下：

class Tree {
   constructor(value) {
     this.root = null
   }

   add(value) {
    // 我們將在下面實現(xiàn)
   }

}

我們還將創(chuàng)建一個 Node 類來代表每個節(jié)點。

class Node {
  constructor(value, left = null, right = null) {
    this.value = value;
    this.left = left;
    this.right = right;
  }
}

下面實現(xiàn) add 方法。我已經(jīng)對代碼進行了注釋，但是如果你發(fā)現(xiàn)使你感到困惑，請記住，我們要做的只是從根開始并檢查每個節(jié)點的 left 和 right。

add(value) {
    // 如果沒有根，那么就創(chuàng)建一個
    if (this.root === null) {
      this.root = new Node(value);
      return;
    }
    let current = this.root;
    // keep looping
    while (true) {
      // 如果當前值大于傳入的值，則向左
      if (current.value > value) {
        // 如果存在左子節(jié)點，則再次進行循環(huán)
        if (current.left) {
          current = current.left;
        } else {
          current.left = new Node(value);
          return;
        }
      }
      // 值較小，所以我們走對了
      else {
        // 向右
        // 如果存在左子節(jié)點，則再次運行循環(huán)
        if (current.right) {
          current = current.right;
        } else {
          current.right = new Node(value);
          return;
        }
      }
    }
}

測試新的 add 方法：

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

現(xiàn)在樹看起來是這樣：

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

contains(value) {
  // 獲取根節(jié)點
  let current = this.root;
  // 當存在節(jié)點時
  while (current) {
    // 檢查當前節(jié)點是否為該值
    if (value === current.value) {
      return true; // 退出函數(shù)
    }
    // 通過將我們的值與 current.value 進行比較來決定下一個當前節(jié)點
    // 如果小則往左，否則往右
    current = value < current.value ? current.left : current.right;
  }
  return false;
}

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

總結(jié)

我已經(jīng)在本文中介紹了很多內(nèi)容，并且掌握這些知識后在面試中將使你處于有利位置。希望你能夠?qū)W到一些東西，并能夠輕松地通過技術(shù)面試（尤其是討厭的白板面試）。

關于“JavaScript如何實現(xiàn)常用數(shù)據(jù)結(jié)構(gòu)”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。

本文名稱：JavaScript如何實現(xiàn)常用數(shù)據(jù)結(jié)構(gòu)
當前鏈接：http://www.muchs.cn/article10/gjgjgo.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供建站公司、云服務器、移動網(wǎng)站建設、網(wǎng)站策劃、企業(yè)建站、網(wǎng)站內(nèi)鏈

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)