17370845950

JavaScript中链表需手动实现，核心是用对象模拟节点并通过next指针连接；单向链表节点含val和next，链表类维护head，支持O(1)头插、O(n)尾插及索引操作，需注意空链表和边界处理。

JavaScript中链表不是内置数据结构，需要手动实现节点和操作逻辑。核心是用对象模拟节点，通过next（单向）或next+prev（双向）指针连接，避免数组的连续内存限制，适合频繁增删的场景。

如何构建单向链表节点和链表类

每个节点包含数据和指向下一节点的引用；链表类维护头节点（head），提供增删查等方法。

示例代码：

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

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

常见操作及实现要点

所有操作围绕head展开，注意边界处理（空链表、插入位置越界、删除尾节点等）。

• 插入头部：新建节点，其next指向原head，再更新head；时间复杂度 O(1)
• 插入尾部：遍历到末尾节点，将其next指向新节点；若维护tail属性可优化为 O(1)
• 按索引插入/删除：先遍历到目标前一节点（如插入第i位，需走到i-1），再调整指针；注意检查索引有效性
• 查找值：从head开始逐个比对val，返回节点或索引；不支持随机访问，平均 O(n)
• 反转链表：用三个变量（prev、curr、nextTemp）迭代翻转指针方向；递归写法也常用

双向链表的额外考虑

节点多一个prev属性，插入/删除时需同步更新前后指针。优势是可从尾部高效操作、支持反向遍历，但占用更多内存、逻辑稍复杂。

例如删除节点curr时需：

curr.prev.next = curr.next;
if (curr.next) curr.next.prev = curr.prev;

实用提示与易错点

• 操作前务必判空（this.head === null），尤其删除或查找时避免Cannot read property 'xxx' of null
• 插入/删除后及时更新head（如删头节点）或tail（如维护了尾指针）
• 遍历时用let curr = this.head而非直接操作this.head，防止误改结构
• 调试时可加print()方法，用while循环拼接值，快速验证结构

基本上就这些。链表重在理解指针跳转逻辑，写熟几个基础操作后，合并、环检测、倒数第k节点等进阶题也容易上手。