JavaScript实现常用数据构造（栈、队列、链表、哈希表、树）

相关引荐：《javascript视频教程》

在 JavaScript 中数据构造平常总是被忽略，或者接触得不多。但是关于很多大厂而言，一样都需要你深刻理解怎样治理数据。把握数据构造也能够在解决问题时为你的工作供给帮忙。

在本文中，我们将要计议并实现的数据构造是：

• 栈
• 队列
• 链表
• 哈希表
• 树

栈

第一个数据构造是栈。它与队列非常类似，你此前大概据说过调取栈，这是 JavaScript 用于处置事件的办法。

栈看起来像这样：

最后一个存入栈里的项目将是第一个被移除的项目。这被称为后进先出（LIFO）。 Web 阅读器中的后退按钮就是一个很好的例子：将你查看的每个页面增加到栈中，当你单击“返回”时，将从栈中弹出当前页面（最后增加的页面）。

理论足够多了。接下来看一些代码：

class Stack {
  constructor() {
    // 创立栈构造，这是一个空对象
    this.stack = {}
  }
  // 把一个值压入栈的顶部
  push(value) {

  }
  // 弹出栈顶的值并返回
  pop() {

  }

  // 读取栈中的最后一个值，但是不删除
  peek() {

  }
}

我已经对上面的代码停止了注释，此刻咱们一起对其停止实现。第一种办法是 push。

先思索一下需要这个办法做的事情：

• 我们需要接受一个值
• 然后将该值增加到栈的顶部
• 还应当跟踪栈的长度，以便知道栈的索引

假如你能够先本人尝试一下，那就太好了，完全的 push 办法实现如下：

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

  push(value) {
    // 将值增加到栈顶
    this._storage[this._length] = value;
    // 由于增添了一个值，所以也应当将长度加1
    this._length++;
  }
  /// .....
}

我敢打赌，这比你想象的要容易。有很多相似这样的构造，它们听起来比实际上要复杂得多。

此刻是 pop 办法。 pop 办法的目标是删除最后一个增加到栈中的值，然后返回它。假如可以的话，请先本人尝试实现：

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 函数，该函数查看栈中的最后一项。这是最简便的功效：只需要返回最后一个值。实现是：

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！第一个数据构造已经实现。接着是队列，队列与栈非常类似。

队列

接下来计议队列——但愿栈在你的脑子依然记得很分明，由于它和队列非常类似。栈和队列之间的主要不同在于队列是先进先出（FIFO）。

可以用图形这样表示：

所以两个主要办法是 enqueue 与 dequeue。数据被增加到队尾，并从队首移除。为了更好的懂得它，下面开端实现队列。

中心代码构造如下所示：

class Queue {
  constructor() {
    // 与前面相似，我们为数据构造供给了一个对象
    // 并且还有一个变量来留存长度
    this.queue = {}
    this.length = 0
    // 这是一个跟踪头部的新变量
    this.head = 0
  }

  enqueue(value) {

  }

  dequeue() {

  }

  peek() {

  }
}

第一实现 enqueue 办法。其目的是向队尾增加一个项目。

enqueue(value) {
  // 使用 value 参数将 length + head 的键增加到对象
  this.queue[this.length + this.head] = value;
  this.length++
}

这是一个非常简便的办法，可以在队列的末尾增加一个值，但是你大概会对this.queue[this.length + this.head] = value;感到困惑。

假设队列看起来像这样的 {14 : 'randomVal'}。在增加这个内容时，我们但愿的下一个值为 15，所以应当是 length(1) + head(14)，即为 15。

下一个要实现的是 dequeue ：

dequeue() {
  // 猎取第一个值的援用，以便将其返回
  const firstVal = this.queue[this.head]
  // 此刻将其从队列中删除
  delete this.queue[this.head]
  this.length--;
  // 终究增添我们的头成为下一个节点
  this.head++;
}

最后要实现的是 peek 办法，非常简便：

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

队列实现完毕。

链表

先让我们计议一下强大的链表。这比上面的构造要复杂得多。

大概你第一个问题是为什么要使用链表？链表主要用于没有动态大小调整数组的说话。链表按次序组织项目，一个项目指向下一个项目。

