javascript中的数据结构有哪些_如何实现链表或二叉树-js教程-PHP中文网

javascript中的数据结构有哪些_如何实现链表或二叉树

幻影之瞳

发布： 2025-12-15 09:51:09

原创

312人浏览过

JavaScript无内置链表、队列、栈、二叉树等结构，需用对象/数组/函数模拟；常见需手写的是单向/双向链表、BST、堆、图；如单向链表用ListNode和LinkedList类实现头尾插入与查找，BST通过递归插入和中序遍历支持有序操作。

javascript中的数据结构有哪些_如何实现链表或二叉树

JavaScript 中没有内置的链表、队列、栈、二叉树等经典数据结构，但可以用对象、数组和函数灵活模拟。核心在于理解结构逻辑，再用原生语法实现。

常见可手写的数据结构类型

虽然 JS 提供了 Array（可当栈/队列用）、Map（哈希表）、Set（去重集合），但以下结构需手动实现：

单向/双向链表（插入删除 O(1)，查找 O(n)）
二叉搜索树（BST，支持有序遍历和对数级查找）
堆（最小堆/最大堆，用于优先队列）
图（邻接表或邻接矩阵表示）

如何实现一个单向链表

每个节点包含 value 和指向下一个节点的 next 引用。重点是维护头节点（head）和操作逻辑。

示例代码：

立即学习“Java免费学习笔记（深入）”；

星声AI

可分享的AI播客内容生成器和效率工具

185

查看详情

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  // 头部插入
  prepend(val) {
    this.head = new ListNode(val, this.head);
  }

  // 尾部插入
  append(val) {
    if (!this.head) {
      this.head = new ListNode(val);
      return;
    }
    let node = this.head;
    while (node.next) node = node.next;
    node.next = new ListNode(val);
  }

  // 查找值
  find(val) {
    let node = this.head;
    while (node && node.val !== val) node = node.next;
    return node;
  }
}

登录后复制

如何实现一个二叉搜索树（BST）

BST 要求：左子树所有节点值

示例代码：

立即学习“Java免费学习笔记（深入）”；

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

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

  insert(val) {
    this.root = this._insertNode(this.root, val);
  }

  _insertNode(node, val) {
    if (!node) return new TreeNode(val);
    if (val < node.val) {
      node.left = this._insertNode(node.left, val);
    } else if (val > node.val) {
      node.right = this._insertNode(node.right, val);
    }
    return node; // 重复值不插入
  }

  // 中序遍历：左→根→右 → 输出升序数组
  inorder() {
    const result = [];
    function traverse(node) {
      if (!node) return;
      traverse(node.left);
      result.push(node.val);
      traverse(node.right);
    }
    traverse(this.root);
    return result;
  }
}

登录后复制

实际使用建议

不要为了“炫技”在业务中硬套手写结构。多数场景下：

用 Array + push/pop 模拟栈；shift/push 模拟队列（注意 shift 是 O(n)，高频队列可用双端队列思路优化）
需要排序+查范围？考虑 Array.sort() + 二分查找（如用 lowerBound）更简单可靠
真有性能瓶颈（如大量增删+有序遍历），再引入 BST 或用现成库如 tinyqueue（最小堆）