Open henry-fun opened 4 years ago
原文地址: https://medium.com/siliconwat/data-structures-in-javascript-1b9aed0ea17c 原文作者: Thon Ly 翻译作者: hanxiansen 中文标题：前端必知必会的数据结构 Data Structures in JavaScript
原文地址: https://medium.com/siliconwat/data-structures-in-javascript-1b9aed0ea17c
原文作者: Thon Ly
翻译作者: hanxiansen
中文标题：前端必知必会的数据结构
随着业务逻辑越来越多地从后台迁往前端，前端工程化方面的专业知识变得愈发重要。作为一名前端工程师，我们依赖于像 React 这样的视图库来提高工作效率。而视图库又依赖于像 Redux 这样的数据流管理工具来掌控数据。React 和 Redux 共同遵循响应式设计模式，在该设计模式下，数据的更新将会导致对应 UI 的更新。后端越来越充当着简单的 API 服务器角色，提供数据的检索和更新接口。实际上，后端只是把数据库搬到了前端，期望前端来处理所有的数据控制器逻辑。微服务和 GraphQL 的日益流行证明了这一增长趋势。
现在，除了掌握 HTML 和 CSS 以外，前端工程师还应该掌握 JavaScript。因为客户端成了服务端的数据库“副本”，掌握常用的的数据结构变得至关重要。事实上，一个工程师的水平可以从 ta 知道何时及为何使用特定的数据结构的能力中得以体现。
Bad programmers worry about the code. Good programmers worry about data structures and their relationships. 糟糕的工程师考虑代码，优秀的工程师考虑数据结构及其对应关系。 — Linus Torvalds, Creator of Linux and Git
Bad programmers worry about the code. Good programmers worry about data structures and their relationships.
糟糕的工程师考虑代码，优秀的工程师考虑数据结构及其对应关系。
— Linus Torvalds, Creator of Linux and Git
总的来说，基础的数据结构分三种：栈和队列是类似数组的数据结构，它们的区别只在于插入和删除条目的方式不同。链表、树和图是具有节点的数据结构，这些节点保持着对其它节点的引用。哈希表依赖于哈希函数来保存和定位数据。就复杂度而言，栈和队列是最简单的，可以用链表来构造。树和图是最复杂的，因为它们扩展了链表的概念。哈希表利用这些数据结构来高效的执行任务。就效率而言，链表最适合记录与存储数据，哈希表则最适合搜索与检索数据。
本文将依照“为什么(why)”与“何时(when)”的顺序来进行阐释说明，让我们开始吧！
可以说，Js 中最重要的栈就是调用栈(译者注：调用栈是 js 解释器追踪函数执行流的一种机制)，在该栈中，无论何时执行函数，我们都会往栈中推入该函数的作用域。在编码中，它只是一个具有两个基本操作的数组：push 和 pop。push 将元素添加到数组的头部，而pop将它们从同一位置删除。换句话说，栈遵循“后进先出”的原则(LIFO)。
push
pop
下面是代码中的栈示例。请注意，我们可以颠倒栈的顺序：底部变为顶部，顶部变为底部。因此，我们可以使用十足的 unshift 和 shift 方法来分别代替 push 和 pop。
unshift
shift
https://codepen.io/thonly/pen/GMyLOV
随着条目数的增加，push/pop将会比unshift/shift拥有更好的性能，因为后者的每个条目都需要重建索引，但前者不需要。
Js 是一门事件驱动型语言，它使得支持非阻塞操作成为可能。在内部，浏览器只管理一个线程来运行整个 Js 代码，它使用事件队列(event queue)将事件注册到队列中，然后使用事件循环(event loop)来监听被注册的事件。为了在单线程环境中支持异步操作(节省资源并增强 Web 体验)，监听函数只有当调用栈为空时才会出队列并执行。Promise 就是基于这种事件驱动架构设计的，它允许用“同步模式”来执行不糊阻塞其它操作的异步代码。
在编程中，队列仅仅是拥有两个主要操作方法的数组：Unshift将条目列入数组的尾部，而Pop则将它们从数组头部列出。换句话说，队列遵循“First in, First Out”的原则(FIFO)。如果颠倒方向，我们可以使用push和shift方法唉替换unshift和pop方法。
Unshift
Pop
队列的代码示例如下：
https://codepen.io/thonly/pen/KypxZg
类似于数组，链表也是按照顺序存储数据元素。不同的是，链表保存指向其它元素的指针，而非索引。链表的第一个节点被称为头部节点，最后一个节点被称为尾部节点，在单链表中，每个检点只有一个指向下个节点的指针。在单链表里，头部节点是我们遍历剩余节点的的地方。在双链表中，每个节点还保留了指向上一个节点的指针。因此，我们也可以从尾部节点开始，“倒退遍历“到头部节点。
链表具有常量的插入和删除时间，因为我们只需更改指针即可。但在数组中执行相同的操作却需要线性时间，因为后续条目需要移位。此外，只要有空间，链表就可以增长。然而，及时是可以自动调整大小的“动态数组”在空间利用上也是出乎意料的昂贵。当然，事物总有权衡取舍。在链表中检索和编辑一个元素，我们需要遍历整个链表，这等同于线性时间。然而对于有索引的数组，这样的操作时微不足道的。
类似于数组，链表也可以进行栈的操作。该操作很简单，只需将头部作为插入和取出的唯一位置。链表也可以进行队列操作，这可以使用双向链表来实现，插入发生在尾部，删除发生在头部，反之亦然。对于大的数据而言，这种实现队列的方案比数组的性能更高，因为在数组的开始位置插入和移出元素，需要线性的时间来重新索引后续的每个元素。
链表数据结构在客户端和服务端都很有用。在客户端，像Express这样的 web 框架也以类似的逻辑构建它的中间件。当收到请求，请求通过管道一个接一个的传递下去，直到请求被发出。
双向链表的代码如下：
https://codepen.io/thonly/pen/QqRVJX
树类似于数组，区别在于它在层次结构中保留了对多个子节点的引用。换句话说，每个节点不止拥有一个父节点。DOM 树就是这样一种数据结构，它拥有一个 html 根节点，然后分成 head节点和 body 节点，这两个节点又进一步细分为多个你所熟悉的 html 标签。更深层面上，原型继承和 React 的组件也采用类似的树形结构。当然，作为DOM的内存表现形式，React 的虚拟 Dom也是一个树形结构。
二叉搜索树是特殊的，因为它拥有的子节点不能超过两个。左子节点的值必须小于或等于其父节点的值，而右子节点的值必须大于父节点的值。通过这种结构和平衡方式，我们可以在指数时间内检索任何值，因为我们可以在每次迭代中忽略另一半分支。插入和删除的时间也是指数级的。此外最小值和最大值也可以很容易的在最左边和最右边的叶子节点中找到。
遍历树可以在垂直或水平过程中进行。在垂直方向的深度优先遍历(DFT)中，递归算法将会比迭代算法更加优雅。节点遍历可以按照前序遍历、中序遍历、后序遍历的方式进行。如果我们需要先访问根节点再探索叶子节点，我们应选择前序遍历。但如果我们需要先访问叶子节点再访问根节点，我们应选择后序遍历。顾名思义，中序遍历使我们可以按照顺序进行遍历。这种特性使二叉搜索树成为排序的最佳选择。
在水平方向上的广度优先遍历(BFT)中，迭代比递归更优雅。这需要使用一个队列来追踪每次迭代的所有子节点。这样一个队列所需的内存是微不足道的。然而，如果树的形状宽大于深，BFT 是比 DFT 更好的选择。此外，BFT 在任意两个节点之间采用的路径是可能的最短路径。
二叉搜索树的示例代码如下：
https://codepen.io/thonly/pen/qVWOpM
如果一个树可以自由的拥有多个父级节点，它将变为Graph(图)。将图中的节点连接在一起的边可以是有方向的，也可以是无方向的，可以是加权的，也可以是未加权的。同时具备方向和权重的边类似于矢量。
混合形式的多重继承和具有多对多关系的数据对象生成图形结构。社交网络和互联网本身也是图。自然界中最复杂的图是我们的人脑，神经网络试图复制人脑来赋予机器超级智能。
哈希表是一种类似于字典的结构，它将键与值进行配对。每个键值对在内存中的储存位置由焊锡函数决定，该哈希函数接收一个 key ，然后返回它应该插入和检索该键值对的地址。如果两个或更多的 key 被转换为同一个地址，可能会导致冲突。为了保持哈希函数的健壮性，getter 和 setter 方法应该预防到这些问题，来确保可以恢复所有的数据，并且不会覆盖任何数据，通常，链表可以提供最简单的解决方案。拥有巨大空间的哈希表也同样可以解决该问题。
看起来这个很期待啊
icepy
commented
4 years ago
介绍
随着业务逻辑越来越多地从后台迁往前端，前端工程化方面的专业知识变得愈发重要。作为一名前端工程师，我们依赖于像 React 这样的视图库来提高工作效率。而视图库又依赖于像 Redux 这样的数据流管理工具来掌控数据。React 和 Redux 共同遵循响应式设计模式，在该设计模式下，数据的更新将会导致对应 UI 的更新。后端越来越充当着简单的 API 服务器角色，提供数据的检索和更新接口。实际上，后端只是把数据库搬到了前端，期望前端来处理所有的数据控制器逻辑。微服务和 GraphQL 的日益流行证明了这一增长趋势。
现在，除了掌握 HTML 和 CSS 以外，前端工程师还应该掌握 JavaScript。因为客户端成了服务端的数据库“副本”，掌握常用的的数据结构变得至关重要。事实上，一个工程师的水平可以从 ta 知道何时及为何使用特定的数据结构的能力中得以体现。
总的来说，基础的数据结构分三种：栈和队列是类似数组的数据结构，它们的区别只在于插入和删除条目的方式不同。链表、树和图是具有节点的数据结构，这些节点保持着对其它节点的引用。哈希表依赖于哈希函数来保存和定位数据。就复杂度而言，栈和队列是最简单的，可以用链表来构造。树和图是最复杂的，因为它们扩展了链表的概念。哈希表利用这些数据结构来高效的执行任务。就效率而言，链表最适合记录与存储数据，哈希表则最适合搜索与检索数据。
本文将依照“为什么(why)”与“何时(when)”的顺序来进行阐释说明，让我们开始吧！
栈(Stack)
可以说，Js 中最重要的栈就是调用栈(译者注：调用栈是 js 解释器追踪函数执行流的一种机制)，在该栈中，无论何时执行函数，我们都会往栈中推入该函数的作用域。在编码中，它只是一个具有两个基本操作的数组：
push和pop。push将元素添加到数组的头部，而pop将它们从同一位置删除。换句话说，栈遵循“后进先出”的原则(LIFO)。下面是代码中的栈示例。请注意，我们可以颠倒栈的顺序：底部变为顶部，顶部变为底部。因此，我们可以使用十足的
unshift和shift方法来分别代替push和pop。https://codepen.io/thonly/pen/GMyLOV
随着条目数的增加，
push/pop将会比unshift/shift拥有更好的性能，因为后者的每个条目都需要重建索引，但前者不需要。队列(Queue)
Js 是一门事件驱动型语言，它使得支持非阻塞操作成为可能。在内部，浏览器只管理一个线程来运行整个 Js 代码，它使用事件队列(event queue)将事件注册到队列中，然后使用事件循环(event loop)来监听被注册的事件。为了在单线程环境中支持异步操作(节省资源并增强 Web 体验)，监听函数只有当调用栈为空时才会出队列并执行。Promise 就是基于这种事件驱动架构设计的，它允许用“同步模式”来执行不糊阻塞其它操作的异步代码。
在编程中，队列仅仅是拥有两个主要操作方法的数组：
Unshift将条目列入数组的尾部，而Pop则将它们从数组头部列出。换句话说，队列遵循“First in, First Out”的原则(FIFO)。如果颠倒方向，我们可以使用push和shift方法唉替换unshift和pop方法。队列的代码示例如下：
https://codepen.io/thonly/pen/KypxZg
链表(Linked List)
类似于数组，链表也是按照顺序存储数据元素。不同的是，链表保存指向其它元素的指针，而非索引。链表的第一个节点被称为头部节点，最后一个节点被称为尾部节点，在单链表中，每个检点只有一个指向下个节点的指针。在单链表里，头部节点是我们遍历剩余节点的的地方。在双链表中，每个节点还保留了指向上一个节点的指针。因此，我们也可以从尾部节点开始，“倒退遍历“到头部节点。
链表具有常量的插入和删除时间，因为我们只需更改指针即可。但在数组中执行相同的操作却需要线性时间，因为后续条目需要移位。此外，只要有空间，链表就可以增长。然而，及时是可以自动调整大小的“动态数组”在空间利用上也是出乎意料的昂贵。当然，事物总有权衡取舍。在链表中检索和编辑一个元素，我们需要遍历整个链表，这等同于线性时间。然而对于有索引的数组，这样的操作时微不足道的。
类似于数组，链表也可以进行栈的操作。该操作很简单，只需将头部作为插入和取出的唯一位置。链表也可以进行队列操作，这可以使用双向链表来实现，插入发生在尾部，删除发生在头部，反之亦然。对于大的数据而言，这种实现队列的方案比数组的性能更高，因为在数组的开始位置插入和移出元素，需要线性的时间来重新索引后续的每个元素。
链表数据结构在客户端和服务端都很有用。在客户端，像Express这样的 web 框架也以类似的逻辑构建它的中间件。当收到请求，请求通过管道一个接一个的传递下去，直到请求被发出。
双向链表的代码如下：
https://codepen.io/thonly/pen/QqRVJX
树(Tree)
树类似于数组，区别在于它在层次结构中保留了对多个子节点的引用。换句话说，每个节点不止拥有一个父节点。DOM 树就是这样一种数据结构，它拥有一个 html 根节点，然后分成 head节点和 body 节点，这两个节点又进一步细分为多个你所熟悉的 html 标签。更深层面上，原型继承和 React 的组件也采用类似的树形结构。当然，作为DOM的内存表现形式，React 的虚拟 Dom也是一个树形结构。
二叉搜索树是特殊的，因为它拥有的子节点不能超过两个。左子节点的值必须小于或等于其父节点的值，而右子节点的值必须大于父节点的值。通过这种结构和平衡方式，我们可以在指数时间内检索任何值，因为我们可以在每次迭代中忽略另一半分支。插入和删除的时间也是指数级的。此外最小值和最大值也可以很容易的在最左边和最右边的叶子节点中找到。
遍历树可以在垂直或水平过程中进行。在垂直方向的深度优先遍历(DFT)中，递归算法将会比迭代算法更加优雅。节点遍历可以按照前序遍历、中序遍历、后序遍历的方式进行。如果我们需要先访问根节点再探索叶子节点，我们应选择前序遍历。但如果我们需要先访问叶子节点再访问根节点，我们应选择后序遍历。顾名思义，中序遍历使我们可以按照顺序进行遍历。这种特性使二叉搜索树成为排序的最佳选择。
在水平方向上的广度优先遍历(BFT)中，迭代比递归更优雅。这需要使用一个队列来追踪每次迭代的所有子节点。这样一个队列所需的内存是微不足道的。然而，如果树的形状宽大于深，BFT 是比 DFT 更好的选择。此外，BFT 在任意两个节点之间采用的路径是可能的最短路径。
二叉搜索树的示例代码如下：
https://codepen.io/thonly/pen/qVWOpM
图(Graph)
如果一个树可以自由的拥有多个父级节点，它将变为Graph(图)。将图中的节点连接在一起的边可以是有方向的，也可以是无方向的，可以是加权的，也可以是未加权的。同时具备方向和权重的边类似于矢量。
混合形式的多重继承和具有多对多关系的数据对象生成图形结构。社交网络和互联网本身也是图。自然界中最复杂的图是我们的人脑，神经网络试图复制人脑来赋予机器超级智能。
哈希表(Hash Table)
哈希表是一种类似于字典的结构，它将键与值进行配对。每个键值对在内存中的储存位置由焊锡函数决定，该哈希函数接收一个 key ，然后返回它应该插入和检索该键值对的地址。如果两个或更多的 key 被转换为同一个地址，可能会导致冲突。为了保持哈希函数的健壮性，getter 和 setter 方法应该预防到这些问题，来确保可以恢复所有的数据，并且不会覆盖任何数据，通常，链表可以提供最简单的解决方案。拥有巨大空间的哈希表也同样可以解决该问题。