Javascript中的8种常见数据结构（建议收藏）

679次阅读 | 发布于4年以前

1.Stack（栈）

堆栈遵循LIFO（后进先出）的原则。如果你把书堆叠起来，上面的书会比下面的书先拿。或者当你在网上浏览时，后退按钮会引导你到最近浏览的页面。

Stack具有以下常见方法：

push：输入一个新元素
pop：删除顶部元素，返回删除的元素
peek：返回顶部元素
length：返回堆栈中元素的数量

Javascript中的数组具有Stack的属性，但是我们使用 function Stack() 从头开始构建Stack

function Stack() {
    this.count = 0;
  this.storage = {};

  this.push = function (value) {
    this.storage[this.count] = value;
    this.count++;
  }

  this.pop = function () {
    if (this.count === 0) {
      return undefined;
    }
    this.count--;
    var result = this.storage[this.count];
    delete this.storage[this.count];
    return result;
  }

  this.peek = function () {
    return this.storage[this.count - 1];
  }

  this.size = function () {
    return this.count;
  }
}

2.Queue（队列）

Queue与Stack类似。唯一不同的是，Queue使用的是FIFO原则（先进先出）。换句话说，当你排队等候公交车时，队列中的第一个总是先上车。

队列具有以下方法：

enqueue：输入队列，在最后添加一个元素
dequeue：离开队列，删除前元素并返回
front：得到第一个元素
isEmpty：确定队列是否为空
size：获取队列中元素的数量

JavaScript中的数组具有Queue的某些属性，因此我们可以使用数组来构造Queue的示例：

function Queue() {
  var collection = [];
  this.print = function () {
    console.log(collection);
  }
  this.enqueue = function (element) {
    collection.push(element);
  }
  this.dequeue = function () {
    return collection.shift();
  }
  this.front = function () {
    return collection[0];
  }

  this.isEmpty = function () {
    return collection.length === 0;
  }
  this.size = function () {
    return collection.length;
  }
}

优先队列

队列还有另一个高级版本。为每个元素分配优先级，并将根据优先级对它们进行排序：

function PriorityQueue() {

  ...

  this.enqueue = function (element) {
    if (this.isEmpty()) {
      collection.push(element);
    } else {
      var added = false;
      for (var i = 0; i < collection.length; i++) {
        if (element[1] < collection[i][1]) {
          collection.splice(i, 0, element);
          added = true;
          break;
        }
      }
      if (!added) {
        collection.push(element);
      }
    }
  }
}

测试一下：

var pQ = new PriorityQueue();
pQ.enqueue([ gannicus , 3]);
pQ.enqueue([ spartacus , 1]);
pQ.enqueue([ crixus , 2]);
pQ.enqueue([ oenomaus , 4]);
pQ.print();

[
  [  spartacus , 1 ],
  [  crixus , 2 ],
  [  gannicus , 3 ],
  [  oenomaus , 4 ]
]

Linked List（链表）

从字面上看，链表是一个链式数据结构，每个节点由两个信息组成：节点的数据和指向下一个节点的指针。链表和传统数组都是线性数据结构，具有序列化的存储方式。当然，它们也有差异：

比较	Array	Linked List
内存分配	静态内存分配，发生在编译和序列化过程中	动态内存分配，发生在运行过程中，非连续的。
获取元素	从索引中读取，速度更快	读取队列中的所有节点，直到得到特定的元素，速度较慢
添加/删除元素	由于是顺序记忆和静态记忆，速度较慢	由于是动态分配，只需要少量的内存开销，速度更快
空间结构	一维或多维	单边/双边，或循环链表

单边链表通常具有以下方法：

size：返回节点数
head：返回头部的元素
add：在尾部添加另一个节点
remove：删除某些节点
indexOf：返回节点的索引
elementAt：返回索引的节点
addAt：在特定索引处插入节点
removeAt：删除特定索引处的节点

