JavaScript中链表和树形结构该怎么自己实现？

在JavaScript里，虽然语言本身没有提供专门的链表或树类型，但利用对象引用和类机制，我们完全可以构建出这两种基础数据结构。理解它们的实现方式，对处理有序数据操作以及层级模型有直接的帮助。

一、单向链表的实现

链表由一系列节点组成，每个节点包含自身的数据和指向下一个节点的引用。与数组不同，链表在中间插入或删除元素时不需要移动大量数据，只需修改相邻节点的指向即可。这种特性让它在频繁变动的有序集合中表现更好。

我们先定义节点类和链表类。节点类只负责保存值和下一个节点的链接；链表类维护头节点，并提供添加、查找和删除等方法。下面的代码展示了最基础的单向链表结构：

// 定义链表节点
class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

// 定义单向链表
class LinkedList {
  constructor() {
    this.head = null;
  }

  // 尾部添加节点
  append(value) {
    const newNode = new ListNode(value);
    if (!this.head) {
      this.head = newNode;
      return;
    }
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }

  // 查找节点
  find(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) {
        return current;
      }
      current = current.next;
    }
    return null;
  }

  // 删除节点
  remove(value) {
    if (!this.head) return;
    if (this.head.value === value) {
      this.head = this.head.next;
      return;
    }
    let current = this.head;
    while (current.next) {
      if (current.next.value === value) {
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
  }
}

上述实现中，append方法通过遍历找到尾节点再接入新节点，时间复杂度为O(n)。如果业务场景需要在头部频繁插入，可以额外维护尾指针或直接使用头插法来将复杂度降到O(1)。

链表的缺点也很明显：无法像数组那样通过索引直接访问元素，只能顺序遍历。因此在需要随机访问的场合，数组仍然更合适。我们在选型时应权衡插入删除频率和访问模式。

二、树形结构的基本实现

树用来表达具有层次关系的数据，例如文件目录、组织架构等。最常见的形式是多叉树，其中每个节点拥有零个或多个子节点。在JavaScript中，用子节点数组来保存分支是最直观的做法。

下面给出一个通用的树节点与简单的树操作方法，包括添加子节点和递归打印整棵树。通过递归，我们可以轻松实现深度优先遍历：

// 定义树节点
class TreeNode {
  constructor(value) {
    this.value = value;
    this.children = [];
  }

  // 添加子节点
  addChild(childNode) {
    this.children.push(childNode);
  }

  // 深度优先打印
  print(depth = 0) {
    console.log('  '.repeat(depth) + this.value);
    this.children.forEach(child => child.print(depth + 1));
  }
}

// 使用示例
const root = new TreeNode('根');
const childA = new TreeNode('节点A');
const childB = new TreeNode('节点B');
root.addChild(childA);
root.addChild(childB);
childA.addChild(new TreeNode('节点A-1'));
root.print();

在这个实现里，每个TreeNode通过children数组管理下级节点，结构非常灵活。print方法利用递归逐层缩进输出，清晰展现层级。如果树很深，递归可能导致调用栈溢出，此时可改为显式栈的迭代遍历。

树形结构同样支持多种遍历策略，例如广度优先遍历可以使用队列来实现。相较于链表，树的实现重点在于父子关系的维护和递归思维的应用，而不是指针的频繁改写。

三、链表与树的对比及选用建议

从底层看，链表是线性结构，树是非线性结构。链表适合表达有序序列且插入删除多变的场景；树适合表达归属、包含等层级语义。二者都能用JavaScript对象引用自然表达，不需要依赖原生特殊类型。

实际开发中，如果数据规模不大且操作不复杂，直接使用数组或嵌套对象往往更省事。但当逻辑明显呈现链状或树状特征时，自己实现对应结构可提升代码可读性和运行效率。

掌握这两种结构的手写实现，也是理解更复杂结构如二叉搜索树、图以及前端虚拟DOM差异算法的基础。建议结合小例子反复练习节点链接与递归遍历，直到能不看模板独立写出。

JavaScriptlinked_listtree_structure修改时间：2026-08-04 15:00:33