這篇文章將為大家詳細(xì)講解有關(guān)JavaScript如何實(shí)現(xiàn)常用數(shù)據(jù)結(jié)構(gòu)，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。
10年的新華網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都營銷網(wǎng)站建設(shè)的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整新華建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。成都創(chuàng)新互聯(lián)公司從事“新華網(wǎng)站設(shè)計(jì)”,“新華網(wǎng)站推廣”以來，每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。
在 JavaScript 中數(shù)據(jù)結(jié)構(gòu)通?？偸潜缓雎?，或者接觸得不多。但是對(duì)于許多大廠而言，一般都需要你深刻了解如何管理數(shù)據(jù)。掌握數(shù)據(jù)結(jié)構(gòu)也能夠在解決問題時(shí)為你的工作提供幫助。
在本文中，我們將要討論并實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)是：
棧
隊(duì)列
鏈表
哈希表
樹
第一個(gè)數(shù)據(jù)結(jié)構(gòu)是棧。它與隊(duì)列非常相似，你之前可能聽說過調(diào)用棧，這是 JavaScript 用于處理事件的方法。
?？雌饋硐襁@樣：
.jpg)
最后一個(gè)存入棧里的項(xiàng)目將是第一個(gè)被移除的項(xiàng)目。這被稱為后進(jìn)先出（LIFO）。 Web 瀏覽器中的后退按鈕就是一個(gè)很好的例子：將你查看的每個(gè)頁面添加到棧中，當(dāng)你單擊“返回”時(shí)，將從棧中彈出當(dāng)前頁面（最后添加的頁面）。
理論足夠多了。接下來看一些代碼：
重慶分公司
重慶分公司
class Stack {
constructor() {
// 創(chuàng)建棧結(jié)構(gòu)，這是一個(gè)空對(duì)象
this.stack = {}
}
// 把一個(gè)值壓入棧的頂部
push(value) {
}
// 彈出棧頂?shù)闹挡⒎祷?
pop() {
}
// 讀取棧中的最后一個(gè)值，但是不刪除
peek() {
}
}我已經(jīng)對(duì)上面的代碼進(jìn)行了注釋，現(xiàn)在咱們一起對(duì)其進(jìn)行實(shí)現(xiàn)。第一種方法是 push。
先思考一下需要這個(gè)方法做的事情：
我們需要接受一個(gè)值
然后將該值添加到棧的頂部
還應(yīng)該跟蹤棧的長(zhǎng)度，以便知道棧的索引
如果你能夠先自己嘗試一下，那就太好了，完整的 push 方法實(shí)現(xiàn)如下：
class Stack {
constructor() {
this._storage = {};
this._length = 0; // 這是棧的大小
}
push(value) {
// 將值添加到棧頂
this._storage[this._length] = value;
// 因?yàn)樵黾恿艘粋€(gè)值，所以也應(yīng)該將長(zhǎng)度加1
this._length++;
}
/// .....
}我敢打賭，這比你想象的要容易。有許多類似這樣的結(jié)構(gòu)，它們聽起來比實(shí)際上要復(fù)雜得多。
現(xiàn)在是 pop 方法。 pop 方法的目標(biāo)是刪除最后一個(gè)添加到棧中的值，然后返回它。如果可以的話，請(qǐng)先自己嘗試實(shí)現(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
}
}酷！快要完成了。最后一個(gè)是 peek 函數(shù)，該函數(shù)查看棧中的最后一項(xiàng)。這是最簡(jiǎn)單的功能：只需要返回最后一個(gè)值。實(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 方法非常相似，但不刪除最后一項(xiàng)。
Yes！第一個(gè)數(shù)據(jù)結(jié)構(gòu)已經(jīng)實(shí)現(xiàn)。接著是隊(duì)列，隊(duì)列與棧非常相似。
接下來討論隊(duì)列——希望棧在你的腦子仍然記得很清楚，因?yàn)樗完?duì)列非常相似。棧和隊(duì)列之間的主要區(qū)別在于隊(duì)列是先進(jìn)先出（FIFO）。
可以用圖形這樣表示：
所以兩個(gè)主要方法是 enqueue 與 dequeue。數(shù)據(jù)被添加到隊(duì)尾，并從隊(duì)首移除。為了更好的理解它，下面開始實(shí)現(xiàn)隊(duì)列。
核心代碼結(jié)構(gòu)如下所示：
class Queue {
constructor() {
// 與前面類似，我們?yōu)閿?shù)據(jù)結(jié)構(gòu)提供了一個(gè)對(duì)象
// 并且還有一個(gè)變量來保存長(zhǎng)度
this.queue = {}
this.length = 0
// 這是一個(gè)跟蹤頭部的新變量
this.head = 0
}
enqueue(value) {
}
dequeue() {
}
peek() {
}
}首先實(shí)現(xiàn) enqueue 方法。其目的是向隊(duì)尾添加一個(gè)項(xiàng)目。
enqueue(value) {
// 使用 value 參數(shù)將 length + head 的鍵添加到對(duì)象
this.queue[this.length + this.head] = value;
this.length++
}這是一個(gè)非常簡(jiǎn)單的方法，可以在隊(duì)列的末尾添加一個(gè)值，但是你可能會(huì)對(duì)this.queue[this.length + this.head] = value;感到困惑。
假設(shè)隊(duì)列看起來像這樣的 {14 : 'randomVal'}。在添加這個(gè)內(nèi)容時(shí)，我們希望的下一個(gè)值為 15，所以應(yīng)該是 length(1) + head(14)，即為 15。
下一個(gè)要實(shí)現(xiàn)的是 dequeue ：
dequeue() {
// 獲取第一個(gè)值的引用，以便將其返回
const firstVal = this.queue[this.head]
// 現(xiàn)在將其從隊(duì)列中刪除
delete this.queue[this.head]
this.length--;
// 最終增加我們的頭成為下一個(gè)節(jié)點(diǎn)
this.head++;
}最后要實(shí)現(xiàn)的是 peek 方法，非常簡(jiǎn)單：
peek() {
// 只需要把值返回即可
return this.queue[this.head];
}隊(duì)列實(shí)現(xiàn)完畢。
先讓我們討論一下強(qiáng)大的鏈表。這比上面的結(jié)構(gòu)要復(fù)雜得多。
可能你第一個(gè)問題是為什么要使用鏈表？鏈表主要用于沒有動(dòng)態(tài)大小調(diào)整數(shù)組的語言。鏈表按順序組織項(xiàng)目，一個(gè)項(xiàng)目指向下一個(gè)項(xiàng)目。
鏈表中的每個(gè)節(jié)點(diǎn)都有一個(gè) data 值和一個(gè) next 值。下圖中 5 是 data 值，next 值指向下一個(gè)節(jié)點(diǎn)，即值為 10 的節(jié)點(diǎn)。
在視覺上，它看起來像這樣：
在一個(gè)對(duì)象中，上面的 LinkedList 看起來像下面的樣子
.jpg)
你會(huì)看到最后一個(gè)值 1 的 next 值為 null，因?yàn)檫@是 LinkedList 的結(jié)尾。
那么該如何實(shí)現(xiàn)呢？
讓我們創(chuàng)建一個(gè)具有值 1、 2 和 37的 LinkedList。
const myLinkedList = {
head: {
value: 1
next: {
value: 2
next: {
value: 37
next: null
}
}
}
};現(xiàn)在我們知道了該怎樣手動(dòng)創(chuàng)建 LinkedList，但是還需要編碼實(shí)現(xiàn) LinkedList 的方法。
首先要注意的是，LinkedList 只是一堆嵌套對(duì)象！
當(dāng)構(gòu)造一個(gè) LinkedList 時(shí)，我們需要一個(gè) head 和一個(gè) tail，它們最初都會(huì)指向頭部（因?yàn)?head 是第一個(gè)也是最后一個(gè)）。
class LinkedList {
constructor(value) {
this.head = {value, next: null}
this.tail = this.head
}
}第一個(gè)要實(shí)現(xiàn)的方法是 insert ，該方法用來在鏈表的末尾插入一個(gè)值。
// insert 將添加到鏈接列表的末尾
insert(value) {
/* 創(chuàng)建一個(gè)節(jié)點(diǎn) */
const node = {value, next: null}
/* 把 tail 的 next 屬性設(shè)置為新節(jié)點(diǎn)的引用 */
this.tail.next = node;
/* 新節(jié)點(diǎn)現(xiàn)在是尾節(jié)點(diǎn) */
this.tail = node;
}上面最混亂的一行可能是 this.tail.next = node。之所以這樣做，是因?yàn)楫?dāng)添加一個(gè)新節(jié)點(diǎn)時(shí)，我們還希望當(dāng)前的 tail 指向新的 node，該節(jié)點(diǎn)將成為新的 tail。第一次插入 node 時(shí)，頭部的 next 指針將指向新節(jié)點(diǎn)，就像在構(gòu)造函數(shù)中那樣，在其中設(shè)置了 this.tail = this.head。
你還可以到這個(gè)網(wǎng)站來查看圖形化的演示，這將幫你了解插入的過程（按 esc 擺脫煩人的彈出窗口）。
下一個(gè)方法是刪除節(jié)點(diǎn)。我們首先要決定參數(shù)是值（ value） 還是對(duì)節(jié)點(diǎn)（node）的引用（在面試中，最好先問問面試官）。我們的代碼中傳遞了一個(gè)“值”。按值從列表中刪除節(jié)點(diǎn)是一個(gè)緩慢的過程，因?yàn)楸仨氁闅v整個(gè)列表才能找到值。
我這樣做是這樣的：
removeNode(val) {
/* 從 head 開始 */
let currentNode = this.head
/* 我們需要保留對(duì)上一個(gè)節(jié)點(diǎn)的引用 */
let previousNode
/* 當(dāng)存在一個(gè)節(jié)點(diǎn)時(shí)，意味著沒有到達(dá)尾部 */
while(currentNode) {
/* 如果發(fā)現(xiàn)自己想要的那個(gè)值，那么就退出循環(huán) */
if(currentNode.value === val) {
break;
}
/* 沒有找到值就將 currentNode 設(shè)置為 previousNode */
previousNode = currentNode
/* 得到下一個(gè)節(jié)點(diǎn)并將其分配給currentNode */
currentNode = currentNode.next
}
/* 返回undefined，因?yàn)闆]有找到具有該值的節(jié)點(diǎn) */
if (currentNode=== null) {
return false;
}
// 如果節(jié)點(diǎn)是 head ，那么將 head 設(shè)置為下一個(gè)值
頭節(jié)點(diǎn)的
if (currentNode === this.head) {
this.head = this.head.next;
return;
}
/* 通過將節(jié)點(diǎn)設(shè)置為前面的節(jié)點(diǎn)來刪除節(jié)點(diǎn) */
previousNode.next = currentNode.next
}removeNode 方法使我們對(duì) LinkedList 的工作方式有了很好的了解。
所以再次說明一下，首先將變量 currentNode 設(shè)置為 LinkedList 的 head，因?yàn)檫@是第一個(gè)節(jié)點(diǎn)。然后創(chuàng)建一個(gè)名為 previousNode 的占位符變量，該變量將在 while 循環(huán)中使用。從條件 currentNode 開始 while 循環(huán)，只要存在 currentNode，就會(huì)一直運(yùn)行。
在 while 循環(huán)中第一步是檢查是否有值。如果不是，則將 previousNode 設(shè)置為 currentNode，并將 currentNode 設(shè)置為列表中的下一個(gè)節(jié)點(diǎn)。繼續(xù)進(jìn)行此過程，直到找到我需要找的值或遍歷完節(jié)點(diǎn)為止。
在 while 循環(huán)之后，如果沒有 currentNode，則返回 false，這意味著沒有找到任何節(jié)點(diǎn)。如果確實(shí)存在一個(gè) currentNode，則檢查的 currentNode 是否為 head。如果是的話就把 LinkedList 的 head 設(shè)置為第二個(gè)節(jié)點(diǎn)，它將成為 head。
最后，如果 currentNode 不是頭，就把 previousNode 設(shè)置為指向 currentNode 前面的 node，這將會(huì)從對(duì)象中刪除 currentNode。
另一個(gè)常用的方法（面試官可能還會(huì)問你）是 removeTail 。這個(gè)方法如其所言，只是去掉了 LinkedList 的尾節(jié)點(diǎn)。這比上面的方法容易得多，但工作原理類似。
我建議你先自己嘗試一下，然后再看下面的代碼（為了使其更復(fù)雜一點(diǎn)，我們?cè)跇?gòu)造函數(shù)中不使用 tail）：
removeTail() {
let currentNode = this.head;
let previousNode;
while (currentNode) {
/* 尾部是唯一沒有下一個(gè)值的節(jié)點(diǎn)，所以如果不存在下一個(gè)值，那么該節(jié)點(diǎn)就是尾部 */
if (!currentNode.next) {
break;
}
// 獲取先前節(jié)點(diǎn)的引用
previousNode = currentNode;
// 移至下一個(gè)節(jié)點(diǎn)
currentNode = currentNode.next;
}
// 要?jiǎng)h除尾部，將 previousNode.next 設(shè)置為 null
previousNode.next = null;
}這些就是 LinkedList 的一些主要方法。鏈表還有各種方法，但是利用以上學(xué)到的知識(shí)，你應(yīng)該能夠自己實(shí)現(xiàn)它們。
接下來是強(qiáng)大的哈希表。
哈希表是一種實(shí)現(xiàn)關(guān)聯(lián)數(shù)組的數(shù)據(jù)結(jié)構(gòu)，這意味著它把鍵映射到值。 JavaScript 對(duì)象就是一個(gè)“哈希表”，因?yàn)樗鎯?chǔ)鍵值對(duì)。
在視覺上，可以這樣表示：
.jpg)
在討論如何實(shí)現(xiàn)哈希表之前，需要討論討論哈希函數(shù)的重要性。哈希函數(shù)的核心概念是它接受任意大小的輸入并返回固定長(zhǎng)度的哈希值。
hashThis('i want to hash this') => 7哈希函數(shù)可能非常復(fù)雜或直接。 GitHub 上的每個(gè)文件都經(jīng)過了哈希處理，這使得每個(gè)文件的查找都非?？?。哈希函數(shù)背后的核心思想是，給定相同的輸入將返回相同的輸出。
在介紹了哈希功能之后，該討論一下如何實(shí)現(xiàn)哈希表了。
將要討論的三個(gè)操作是 insert、get最后是 remove。
實(shí)現(xiàn)哈希表的核心代碼如下：
class HashTable {
constructor(size) {
// 定義哈希表的大小，將在哈希函數(shù)中使用
this.size = size;
this.storage = [];
}
insert(key, value) { }
get() {}
remove() {}
// 這是計(jì)算散列密鑰的方式
myHashingFunction(str, n) {
let sum = 0;
for (let i = 0; i < str.length; i++) {
sum += str.charCodeAt(i) * 3;
}
return sum % n;
}
}現(xiàn)在解決第一個(gè)方法，即 insert。insert 到哈希表中的代碼如下（為簡(jiǎn)單起見，此方法將簡(jiǎn)單的處理沖突問題）：
insert(key, value) {
// 得到數(shù)組中的索引
const index = this.myHashingFunction(key, this.size);
// 處理沖突 - 如果哈希函數(shù)為不同的鍵返回相同的索引，
// 在復(fù)雜的哈希函數(shù)中，很可能發(fā)生沖突
if (!this.storage[index]) {
this.storage[index] = [];
}
// push 新的鍵值對(duì)
this.storage[index].push([key, value]);
}像這樣調(diào)用 insert 方法：
const myHT = new HashTable(5);
myHT.insert("a", 1);
myHT.insert("b", 2);你認(rèn)為我們的哈希表會(huì)是什么樣的？
你可以看到鍵值對(duì)已插入到表中的索引 1 和 4 處。
現(xiàn)在實(shí)現(xiàn)從哈希表中刪除
remove(key) {
// 首先要獲取 key 的索引，請(qǐng)記住，
// 哈希函數(shù)將始終為同一 key 返回相同的索引
const index = this.myHashingFunction(key, this.size);
// 記住我們?cè)谝粋€(gè)索引處可以有多個(gè)數(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];
}
}
}
}我認(rèn)為不需要執(zhí)行這個(gè)操作，因?yàn)樗淖饔门c remove 方法相同。
你可以認(rèn)為它并不像最初看起來那樣復(fù)雜。這是一種到處使用的數(shù)據(jù)結(jié)構(gòu)，也是是一個(gè)很好理解的結(jié)構(gòu)！
最后一個(gè)數(shù)據(jù)結(jié)構(gòu)是臭名昭著的二叉搜索樹。
在二叉搜索樹中，每個(gè)節(jié)點(diǎn)具有零個(gè)、一個(gè)或兩個(gè)子節(jié)點(diǎn)。左邊的稱為左子節(jié)點(diǎn)，右邊的稱為右子節(jié)點(diǎn)。在二叉搜索樹中，左側(cè)的子項(xiàng)必須小于右側(cè)的子項(xiàng)。
你可以像這樣描繪一個(gè)二叉搜索樹：
樹的核心類如下：
class Tree {
constructor(value) {
this.root = null
}
add(value) {
// 我們將在下面實(shí)現(xiàn)
}
}我們還將創(chuàng)建一個(gè) Node 類來代表每個(gè)節(jié)點(diǎn)。
class Node {
constructor(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
}下面實(shí)現(xiàn) add 方法。我已經(jīng)對(duì)代碼進(jìn)行了注釋，但是如果你發(fā)現(xiàn)使你感到困惑，請(qǐng)記住，我們要做的只是從根開始并檢查每個(gè)節(jié)點(diǎn)的 left 和 right。
add(value) {
// 如果沒有根，那么就創(chuàng)建一個(gè)
if (this.root === null) {
this.root = new Node(value);
return;
}
let current = this.root;
// keep looping
while (true) {
// 如果當(dāng)前值大于傳入的值，則向左
if (current.value > value) {
// 如果存在左子節(jié)點(diǎn)，則再次進(jìn)行循環(huán)
if (current.left) {
current = current.left;
} else {
current.left = new Node(value);
return;
}
}
// 值較小，所以我們走對(duì)了
else {
// 向右
// 如果存在左子節(jié)點(diǎn)，則再次運(yùn)行循環(huán)
if (current.right) {
current = current.right;
} else {
current.right = new Node(value);
return;
}
}
}
}測(cè)試新的 add 方法：
const t = new Tree(); t.add(2); t.add(5); t.add(3);
現(xiàn)在樹看起來是這樣：
為了更好的理解，讓我們實(shí)現(xiàn)一個(gè)檢查樹中是否包含值的方法。
contains(value) {
// 獲取根節(jié)點(diǎn)
let current = this.root;
// 當(dāng)存在節(jié)點(diǎn)時(shí)
while (current) {
// 檢查當(dāng)前節(jié)點(diǎn)是否為該值
if (value === current.value) {
return true; // 退出函數(shù)
}
// 通過將我們的值與 current.value 進(jìn)行比較來決定下一個(gè)當(dāng)前節(jié)點(diǎn)
// 如果小則往左，否則往右
current = value < current.value ? current.left : current.right;
}
return false;
}Add 和 Contains 是二進(jìn)制搜索樹的兩個(gè)核心方法。對(duì)這兩種方法的了解可以使你更好地解決日常工作中的問題。
我已經(jīng)在本文中介紹了很多內(nèi)容，并且掌握這些知識(shí)后在面試中將使你處于有利位置。希望你能夠?qū)W到一些東西，并能夠輕松地通過技術(shù)面試（尤其是討厭的白板面試）。
關(guān)于“JavaScript如何實(shí)現(xiàn)常用數(shù)據(jù)結(jié)構(gòu)”這篇文章就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，使各位可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，請(qǐng)把它分享出去讓更多的人看到。
