JS 数据结构实现指南 - 链表、栈、队列与哈希表的应用场景

夜晨

发布时间：2025-09-21 22:23:01

530人浏览过

来源于php中文网

原创

链表、栈、队列与哈希表在JavaScript中通过对象和数组模拟实现，各自适用于不同场景：链表适合频繁增删的动态数据，如LRU缓存；栈遵循LIFO原则，用于函数调用、撤销操作；队列遵循FIFO，适用于任务调度与事件循环；哈希表（Map/对象）提供键值对快速访问，广泛用于缓存、状态管理。性能上，链表插入删除O(1)，访问O(N)；数组实现的栈push/pop高效，队列shift存在O(N)瓶颈；Map相比普通对象更优，支持任意键类型、避免原型污染且保持插入顺序。实际应用中，链表支撑React Fiber架构，栈管理路由与撤销，队列驱动事件循环，哈希表优化状态与渲染。选择时需权衡访问模式与操作频率，优先使用Map并注意内存管理，如WeakMap防泄漏。

js 数据结构实现指南 - 链表、栈、队列与哈希表的应用场景

JavaScript中的链表、栈、队列与哈希表是构建高效、可维护代码的基石，它们各自以独特的存储和访问机制，解决着不同场景下的数据管理难题，理解并善用它们，能显著提升我们处理复杂逻辑的能力。

解决方案

谈到数据结构，我个人觉得它们就像是编程世界的“工具箱”，每种工具都有其独特用途。在JavaScript里，虽然我们没有C++或Java那样直接的底层实现，但通过对象和数组的组合，我们依然能优雅地模拟并运用这些核心数据结构。

链表（Linked List）

链表，在我看来，是一种非常灵活的数据结构。它不像数组那样在内存中是连续的，而是通过节点（Node）连接起来的。每个节点通常包含两部分：数据和指向下一个节点的指针（引用）。

实现思路： 最基本的链表会有一个

head

指向第一个节点。我们可以创建一个

Node

类，包含

value

和

next

属性。

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.size = 0;
    }
    // 插入、删除等操作...
}

应用场景：
- 实现LRU缓存： 当缓存满时，需要淘汰最久未使用的项。链表能高效地进行头部插入（最新使用）和尾部删除（最久未使用）。
- 图片查看器中的“上一张/下一张”功能： 每个图片可以看作一个节点，通过链表结构可以快速切换。
- 内存管理： 操作系统底层可能会用链表来管理空闲内存块。

栈（Stack）

栈，我常把它比作一叠盘子，遵循“后进先出”（LIFO - Last In, First Out）的原则。你最后放上去的盘子，肯定是最先拿走的。

实现思路： JavaScript数组的

push()

和

pop()

方法完美契合栈的操作。

class Stack {
    constructor() {
        this.items = [];
    }
    push(element) {
        this.items.push(element);
    }
    pop() {
        if (this.isEmpty()) {
            return "Underflow"; // 栈空
        }
        return this.items.pop();
    }
    peek() { // 查看栈顶元素
        return this.items[this.items.length - 1];
    }
    isEmpty() {
        return this.items.length === 0;
    }
}

应用场景：
- 函数调用栈： JavaScript引擎在执行函数时，会将函数及局部变量压入栈中，函数执行完毕后弹出。
- 浏览器历史记录的“后退”功能： 每次访问新页面就压栈，点击后退就弹出。
- 括号匹配： 判断表达式中的括号是否正确匹配，左括号入栈，右括号出栈并匹配。

队列（Queue）

队列，就像排队买票，遵循“先进先出”（FIFO - First In, First Out）的原则。先来的人先买票。

实现思路： 同样可以用JavaScript数组实现，

push()

用于入队，

shift()

用于出队。但需要注意

shift()

操作在数组较大时性能会下降，因为它会重新索引所有元素。更优的实现可能需要两个指针（

head

和

tail

）或者使用链表。

class Queue {
    constructor() {
        this.items = [];
    }
    enqueue(element) {
        this.items.push(element);
    }
    dequeue() {
        if (this.isEmpty()) {
            return "Underflow"; // 队列空
        }
        return this.items.shift(); // 性能瓶颈
    }
    front() { // 查看队首元素
        if (this.isEmpty()) {
            return "No elements in queue";
        }
        return this.items[0];
    }
    isEmpty() {
        return this.items.length === 0;
    }
}

应用场景：
- 任务调度： 比如打印机队列、消息队列，按顺序处理任务。
- 广度优先搜索（BFS）： 遍历图或树时，按层级访问节点。
- 事件循环（Event Loop）： JavaScript的宏任务队列（如
```
setTimeout
```
  ）和微任务队列（如
```
Promise
```
  ）本质上就是队列。

哈希表（Hash Table / Map）

哈希表，或者在JavaScript中我们更常使用

Map

