JavaScript中的数据结构

发表于 | 分类于 |

持续更新中…

数组

JavaScript引擎都在尽力的优化以接近C类语言的性能。

对于数组而言，可以直接使用，但最好是触发Fast Elements，具体可查看：《高性能的JavaScript开发》的数组部分

栈、队列

使用数组就可以轻易的模拟了，最多封装个类方便使用。

栈： push pop
队列：unshift pop

Set

es6已经有了，直接使用吧！

链表

我一直认为 链表 是数组长度固定化的产物，js的数组是动态的，不觉得它还有什么存在的必要， arr.splice(10, 1, newNode) 这种代码不是比链表插入要优美得多？而且还有一堆方法可以直接用：shift, unshift, pop, push, forEach, map …

遍历也可以直接用 for...of 使用Iterator的方式

当然如果有不同的意见，我也可以改正。

如果是为了练习代码能力，那倒是不妨自己实现一个。

HashTable、Dictionary

js中的对象起到的作用已经超过了基础的数据结构 Dictionary 和 HashTable，也不必费心去实现了，而且es6还有Map。

hash算法倒是个有意思的东西，不过不在当前范畴。

树

这里还是数学概念：

  • 自由树是一个连通的、无回路的无向图。
  • 有根树就是多了个根节点，由此就有了“父子层级”的概念。
  • 有序树指的是子级节点有序的树。
  • 二叉树是指最多有两个子节点的树。
  • 完全二叉树是指子节点是满的，只要有就一定是两个，并且叶节点的深度一定相同（就是说左右子树的层数相等）。

树的最大特点是：任意两个顶点由唯一一条简单路径相连

二叉树 => 二叉查找树 => 红黑树 => B树 => B+树 …. ????

二叉查找树

节点存值，左子树都比它小，右子树都比它大。

执行基本操作的时间与树的高度成正比。n个节点的完全二叉树，操作最坏运行时间为O(lgn)；如果是线性链（子级节点都跑一边去了），最坏是O(n)。

一颗随机构造的二叉树期望高度为O(lgn)，基本操作的平均时间为O(lgn)。

一个简陋的二叉查找树的实现

图

经典的图定义是 G = (V, E):

1
2
3
4
5
// 至少我曾经会这么写……
class Graph {
    nodes = [];
    edges = [];
}

但实际上有两种表示方法：邻接表 or 邻接矩阵，上面那个一般是邻接矩阵，当然要写成边集的话那也没办法~~

来看图示：

邻接表无向图
邻接表有向图

邻接矩阵，网上找的图：

邻接表适合于稀疏图（|E|远小于|V|^2)，因为表示出来比较紧凑
邻接矩阵则适合于稠密图，或必须很快判别两个给定顶点是否存在连接边（顶点间最短路径算法）

待续…