链表中的每个节点都有一个 data 值和一个 next 值。下图中 5 是 data 值，next 值指向下一个节点，即值为 10 的节点。

在视觉上，它看起来像这样：

在一个对象中，上面的 LinkedList 看起来像下面的模样

你会看到最后一个值 1 的 next 值为 null，由于这是 LinkedList 的结尾。

那么该怎样实现呢？

让我们创立一个具有值 1、 2 和 37的 LinkedList。

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

此刻我们知道了该怎样手动创立 LinkedList，但是还需要编码实现 LinkedList 的办法。

第一要留意的是，LinkedList 只是一堆嵌套对象！

当结构一个 LinkedList 时，我们需要一个 head 和一个 tail，它们最初都会指向头部（由于 head 是第一个也是最后一个）。

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

第一个要实现的办法是 insert ，该办法用来在链表的末尾插入一个值。

// insert 将增加到链接列表的末尾
insert(value) {
  /* 创立一个节点 */
  const node = {value, next: null}
  /* 把 tail 的 next 属性设定为新节点的援用 */
  this.tail.next = node;
  /* 新节点此刻是尾节点 */
  this.tail = node;
}

上面最纷乱的一行大概是 this.tail.next = node。之所以这样做，是由于当增加一个新节点时，我们还但愿当前的 tail 指向新的 node，该节点将成为新的 tail。第一次插入 node 时，头部的 next 指针将指向新节点，就像在结构函数中那样，在其中设定了 this.tail = this.head。

你还可以到这个网站来查看图形化的演示，这将帮你理解插入的历程（按 esc 挣脱烦人的弹出窗口）。

下一个办法是删除节点。我们第一要决议参数是值（ value） 还是对节点（node）的援用（在面试中，最好先问问面试官）。我们的代码中传递了一个“值”。按值从列表中删除节点是一个迟缓的历程，由于必需要遍历整个列表才能寻到值。

我这样做是这样的：

removeNode(val) {
  /* 从 head 开端 */
  let currentNode = this.head
  /* 我们需要保存对上一个节点的援用 */
  let previousNode
  /* 当存在一个节点时，意味着没有抵达尾部 */
  while(currentNode) {
     /* 假如发明本人想要的阿谁值，那么就退出轮回 */
     if(currentNode.value === val) {
        break;
     }
    /* 没有寻到值就将 currentNode 设定为 previousNode */
    previousNode = currentNode
    /* 得到下一个节点并将其分配给currentNode  */
    currentNode = currentNode.next
  }
  /* 返回undefined，由于没有寻到具有该值的节点  */
  if (currentNode=== null) {
    return false;
  }

  // 假如节点是 head ，那么将 head 设定为下一个值
  头节点的
  if (currentNode === this.head) {
    this.head = this.head.next;
    return;
  }
  /* 通过将节点设定为前面的节点来删除节点 */  
  previousNode.next = currentNode.next
}

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）：

removeTail() {
  let currentNode = this.head;
  let previousNode;
  while (currentNode) {
    /* 尾部是独一没有下一个值的节点，所以假如不存鄙人一个值，那么该节点就是尾部 */
    if (!currentNode.next) {
      break;
    }
    // 猎取先前节点的援用
    previousNode = currentNode;
    // 移至下一个节点
    currentNode = currentNode.next;
  }
  // 要删除尾部，将 previousNode.next 设定为 null
  previousNode.next = null;
}

这些就是 LinkedList 的一些主要办法。链表还有各种办法，但是利用以上学到的知识，你应当能够本人实现它们。

哈希表

接下来是强大的哈希表。

哈希表是一种实现关联数组的数据构造，这意味着它把键映射到值。 JavaScript 对象就是一个“哈希表”，由于它储备键值对。

在视觉上，可以这样表示：

在计议怎样实现哈希表此前，需要计议计议哈希函数的重要性。哈希函数的中心概念是它接受任意大小的输入并返回牢固长度的哈希值。

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

哈希函数大概非常复杂或直接。 GitHub 上的每个文件都经过了哈希处置，这使得每个文件的查寻都非常快。哈希函数背后的中心思想是，给定雷同的输入将返回雷同的输出。

