当前位置：首页 > JavaScript

js如何实现链表

2026-02-02 19:45:26JavaScript

实现链表的基础结构

在JavaScript中，链表可以通过对象（节点）和引用来实现。每个节点包含两个部分：存储的数据（value）和指向下一个节点的指针（next）。头节点（head）是链表的起点。

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

创建链表实例

初始化一个链表需要创建头节点，并通过next属性连接后续节点。以下是一个包含三个节点的链表示例：

const node1 = new ListNode(1);
const node2 = new ListNode(2);
const node3 = new ListNode(3);

node1.next = node2;
node2.next = node3;

遍历链表

通过循环访问每个节点的next属性，直到遇到null为止，可以遍历链表的所有节点：

let current = node1;
while (current !== null) {
  console.log(current.value);
  current = current.next;
}
// 输出：1 → 2 → 3

插入节点

在链表中插入节点需要调整相邻节点的next指针。例如，在第二个节点后插入一个新节点：

const newNode = new ListNode(4);
newNode.next = node2.next;
node2.next = newNode;

删除节点

删除节点需将前一个节点的next指向被删除节点的下一个节点。例如删除第二个节点：

node1.next = node2.next; // 跳过node2

实现链表类

封装链表操作到一个类中，提供增删查等方法：

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;
  }

  delete(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;
    }
  }
}

反转链表

反转链表需要调整每个节点的next指针方向：

function reverseList(head) {
  let prev = null;
  let current = head;
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  return prev;
}

检测环形链表

使用快慢指针（Floyd判圈算法）判断链表是否有环：

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

链表与数组的转换

将链表转换为数组便于调试或处理：

function listToArray(head) {
  const result = [];
  let current = head;
  while (current) {
    result.push(current.value);
    current = current.next;
  }
  return result;
}