17370845950

JavaScript数据结构需依操作模式选择：查多用哈希（Map/Object），删多用链表，有序少变更用数组，层级深用树；栈用push/pop，队列优选双端链表或双栈，链表注意内存泄漏，树结构助于理解嵌套数据与算法。

JavaScript 数据结构的实现与应用，核心在于理解底层逻辑并结合语言特性合理封装。原生 JavaScript 没有内置的栈、队列、链表等类型，但可通过数组、对象或类灵活构建，关键不是“造轮子”，而是明确何时用、怎么用更安全高效。

用数组模拟栈和队列

数组的 push/pop 天然支持后进先出（栈），push/shift 或 unshift/pop 可模拟先进先出（队列）。注意 shift() 会重排索引，大数据量时性能较差，生产环境队列建议用双端链表或两个栈实现。

• 栈：const stack = []; stack.push(1); stack.pop();
• 简单队列：const queue = []; queue.push(1); queue.shift();
• 高性能队列：维护 head/tail 指针，用数组下标代替删除操作

链表需手动管理节点引用

JavaScript 中链表不依赖内存地址，靠对象引用连接。每个节点是 { value, next } 形式，插入删除时间复杂度 O(1)，但查找为 O(n)。适合频繁增删、顺序访问的场景，比如实现 LRU 缓存或浏览器历史记录。

• 单向链表：删除节点需从头遍历找到前驱；双向链表可直接通过 prev/next 调整
• 避免内存泄漏：删除节点时设 node.next = null，帮助 GC 回收
• 实际项目中可用 Map + 对象模拟双向链表（如 React 的 fiber 链表）

哈希表靠对象和 Map 实现

Object 是最简哈希表，但键只能是字符串或 Symbol；Map 更通用，支持任意类型作键，且保持插入顺序。两者都提供 O(1) 平均查找，常用于去重、计数、缓存（如 memoize 函数）。

• 计数统计：const count = new Map(); count.set('a', (count.get('a') || 0) + 1)
• 避免 Object 原型污染：优先用 Map，尤其键不确定时
• Set 是 Map 的简化版，适合仅需唯一值的场景（如数组去重）

树结构多用于嵌套关系与算法题

二叉搜索树（BST）、AVL、红黑树在 JS 中极少手写（V8 引擎内部已优化 Map/Set），但理解其结构对处理文件目录、DOM 树、JSON Schema、前端权限菜单等嵌套数据很有帮助。递归遍历是最自然的访问方式。

• 扁平数据转树：按 parent_id 建立映射表，一次遍历完成父子关联
• 虚拟滚动列表常用线段树思想做区间查询
• AST 解析、状态机、路由匹配都隐含树或图的结构

不复杂但容易忽略：数据结构的选择往往取决于操作模式——查得多用哈希，删得多用链表，有序且变少用数组，层级深用树。写代码前先问自己“主要操作是什么”，再决定用什么结构封装，而不是一上来就堆 class Node。