JavaScript 数据结构深度解析

JavaScript 作为现代 Web 与 Node.js 的基石，提供了高表达力与高度优化的运行时数据结构：

• 引擎级深度优化：V8 引擎对 Array 采用了基于连续内存（Fast Elements）与字典模式（Dictionary Elements）的自适应转换机制。
• 现代 ES6+ 容器：Map 与 Set 提供了任意键类型支持与常数级查找性能。

---

📊 核心结构与复杂度对照

容器类型	描述与底层模型	典型复杂度	最佳使用建议
Array	动态连续元素缓冲区 / 稀疏字典	索引 $O(1)$，尾部 push/pop $O(1)$	通用列表，头部 shift/unshift 为 $O(n)$
Map	确定插入顺序的哈希字典	增删查平均 $O(1)$	频繁增删键值对的首选
Set	唯一值集合	增删查平均 $O(1)$	元素去重与快速集合运算
二叉搜索树	自定义 Class 指针节点	增删查 $O(\log n)$	树形层次与区间搜索

---

1. 线性结构：动态数组与双端队列 (Array / 双端模拟)

console.log("=== JavaScript Array & Deque Demo ===");
const arr = [10, 20];
arr.push(30);
console.assert(arr.length === 3, "Length assertion failed");
console.assert(arr[1] === 20, "Index assertion failed");
console.assert(arr.pop() === 30, "Pop assertion failed");

const deque = ["center"];
deque.unshift("front");
deque.push("back");
console.assert(deque[0] === "front" && deque[2] === "back", "Deque assertion failed");

console.log("JS Array:", arr, "Deque:", deque);
console.log("JavaScript Dynamic Array tests passed successfully.");

🐳 Docker Verified📋node:22-alpine

Exit Code: 0

=== JavaScript Array & Deque Demo ===
JS Array: [ 10, 20 ] Deque: [ 'front', 'center', 'back' ]
JavaScript Dynamic Array tests passed successfully.

---

2. 树形结构：二叉搜索树 (BST)

class BSTNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  insert(val) {
    const node = new BSTNode(val);
    if (!this.root) {
      this.root = node;
      return;
    }
    let curr = this.root;
    while (true) {
      if (val < curr.val) {
        if (!curr.left) { curr.left = node; break; }
        curr = curr.left;
      } else {
        if (!curr.right) { curr.right = node; break; }
        curr = curr.right;
      }
    }
  }

  search(val) {
    let curr = this.root;
    while (curr) {
      if (curr.val === val) return true;
      curr = val < curr.val ? curr.left : curr.right;
    }
    return false;
  }
}

console.log("=== JavaScript Binary Search Tree ===");
const bst = new BST();
bst.insert(50);
bst.insert(30);
bst.insert(70);

console.assert(bst.search(30) === true, "Search 30 failed");
console.assert(bst.search(99) === false, "Search 99 failed");
console.log("JavaScript BST tests passed successfully.");

🐳 Docker Verified📋node:22-alpine

Exit Code: 0

=== JavaScript Binary Search Tree ===
JavaScript BST tests passed successfully.