怎样在JavaScript中实现链表操作？

链表是一种非连续存储的线性数据结构，由一系列节点组成，每个节点包含数据域和指向下一个节点的指针。在JavaScript中没有原生的链表类型，我们可以通过对象模拟节点，再封装链表类来实现完整的链表操作。

链表节点的定义

链表的每个节点需要存储当前节点的数据，以及指向下一个节点的引用，我们可以通过构造函数或者类来定义节点结构：

// 定义链表节点类
class ListNode {
  constructor(val) {
    this.val = val; // 节点存储的数据
    this.next = null; // 指向下一个节点的指针，初始为null
  }
}

链表类的实现

我们可以封装一个链表类，内部维护头节点和链表长度，对外提供插入、删除、遍历等操作接口：

class LinkedList {
  constructor() {
    this.head = null; // 链表的头节点
    this.size = 0; // 链表长度
  }

  // 向链表尾部添加节点
  append(val) {
    const newNode = new ListNode(val);
    if (this.head === null) {
      // 如果链表为空，新节点作为头节点
      this.head = newNode;
    } else {
      // 否则遍历到链表尾部，将尾节点的next指向新节点
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = new ListNode(val);
    }
    this.size++;
  }

  // 在指定位置插入节点，index从0开始
  insert(val, index) {
    if (index < 0 || index > this.size) {
      return false; // 插入位置不合法
    }
    const newNode = new ListNode(val);
    if (index === 0) {
      // 插入到头部，新节点的next指向原来的头节点，再更新头节点
      newNode.next = this.head;
      this.head = newNode;
    } else {
      // 找到插入位置的前一个节点
      let prev = this.head;
      for (let i = 0; i < index - 1; i++) {
        prev = prev.next;
      }
      newNode.next = prev.next;
      prev.next = newNode;
    }
    this.size++;
    return true;
  }

  // 删除指定位置的节点
  removeAt(index) {
    if (index < 0 || index >= this.size || this.head === null) {
      return null; // 删除位置不合法或链表为空
    }
    let removedNode;
    if (index === 0) {
      // 删除头节点，更新头节点为下一个节点
      removedNode = this.head;
      this.head = this.head.next;
    } else {
      // 找到要删除节点的前一个节点
      let prev = this.head;
      for (let i = 0; i < index - 1; i++) {
        prev = prev.next;
      }
      removedNode = prev.next;
      prev.next = removedNode.next;
    }
    this.size--;
    return removedNode.val;
  }

  // 遍历链表，返回所有节点的值组成的数组
  traverse() {
    const result = [];
    let current = this.head;
    while (current !== null) {
      result.push(current.val);
      current = current.next;
    }
    return result;
  }

  // 获取链表长度
  getSize() {
    return this.size;
  }
}

链表操作测试

完成链表类的实现后，我们可以通过以下代码测试各个操作是否符合预期：

// 创建链表实例
const list = new LinkedList();
// 添加节点
list.append(10);
list.append(20);
list.append(30);
console.log(list.traverse()); // 输出 [10, 20, 30]
console.log(list.getSize()); // 输出 3

// 在位置1插入节点
list.insert(15, 1);
console.log(list.traverse()); // 输出 [10, 15, 20, 30]

// 删除位置2的节点
list.removeAt(2);
console.log(list.traverse()); // 输出 [10, 15, 30]
console.log(list.getSize()); // 输出 3

核心操作注意事项

• 插入和删除操作需要特别注意边界情况，比如操作头节点、空链表、索引越界等情况的判断。
• 遍历链表时需要用临时变量保存当前节点，避免直接修改头节点引用导致链表结构被破坏。
• 每次插入或删除节点后，都要同步更新链表的size属性，保证长度统计准确。

链表与数组的对比

JavaScript链表操作数据结构节点定义修改时间：2026-06-06 07:35:02