当前位置：首页 > JavaScript

js实现链表

2026-04-05 13:43:03JavaScript

实现链表的基本结构

在JavaScript中，链表可以通过对象和引用来实现。每个节点包含一个值（value）和一个指向下一个节点的指针（next）。

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

创建链表类

链表类通常包含头节点（head）和一些基本操作方法，如插入、删除和遍历。

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

插入节点

插入节点分为头部插入和尾部插入两种常见方式。

头部插入
新节点成为链表的头节点，原头节点成为新节点的下一个节点。

js实现链表

insertAtHead(value) {
  const newNode = new ListNode(value);
  newNode.next = this.head;
  this.head = newNode;
  this.size++;
}

尾部插入
遍历链表找到最后一个节点，将新节点添加到末尾。

insertAtTail(value) {
  const newNode = new ListNode(value);
  if (!this.head) {
    this.head = newNode;
  } else {
    let current = this.head;
    while (current.next) {
      current = current.next;
    }
    current.next = newNode;
  }
  this.size++;
}

删除节点

删除指定值的节点需要遍历链表，找到目标节点并调整指针。

js实现链表

deleteNode(value) {
  if (!this.head) return;
  if (this.head.value === value) {
    this.head = this.head.next;
    this.size--;
    return;
  }
  let current = this.head;
  while (current.next) {
    if (current.next.value === value) {
      current.next = current.next.next;
      this.size--;
      return;
    }
    current = current.next;
  }
}

遍历链表

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

traverse() {
  let current = this.head;
  while (current) {
    console.log(current.value);
    current = current.next;
  }
}

查找节点

查找链表中是否存在某个值，返回布尔值或节点。

contains(value) {
  let current = this.head;
  while (current) {
    if (current.value === value) {
      return true;
    }
    current = current.next;
  }
  return false;
}

反转链表

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

reverse() {
  let prev = null;
  let current = this.head;
  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }
  this.head = prev;
}

示例用法

const list = new LinkedList();
list.insertAtTail(1);
list.insertAtTail(2);
list.insertAtTail(3);
list.traverse(); // 输出: 1 2 3
list.reverse();
list.traverse(); // 输出: 3 2 1
list.deleteNode(2);
list.traverse(); // 输出: 3 1

以上代码实现了链表的基本功能，包括插入、删除、遍历和反转。链表在JavaScript中常用于实现队列、栈或其他需要动态大小的数据结构。