{T}

常用的数据结构

数据结构是计算机中组织和存储数据的特定方式，也是对基本数据类型的一种高级抽象，它描述了数据之间的关系，以及操作数据的方法。

数据结构不仅是编程语言和算法的基础，对于前端工程师而言，也变得越来越重要。随着 Web 应用的快速发展，前端工程师面临的场景也越来越复杂，无论 React、Vue 这些框架，还是大型 Web 应用，都离不开数据结构的支持。而且越来越多的公司也将数据结构列为面试考察点，所以掌握数据结构，是高级前端工程师的必备技能。

本节我们就来分析最常用的 5 种数据结构：数组、栈、队列、链表、树。

数组

高级语言的原生数据类型一般都提供了数组类型，所以数组结构并不需要特别的实现方式。

数组虽然看似简单，但基于它可以生成一些更复杂的数据结构，比如多维数组、栈、队列等，本节如无特殊说明，数组都指代一维数组。

数组的最大优势在于可以通过索引来快速访问特定的元素，尤其是在有序数组中，比如要在一个升序数组 arr 中找到第 6 小的元素，那么可以直接通过下标 5 获取。

大家在工作中对数组应该比较熟悉了，所以这里就不再详细介绍了，只介绍一下数组的实现原理。V8引擎将 JavaScript 数组分为两类：

  • FixedArray，使用连续的内存进行存储，可以使用索引直接定位，新创建的空数组默认为FixedArray 类型，当数组超过最大长度会进行动态地扩容；

  • HashTable，以哈希表的形式存储在内存空间里，存储地址不连续，与 FixedArray 类型相比，性能相对较差。

这两者之间在实际使用时可以相互转换：

  • FixedArray 转 HashTable，当新增元素的索引值相对于数组长度大于等于 1024 或者新容量 >= 3× 扩容后的容量 × 2；

  • HashTable 转 FixedArray，当 HashTable 数组的元素可存放在 FixedArray 数组中且长度在 smi之间且仅节省了 50% 的空间时发生转换，其中 smi 值在不同操作系统下有所不同。

小结一下，FixedArray 数组通过牺牲空间来提升操作效率，HashTable 数组则相反，不必申请连续的空间，节省了内存，但需要付出效率变差的代价。

栈

栈是一种操作受限的线性结构，限定只能在尾部进行插入和删除操作，尾部被称为栈顶，而头部称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，从一个栈删除元素又称作出栈或退栈。这种受限的操作方式让栈元素的入栈出栈遵循一种特殊的原则——先进后出（First In Last Out，FILO）。

栈的应用非常广泛，这里列举 3 种：

  • 浏览器的历史记录，它的前进、后退功能就是一个栈操作；

  • V8 中的函数执行过程采用的栈结构；

  • JavaScript 在捕获代码异常时，详细信息会以调用栈的形式打印。

栈可以通过数组来实现，下面的代码实现了一个栈结构：

javascript
function Stack() {

    var _stack = [];

    this.push = function (element) {
        _stack.push(element);
    }

    this.pop = function () {
        return _stack.pop();
    }

    this.top = function () {
        return _stack[_stack.length - 1];
    }

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

    this.size = function () {
        return _stack.length;
    }

    this.clear = function () {
        _stack = [];
    }
}

队列

队列和栈一样也是操作受限的线性结构，但和栈有所区别的是，队列可以在头部和尾部进行操作，但尾部只能插入，头部只能删除。这种受限的操作方式让队列元素的插入和删除遵循一种特殊的原则——先进先出原则（First In First Out，FIFO）

JavaScript 在处理异步操作时经常会用到队列，比如宏任务队列、微任务队列、回调函数队列。

队列的实现也可以通过数组来实现，下面的代码实现了一个队列结构：

javascript
function Queue() {

    var _queue = [];

    this.enqueue = function (element) {
        _queue.push(element)
    }

    this.dequeue = function () {
        return _queue.shift()
    }

    this.front = function () {
        return _queue[0]
    }

    this.back = function () {
        return _queue[_queue.length - 1]
    }
  
  	this.clear = function () {
   			 _queue = []
		}

		this.isEmpty = function () {
    			return _queue.length === 0
		}

		this.size = function () {
    			return _queue.length
		}
}

链表

链表是在存储空间上具有一定优势的线性结构。因为它的有序性是通过指针来实现的，即每个元素都有一个指向下一个元素的指针（链表末端元素可能指向 null），所以它不需要连续的内存空间，从而可以节省内存的占用。例如 React.js 的 Fiber 算法就是基于链表实现的。

下面的代码实现了一个基础的链表，包括链表的查找、新增和删除功能。

javascript
function LinkedList() {

    var head = {
        value: 'head',
        next: null
    }

    this.find = function (item) {
        var currNode = head
        while (currNode.value !== item) {
            currNode = currNode.next
        }
        return currNode
    }

    this.insert = function (value, pre) {
        var newNode = {
            value,
            next: null
        }

        var currNode = this.find(pre)
        newNode.next = currNode.next
        currNode.next = newNode
    }

    this.remove = function (item) {
        var prevNode = this.findPrev(item)
        var currNode = this.find(item)
        if (prevNode.next !== null) {
            prevNode.next = prevNode.next.next
            currNode.next = null
        }
    }

    this.findPrev = function (item) {
        var currNode = head
        while (currNode.next !== null && currNode.next.value !== item) {
            currNode = currNode.next
        }
        return currNode
    }

}

