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

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

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中链表、栈和队列的性能差异及选择考量是什么？

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

可图大模型

可图大模型（Kolors）是快手大模型团队自研打造的文生图AI大模型

33

查看详情

• 链表：

  • 插入/删除（头部或尾部）： 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或依赖项）不变时，直接返回缓存结果，避免重复渲染或计算，从而提升性能。

这些例子仅仅是冰山一角。你会发现，这些看似基础的数据结构，在更高层次的抽象和复杂系统中，被巧妙地组合、变形，成为了构建强大、高效前端应用不可或缺的基石。理解它们，就像掌握了设计复杂系统的“语法”，能帮助我们更好地阅读和编写高质量的代码。