在介绍了哈希功效之后，该计议一下怎样实现哈希表了。

将要计议的三个操纵是 insert、get最后是 remove。

实现哈希表的中心代码如下：

class HashTable {
  constructor(size) {
    // 定义哈希表的大小，将在哈希函数中使用
    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;
  }
}

此刻解决第一个办法，即 insert。insert 到哈希表中的代码如下（为简便起见，此办法将简便的处置冲突问题）：

insert(key, value) {
  // 得到数组中的索引
  const index = this.myHashingFunction(key, this.size);
  // 处置冲突 - 假如哈希函数为不一样的键返回雷同的索引，
  // 在复杂的哈希函数中，很大概发生冲突
  if (!this.storage[index]) {
    this.storage[index] = [];
  }
  // push 新的键值对
  this.storage[index].push([key, value]);
}

像这样调取 insert 办法：

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

你认为我们的哈希表会是啥样的？

你可以看到键值对已插入到表中的索引 1 和 4 处。

此刻实现从哈希表中删除

remove(key) {
    // 第一要猎取 key 的索引，请记住，
    // 哈希函数将始终为统一 key 返回雷同的索引
    const index = this.myHashingFunction(key, this.size);
    // 记住我们在一个索引处可以有多个数组（不太大概）
    let arrayAtIndex = this.storage[index];
    if (arrayAtIndex) {
      // 遍历该索引处的所有数组
      for (let i = 0; i < arrayAtIndex.length; i++) {
        // get the pair (a, 1)
        let pair = arrayAtIndex[i];
        // 检查 key 可否与参数 key 匹配
        if (pair[0] === key) {
          delete arrayAtIndex[i];
          // 工作已经完成，所以要退出轮回
          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];
        }
      }
    }
  }

我认为不需要施行这个操纵，由于它的作用与 remove 办法雷同。

你可以认为它并不像最初看起来那样复杂。这是一种各处使用的数据构造，也是是一个很好懂得的构造！

二叉搜索树

最后一个数据构造是臭名昭著的二叉搜索树。

在二叉搜索树中，每个节点具有零个、一个或两个子节点。左边的称为左子节点，右侧的称为右子节点。在二叉搜索树中，左侧的子项必需小于右侧的子项。

你可以像这样描画一个二叉搜索树：

树的中心类如下：

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

   add(value) {
    // 我们将鄙人面实现
   }

}

我们还将创立一个 Node 类来代表每个节点。

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

下面实现 add 办法。我已经对代码停止了注释，但是假如你发明使你感到困惑，请记住，我们要做的只是从根开端并检查每个节点的 left 和 right。

add(value) {
    // 假如没有根，那么就创立一个
    if (this.root === null) {
      this.root = new Node(value);
      return;
    }
    let current = this.root;
    // keep looping
    while (true) {
      // 假如当前值大于传入的值，则向左
      if (current.value > value) {
        // 假如存在左子节点，则再次停止轮回
        if (current.left) {
          current = current.left;
        } else {
          current.left = new Node(value);
          return;
        }
      }
      // 值较小，所以我们走对了
      else {
        // 向右
        // 假如存在左子节点，则再次运转轮回
        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);

此刻树看起来是这样：

为了更好的懂得，让我们实现一个检查树中可否包括值的办法。

contains(value) {
  // 猎取根节点
  let current = this.root;
  // 当存在节点时
  while (current) {
    // 检查当前节点可否为该值
    if (value === current.value) {
      return true; // 退出函数
    }
    // 通过将我们的值与 current.value 停止比力来决议下一个当前节点
    // 假如小则往左，不然往右
    current = value < current.value ? current.left : current.right;
  }
  return false;
}

Add 和 Contains 是二进制搜索树的两个中心办法。对这两种办法的理解可以使你更好地解决日常工作中的问题。

总结

我已经在本文中介绍了许多内容，并且把握这些知识后在面试中将使你处于有益位置。但愿你能够学到一些东西，并能够轻松地通过技术面试（特别是厌恶的白板面试）。