对象或普通对象来模拟它，它是一种通过键（key）直接访问值（value）的数据结构。它的核心在于一个哈希函数，能将任意键映射到一个固定大小的数组索引上。

实现思路： JavaScript提供了原生的

Map

对象，它提供了更强大的功能和更好的性能。普通对象也可以作为简单的哈希表使用，但键必须是字符串或Symbol。

// 使用Map
const myMap = new Map();
myMap.set('name', 'Alice');
myMap.set(123, 'Bob'); // 键可以是任意类型
console.log(myMap.get('name')); // Alice

// 使用普通对象
const myObject = {};
myObject['name'] = 'Alice';
myObject[123] = 'Bob'; // 数字键会被自动转为字符串
console.log(myObject['name']); // Alice

应用场景：
- 缓存： 存储计算结果，避免重复计算。
- 数据库索引： 快速查找记录。
- 频率统计： 统计数组中元素出现的次数。
- 配置管理： 存储各种配置项及其值。
- 去重： 快速判断元素是否存在。

JavaScript中链表、栈和队列的性能差异及选择考量是什么？

当我们谈到这些数据结构的性能，通常会关注它们在插入、删除和访问操作上的时间复杂度。这直接决定了它们在不同场景下的适用性。

STORYD

帮你写出让领导满意的精美文稿

下载

链表：
- 插入/删除（头部或尾部）： O(1)。这是链表最显著的优势，不需要移动其他元素。
- 插入/删除（中间）： O(N)，需要遍历找到目标位置。
- 访问： O(N)，需要从头开始遍历。
- 选择考量： 当你需要频繁地在数据集合的两端进行插入和删除，且不常需要随机访问元素时，链表是很好的选择。例如，在实现LRU缓存或需要高效管理有序但不固定大小的序列时。我个人觉得，链表在处理动态数据流上，比数组要“优雅”得多。
栈和队列（基于数组实现）：
- 栈（
  push
  /
  pop
  ）： O(1)。JavaScript数组的
```
push
```
  和
```
pop
```
  操作效率很高，因为它们只在数组末尾操作。
- 队列（
  enqueue
  /
  dequeue
  ）：
```
enqueue
```
  (push) 是O(1)。
```
dequeue
```
  (shift) 在最坏情况下是O(N)，因为
```
shift
```
  会移动所有剩余元素。如果使用双端队列（
```
unshift
```
  /
```
pop
```
  ）或者更复杂的实现，
```
dequeue
```
  也能达到O(1)。
- 访问： O(1)（栈顶/队首），O(N)（其他位置）。
- 选择考量：
  - 栈：适合处理具有明确LIFO特性的任务，如回溯、撤销操作、函数调用。由于JS数组的
```
push
```
    /
```
pop
```
    性能优异，基于数组的栈实现非常高效。
  - 队列： 适合处理具有FIFO特性的任务，如任务调度、事件处理。如果对
```
dequeue
```
    的性能有较高要求，需要考虑更优的队列实现（例如使用两个栈、循环数组或链表）。我曾经在项目中因为大量使用
```
shift
```
    导致性能瓶颈，后来改用链表实现的队列，效果立竿见影。
总结： 数组在随机访问上是O(1)，但中间插入/删除是O(N)。链表则在两端插入/删除上是O(1)，但随机访问是O(N)。栈和队列是特定访问模式下的抽象，其底层实现会影响性能。在JavaScript中，数组的内置方法通常经过高度优化，但我们仍需理解其底层原理，避免在不经意间引入性能瓶点。

如何在实际项目中优化哈希表（Map/Object）的性能并避免常见陷阱？

哈希表是JavaScript日常开发中用得最多的数据结构之一，但它的使用也并非没有学问。优化和避免陷阱，主要围绕键的类型、操作方式以及潜在的冲突展开。

选择合适的哈希表类型：
```
Map
```
vs 普通对象
- Map
  的优势：
  - 键可以是任意类型： 不仅仅是字符串或Symbol。你可以用对象、函数甚至另一个Map作为键。这在处理复杂数据作为唯一标识时非常有用。
  - 保留插入顺序：
```
Map
```
    会记住键值对的插入顺序，这在某些需要有序迭代的场景下非常方便。
  - 性能更优： 对于频繁的增删改查操作，
```
Map
```
    通常比普通对象表现更好，尤其是在键的数量较大时。
  - 避免原型链污染：
```
Map
```
    是纯粹的键值对集合，不会受到原型链上的属性影响。
- 普通对象的陷阱：
  - 键被强制转换为字符串： 任何非字符串的键都会被隐式转换为字符串。
```
obj[1] = 'a'
```
    和
```
obj['1'] = 'a'
```
    实际上操作的是同一个键。
  - 原型链属性：
```
Object.prototype
```
    上的一些属性（如
```
constructor
```
    ,