/** 链表中的节点 **/
function Node(element) {
    // 节点中的数据
    this.element = element;
    // 指向下一个节点的指针
    this.next = null;
}
function LinkedList() {
  var length = 0;
  var head = null;
  this.size = function () {
    return length;
  }
  this.head = function () {
    return head;
  }
  this.add = function (element) {
    var node = new Node(element);
    if (head == null) {
      head = node;
    } else {
      var currentNode = head;
      while (currentNode.next) {
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    }
    length++;
  }
  this.remove = function (element) {
    var currentNode = head;
    var previousNode;
    if (currentNode.element === element) {
      head = currentNode.next;
    } else {
      while (currentNode.element !== element) {
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    length--;
  }
  this.isEmpty = function () {
    return length === 0;
  }
  this.indexOf = function (element) {
    var currentNode = head;
    var index = -1;
    while (currentNode) {
      index++;
      if (currentNode.element === element) {
        return index;
      }
      currentNode = currentNode.next;
    }
    return -1;
  }
  this.elementAt = function (index) {
    var currentNode = head;
    var count = 0;
    while (count < index) {
      count++;
      currentNode = currentNode.next;
    }
    return currentNode.element;
  }
  this.addAt = function (index, element) {
    var node = new Node(element);
    var currentNode = head;
    var previousNode;
    var currentIndex = 0;
    if (index > length) {
      return false;
    }
    if (index === 0) {
      node.next = currentNode;
      head = node;
    } else {
      while (currentIndex < index) {
        currentIndex++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      node.next = currentNode;
      previousNode.next = node;
    }
    length++;
  }
  this.removeAt = function (index) {
    var currentNode = head;
    var previousNode;
    var currentIndex = 0;
    if (index < 0 || index >= length) {
      return null;
    }
    if (index === 0) {
      head = currentIndex.next;
    } else {
      while (currentIndex < index) {
        currentIndex++;
        previousNode = currentNode;
        currentNode = currentNode.next;
      }
      previousNode.next = currentNode.next;
    }
    length--;
    return currentNode.element;
  }
}

Set（集合）

集合是数学的基本概念：定义明确且不同的对象的集合。ES6引入了集合的概念，它与数组有一定程度的相似性。但是，集合不允许重复元素，也不会被索引。

一个典型的集合具有以下方法：

values：返回集合中的所有元素
size：返回元素个数
has：确定元素是否存在
add：将元素插入集合
remove：从集合中删除元素
union：返回两组交集
difference：返回两组的差
subset：确定某个集合是否是另一个集合的子集

为了区分ES6中的 set，我们在以下示例中声明为 MySet：

function MySet() {
  var collection = [];
  this.has = function (element) {
    return (collection.indexOf(element) !== -1);
  }
  this.values = function () {
    return collection;
  }
  this.size = function () {
    return collection.length;
  }
  this.add = function (element) {
    if (!this.has(element)) {
      collection.push(element);
      return true;
    }
    return false;
  }
  this.remove = function (element) {
    if (this.has(element)) {
      index = collection.indexOf(element);
      collection.splice(index, 1);
      return true;
    }
    return false;
  }
  this.union = function (otherSet) {
    var unionSet = new MySet();
    var firstSet = this.values();
    var secondSet = otherSet.values();
    firstSet.forEach(function (e) {
      unionSet.add(e);
    });
    secondSet.forEach(function (e) {
      unionSet.add(e);
    });
    return unionSet;  }
  this.intersection = function (otherSet) {
    var intersectionSet = new MySet();
    var firstSet = this.values();
    firstSet.forEach(function (e) {
      if (otherSet.has(e)) {
        intersectionSet.add(e);
      }
    });
    return intersectionSet;
  }
  this.difference = function (otherSet) {
    var differenceSet = new MySet();
    var firstSet = this.values();
    firstSet.forEach(function (e) {
      if (!otherSet.has(e)) {
        differenceSet.add(e);
      }
    });
    return differenceSet;
  }
  this.subset = function (otherSet) {
    var firstSet = this.values();
    return firstSet.every(function (value) {
      return otherSet.has(value);
    });
  }
}

Hast table（哈希表）

哈希表是一种键值数据结构。由于通过键值查询的速度快如闪电，所以常用于Map、Dictionary或Object数据结构中。如上图所示，哈希表使用哈希函数(hash function)将键转换为数字列表，这些数字作为对应键的值。要快速使用键获取价值，时间复杂度可以达到O(1)。相同的键必须返回相同的值——这是哈希函数的基础。

哈希表具有以下方法：

add：添加键值对
remove：删除键值对
lookup：使用键查找对应的值

一个Javascript中简化的哈希表的例子：

function hash(string, max) {
  var hash = 0;
  for (var i = 0; i < string.length; i++) {
    hash += string.charCodeAt(i);
  }
  return hash % max;
}

function HashTable() {
  let storage = [];
  const storageLimit = 4;

  this.add = function (key, value) {
    var index = hash(key, storageLimit);
    if (storage[index] === undefined) {
      storage[index] = [
        [key, value]
      ];
    } else {
      var inserted = false;
      for (var i = 0; i < storage[index].length; i++) {
        if (storage[index][i][0] === key) {
          storage[index][i][1] = value;
          inserted = true;
        }
      }
      if (inserted === false) {
        storage[index].push([key, value]);
      }
    }
  }

  this.remove = function (key) {
    var index = hash(key, storageLimit);
    if (storage[index].length === 1 && storage[index][0][0] === key) {
      delete storage[index];
    } else {
      for (var i = 0; i < storage[index]; i++) {
        if (storage[index][i][0] === key) {
          delete storage[index][i];
        }
      }
    }
  }

  this.lookup = function (key) {
    var index = hash(key, storageLimit);
    if (storage[index] === undefined) {
      return undefined;
    } else {
      for (var i = 0; i < storage[index].length; i++) {
        if (storage[index][i][0] === key) {
          return storage[index][i][1];
        }
      }
    }
  }
}

Tree（树）

Tree(树)数据结构是多层结构。与Array，Stack和Queue相比，它也是一种非线性数据结构。这种结构在插入和搜索操作时效率很高。我们来看看树型数据结构的一些概念。

root：树的根节点，无父节点
parent node：上层的直接节点，只有一个
child node：下层的直接节点可以有多个
siblings：共享同一个父节点
leaf：没有孩子的节点
Edge：节点之间的分支或链接
path：从起始节点到目标节点的边
Height of Nod：特定节点到叶节点的最长路径的边数
Height of Tree：根节点到叶节点的最长路径的边数
Depth of Node：从根节点到特定节点的边数
Degree of Node：子节点数

这里以二叉树为例。每个节点最多有两个节点，左边节点比当前节点小，右边节点比当前节点大。

二叉树中的常用方法：

add：将节点插入树
findMin：获取最小节点
findMax：获取最大节点
find：搜索特定节点
isPresent：确定某个节点的存在
remove：从树中删除节点

JavaScript中的示例：

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

class BST {
  constructor() {
    this.root = null;
  }

  add(data) {
    const node = this.root;
    if (node === null) {
      this.root = new Node(data);
      return;
    } else {
      const searchTree = function (node) {
        if (data < node.data) {
          if (node.left === null) {
            node.left = new Node(data);
            return;
          } else if (node.left !== null) {
            return searchTree(node.left);
          }
        } else if (data > node.data) {
          if (node.right === null) {
            node.right = new Node(data);
            return;
          } else if (node.right !== null) {
            return searchTree(node.right);
          }
        } else {
          return null;
        }
      };
      return searchTree(node);
    }
  }

  findMin() {
    let current = this.root;
    while (current.left !== null) {
      current = current.left;
    }
    return current.data;
  }

  findMax() {
    let current = this.root;
    while (current.right !== null) {
      current = current.right;
    }
    return current.data;
  }

  find(data) {
    let current = this.root;
    while (current.data !== data) {
      if (data < current.data) {
        current = current.left
      } else {
        current = current.right;
      }
      if (current === null) {
        return null;
      }
    }
    return current;
  }

  isPresent(data) {
    let current = this.root;
    while (current) {
      if (data === current.data) {
        return true;
      }
      if (data < current.data) {
        current = current.left;
      } else {
        current = current.right;
      }
    }
    return false;
  }

  remove(data) {
    const removeNode = function (node, data) {
      if (node == null) {
        return null;
      }
      if (data == node.data) {
        // no child node
        if (node.left == null && node.right == null) {
          return null;
        }
        // no left node
        if (node.left == null) {
          return node.right;
        }
        // no right node
        if (node.right == null) {
          return node.left;
        }
        // has 2 child nodes
        var tempNode = node.right;
        while (tempNode.left !== null) {
          tempNode = tempNode.left;
        }
        node.data = tempNode.data;
        node.right = removeNode(node.right, tempNode.data);
        return node;
      } else if (data < node.data) {
        node.left = removeNode(node.left, data);
        return node;
      } else {
        node.right = removeNode(node.right, data);
        return node;
      }
    }
    this.root = removeNode(this.root, data);
  }
}

测试一下：

const bst = new BST();
bst.add(4);
bst.add(2);
bst.add(6);
bst.add(1);
bst.add(3);
bst.add(5);
bst.add(7);
bst.remove(4);
console.log(bst.findMin());
console.log(bst.findMax());
bst.remove(7);
console.log(bst.findMax());
console.log(bst.isPresent(4));

1
7
6
false

7. Trie (发音为 “try”)

Trie或“前缀树”也是搜索树的一种。Trie分步存储数据——树中的每个节点代表一个步骤。Trie是用来存储词汇的，所以它可以快速搜索，特别是自动完成功能。

Trie中的每个节点都有一个字母——分支之后可以组成一个完整的单词。它还包括一个布尔指示符，以显示这是否是最后一个字母。

Trie具有以下方法：

add：在字典树中插入一个单词
isWord：确定树是否由某些单词组成
print：返回树中的所有单词

/** Node in Trie **/
function Node() {
  this.keys = new Map();
  this.end = false;
  this.setEnd = function () {
    this.end = true;
  };
  this.isEnd = function () {
    return this.end;
  }
}

function Trie() {
  this.root = new Node();
  this.add = function (input, node = this.root) {
    if (input.length === 0) {
      node.setEnd();
      return;
    } else if (!node.keys.has(input[0])) {
      node.keys.set(input[0], new Node());
      return this.add(input.substr(1), node.keys.get(input[0]));
    } else {
      return this.add(input.substr(1), node.keys.get(input[0]));
    }
  }
  this.isWord = function (word) {
    let node = this.root;
    while (word.length > 1) {
      if (!node.keys.has(word[0])) {
        return false;
      } else {
        node = node.keys.get(word[0]);
        word = word.substr(1);
      }
    }
    return (node.keys.has(word) && node.keys.get(word).isEnd()) ? true : false;
  }
  this.print = function () {
    let words = new Array();
    let search = function (node = this.root, string) {
      if (node.keys.size != 0) {
        for (let letter of node.keys.keys()) {
          search(node.keys.get(letter), string.concat(letter));
        }
        if (node.isEnd()) {
          words.push(string);
        }
      } else {
        string.length > 0 ? words.push(string) : undefined;
        return;
      }
    };
    search(this.root, new String());
    return words.length > 0 ? words : null;
  }
}

Graph（图）

Graph（有时称为网络）是指具有链接（或边）的节点集。根据联系是否有方向性，可以进一步分为两组（即定向图和不定向图）。Graph在我们的生活中被广泛使用——在导航应用中计算最佳路线，或者在社交媒体中推荐朋友，举两个例子。

图有两种表示形式：

邻接清单

在此方法中，我们在左侧列出所有可能的节点，并在右侧显示已连接的节点。

邻接矩阵

相邻矩阵以行和列的形式显示节点，行和列的交点诠释了节点之间的关系，0表示没有联系，1表示有联系，>1表示权重不同。

要查询图中的节点，必须用 “宽度优先搜索"（BFS）方法或 "深度优先搜索"（DFS）方法在整个树网中进行搜索。

让我们看一个例子的BFS在Javascript：

function bfs(graph, root) {
  var nodesLen = {};
  for (var i = 0; i < graph.length; i++) {
    nodesLen[i] = Infinity;
  }
  nodesLen[root] = 0;
  var queue = [root];
  var current;
  while (queue.length != 0) {
    current = queue.shift();

    var curConnected = graph[current];
    var neighborIdx = [];
    var idx = curConnected.indexOf(1);
    while (idx != -1) {
      neighborIdx.push(idx);
      idx = curConnected.indexOf(1, idx + 1);
    }
    for (var j = 0; j < neighborIdx.length; j++) {
      if (nodesLen[neighborIdx[j]] == Infinity) {
        nodesLen[neighborIdx[j]] = nodesLen[current] + 1;
        queue.push(neighborIdx[j]);
      }
    }
  }
  return nodesLen;
}

测试一下：

var graph = [
  [0, 1, 1, 1, 0],
  [0, 0, 1, 0, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [0, 1, 0, 0, 0]
];
console.log(bfs(graph, 1));

// 结果
{
  0: 2,
  1: 0,
  2: 1,
  3: 3,
  4: Infinity
}

就是这样——我们已经介绍了所有常见的数据结构，并给出了JavaScript中的例子。这应该能让你更好地了解数据结构在计算机中的工作原理。祝你编码愉快！

1.Stack（栈）

2.Queue（队列）

优先队列

Linked List（链表）

Set（集合）

Hast table（哈希表）

Tree（树）

7. Trie (发音为 “try”)

Graph（图）