javascript如何实现数据结构_链表和二叉树如何实现

admin 百科 2025-12-16 12

JavaScript中链表和二叉树通过对象属性（如next、left、right）模拟指针实现，无需底层内存操作；链表以head为入口，BST按大小关系插入左右子节点，核心在于引用建模与递归/迭代逻辑。

javascript如何实现数据结构_链表和二叉树如何实现-第1张图片-佛山资讯网

JavaScript 中实现链表和二叉树，核心是用对象（或类）模拟节点结构，通过引用（指针）连接节点。不需要底层内存操作，靠 next、left、right 等属性维护逻辑关系。

链表：单向链表的实现

每个节点包含数据和指向下一个节点的引用。头节点（head）是入口，尾节点的 next 为 null。

基础实现：

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) {
    const newNode = new ListNode(val);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let curr = this.head;
    while (curr.next) curr = curr.next;
    curr.next = newNode;
  }

  // 遍历打印
  traverse() {
    const values = [];
    let curr = this.head;
    while (curr) {
      values.push(curr.val);
      curr = curr.next;
    }
    return values;
  }
}

// 使用示例
const list = new LinkedList();
list.append(1);
list.append(2);
list.prepend(0);
console.log(list.traverse()); // [0, 1, 2]

登录后复制