```
toString
```
    ）可能会被意外访问到，导致错误。使用
```
Object.create(null)
```
    可以创建一个“干净”的对象，避免原型链问题。
  - 无序性： 在ES2015之前，普通对象的属性顺序是不确定的。虽然现代JS引擎在数字键和字符串键上有了更明确的排序规则，但
```
Map
```
    提供了更可靠的插入顺序保证。
- 优化建议： 除非你明确知道所有键都是字符串且不需要保留顺序，否则优先考虑使用
```
Map
```
  。它更强大、更安全，也更符合“哈希表”的语义。
避免哈希冲突（JS引擎内部处理，但理解有益）：
- 哈希表的核心是哈希函数，它将键映射到数组索引。当不同的键映射到同一个索引时，就发生了哈希冲突。JavaScript引擎内部会使用各种策略（如链地址法或开放寻址法）来解决冲突。
- 作为开发者，我们通常不需要关心JS引擎如何处理冲突，但理解这一点可以帮助我们明白为什么在某些极端情况下，哈希表的O(1)平均时间复杂度会退化到O(N)（所有键都冲突到同一个桶）。
- 避免方法： 尽量使用多样化的键，避免人为地创建大量相似的键，这有助于哈希函数更好地分散数据。
内存管理：
```
WeakMap
```
和
WeakSet
- 当键是对象且你希望当键对象不再被引用时，其在哈希表中的条目也能被垃圾回收机制自动清除时，
```
WeakMap
```
  和
```
WeakSet
```
  就派上用场了。
- 它们是弱引用，不会阻止垃圾回收器回收键对象。这对于实现一些内部缓存或元数据存储非常有用，可以避免内存泄漏。
- 注意：
```
WeakMap
```
  的键必须是对象，且不可迭代。

总之，使用

Map

通常是更现代、更健壮的选择。理解其与普通对象的差异，并在需要时利用

WeakMap

，能帮助我们写出更高效、更少内存泄漏的代码。

除了基础应用，这些数据结构在前端框架或库中有哪些进阶实践？

这些基础数据结构远不止于教科书上的例子，它们在现代前端框架和库的底层设计中扮演着至关重要的角色，常常以巧妙的形式出现。

链表在React Fiber架构中的应用：
- React 16引入的Fiber架构，其核心思想就是将组件树构建成一个单向链表（Fiber Tree）。每个Fiber节点代表一个工作单元，包含组件实例、状态、props以及指向父节点、子节点和兄弟节点的指针。
- 这种链表结构允许React在渲染过程中暂停、恢复、中断工作，实现异步渲染和时间切片。它不是传统意义上的DOM树，而是一个“工作单元”的链表，使得渲染过程更具弹性。我第一次深入了解Fiber的时候，就被这种将组件抽象成链表节点，通过遍历和操作链表来管理渲染任务的思路惊艳到了。
栈在路由历史管理和撤销/重做中的应用：
- 前端路由： 许多单页应用（SPA）的路由系统，尤其是那些需要支持前进/后退功能的，其内部会维护一个路由历史栈。每次导航都会将当前路由压入栈中，点击后退则从栈中弹出。
- 富文本编辑器： 像Quill、Draft.js这样的富文本编辑器，其撤销（Undo）/重做（Redo）功能通常就是通过维护两个栈来实现的：一个操作栈用于存储用户操作，一个撤销栈用于存储被撤销的操作。
队列在事件循环和异步任务调度中的应用：
- JavaScript事件循环： 这是前端最核心的机制之一。
```
setTimeout
```
  ,
```
setInterval
```
  ,
```
Promise.then
```
  ,
```
queueMicrotask
```
  等异步操作，都会将回调函数放入不同的队列中（宏任务队列、微任务队列），然后由事件循环机制按优先级和顺序从队列中取出并执行。
- 动画帧调度：
```
requestAnimationFrame
```
  的回调也会被放入一个队列，等待浏览器在下一帧重绘前统一执行，以确保动画流畅。
哈希表（Map/Object）在组件状态管理和性能优化中的应用：
- React
  key
  属性：在列表渲染时，React要求我们为每个列表项提供一个唯一的
```
key
```
  。这个
```
key
```
  在内部被React用来高效地识别组件，并利用哈希表快速查找、更新或删除对应的DOM元素，避免不必要的DOM操作。
- 状态管理库： 像Redux这样的状态管理库，其
```
reducer
```
  中通常会使用普通对象或
```
Map
```
  来存储和管理应用程序的状态，通过键值对快速访问和更新特定状态。
- Memoization（记忆化）：
```
React.memo
```
  或
```
useMemo
```
  钩子在内部会使用哈希表（或类似的查找机制）来缓存组件的渲染结果或计算结果。当输入（props或依赖项）不变时，直接返回缓存结果，避免重复渲染或计算，从而提升性能。