当前位置：首页 > JavaScript

链表实现js

2026-02-28 20:09:18JavaScript

链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。与数组不同，链表在内存中是非连续存储的，动态增删节点更高效。

单向链表的实现

定义节点类 每个节点包含 value 和 next 属性，next 指向下一个节点或 null（尾节点）。

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

初始化链表 创建头节点并逐步追加节点。

const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);

链表常用操作

遍历链表 通过循环访问每个节点，直到 next 为 null。

let current = head;
while (current !== null) {
  console.log(current.value);
  current = current.next;
}

插入节点 在指定位置插入新节点，需调整相邻节点的 next 指针。

function insertAfter(prevNode, value) {
  const newNode = new ListNode(value);
  newNode.next = prevNode.next;
  prevNode.next = newNode;
}

删除节点 修改前驱节点的 next 指针以跳过待删除节点。

function deleteNode(head, value) {
  if (head.value === value) return head.next;
  let current = head;
  while (current.next !== null) {
    if (current.next.value === value) {
      current.next = current.next.next;
      return head;
    }
    current = current.next;
  }
  return head;
}

双向链表的实现

双向链表的节点包含指向前驱和后继的指针。

class DoublyListNode {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

插入操作示例 需同时维护 prev 和 next 指针。

链表实现js

function insertAfter(node, value) {
  const newNode = new DoublyListNode(value);
  newNode.next = node.next;
  newNode.prev = node;
  if (node.next) node.next.prev = newNode;
  node.next = newNode;
}