栈、队列由于操作受限，无法像数组一样通过下标来访问，查找某个元素时只能逐个进行操作，操作效率并不算高。链表由于指针的存在，使得在操作效率方面有很大的提升空间。

从指针的方向上考虑，既可以单向也可以双向，那么就可以形成具有两个指针的双向链表，还可以让指针的头尾相连，形成双向循环链表。在一个双向循环链表中查找元素，就可以同时往两个方向查找，这使得在查找速度方面会略优于单向循环链表。

libuv 中就使用到了双向循环链表来管理任务。

从指针的数量上考虑，还可以通过增加指针的方式来提升操作效率，跳跃表就是这样一种基于链表的数据结构。

下面是一个跳跃表实现原理的例子，在一个链表中建立了 3 层指针。最下一层指针，跨 1 个元素链接；

中间一层指针，跨 2 个元素链接；上层指针，跨 4 个元素链接。

javascript
1---------->5---------->9->null 

1---->3---->5---->7---->9->null 

1->2->3->4->5->6->7->8->9->null

假设现在要在链表中找到数字 8，对于简单链表而言，需要查找 8 次。而在上述跳跃表中，只需要 5步：

  1. 使用上层指针，找到 5，8 比 5 大，继续；

  2. 继续使用上层指针，找到 9，8 比 9 小，回退到 5，并且指针层数下移；

  3. 使用中层指针，找到 7，8 比 7 大，继续；

  4. 使用中层指针，找到 9，8 比 9 小，回退到 7，并且指针层数下移；

  5. 使用下层指针，找到 8。

总的来说，跳跃表通过增加链表元素的冗余指针，使用了空间换时间的方式来提升操作效率。在著名的缓存数据库 Redis 中就使用了跳跃表这种数据结构。

树

树型数据结构在前面的课程中已多次提到，比如（虚拟）DOM 树、抽象语法分析树，大家对于它应该都不陌生。总结起来，树就是有限节点组成一个具有层次关系的集合，因为它看起来非常像一棵倒着生长的树，根朝上叶朝下，所以命名为 “树”。

树根据结构不同，可以分为很多类，比如有序树（树中任意节点，比如，点的子节点之间有顺序关系）、二叉树（每个节点最多有 2 个子树）、满二叉树（除最后一层所有节点都有两个子节点）等。

其中，二叉树是最简单且最基础的树。说它简单，是因为每个节点至多包含两个子节点；说它基础，是因为二叉树可以延伸出一些子类，比如二叉搜索树（BST）、平衡二叉搜索树（AVL）、红黑树（R/BTree）等。

所以我们重点分析二叉树的查询操作——遍历。

树的遍历操作分为两类：深度遍历和广度遍历，其中深度遍历按照遍历根节点的顺序不同又可以分为 3类：先序遍历、中序遍历和后序遍历。它们的遍历顺序如下：

  • 先序遍历，根节点→左子树→右子树

  • 中序遍历，左子树→根节点→右子树

  • 后序遍历，左子树→右子树→根节点

  • 广度遍历，逐层从左至右访问

实现深度遍历最简单的方式就是通过递归，下面是具体代码：

javascript
// 先序遍历，根->左->右 

function preOrder(node, result = []) {

    if (!node) return

    result.push(node.value);

    preOrder(node.left, result);

    preOrder(node.right, result);

    return result;
}

// 中序遍历，左->根->右 

function inOrder(node, result = []) {

    if (!node) return

    inOrder(node.left, result);

    result.push(node.value);

    inOrder(node.right, result);

    return result;

}

// 后序遍历，左->右->根 

function postOrder(node, result = []) {

    if (!node) return

    postOrder(node.left, result);

    postOrder(node.right, result);

    result.push(node.value);

    return result;

}

广度优先遍历的实现会稍稍复杂一些，因为每次访问节点时都要回溯到上一层的父节点，通过其指针进行访问。但每一层都是从左至右的遍历顺序，这种操作方式很符合队列的先进先出原则，所以可以通过队列来缓存遍历的节点，具体代码如下所示：

javascript
function breadthOrder(node) {

    if (!node) return

    var result = []

    var queue = []

    queue.push(node)

    while (queue.length !== 0) {

        node = queue.shift()

        result.push(node.value)

        if (node.left) queue.push(node.left)

        if (node.right) queue.push(node.right)

    }

    return result

}

总结

本节我们介绍了和前端最为贴合的 5 种数据结构，包括数组、栈、队列、链表、树。讲解数组时，JavaScript 引擎通过两种数据结构实现数组，包括 FixedArray 和 HashTable，FixedArray 在时间上有优势，而 HashTable 在空间上更有优势。

栈和队列都是操作受限的数据结构，底层实现都可以借助数组，分别遵循 FILO 和 FIFO 原则。链表由于采用指针连接元素节点，所以可以使用不连续的内存地址，在空间上更有优势。链表有一些变种，包括循环链表、双向链表、双向循环链表及跳跃表，其中跳跃表通过增加指针，达到了空间换时间的效果，能增加查找效率。

树是应用最广泛的非线性结构，子类很多，其中二叉树最为重要，对于其遍历方式需要重点掌握