当前位置：首页 > JavaScript

js中如何实现单链表

2026-01-31 07:41:31JavaScript

单链表的基本概念

单链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的头节点是访问整个链表的起点，尾节点的指针通常指向null。

单链表的节点定义

在JavaScript中，可以通过类或构造函数定义链表节点。每个节点包含value（存储数据）和next（指向下一个节点的指针）。

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

单链表的实现

以下是单链表的完整实现，包含插入、删除、查找等基本操作。

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

  // 在链表尾部添加节点
  append(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++;
  }

  // 在链表头部添加节点
  prepend(value) {
    const newNode = new ListNode(value);
    newNode.next = this.head;
    this.head = newNode;
    this.size++;
  }

  // 在指定位置插入节点
  insertAt(value, index) {
    if (index < 0 || index > this.size) return false;
    if (index === 0) {
      this.prepend(value);
      return true;
    }
    const newNode = new ListNode(value);
    let current = this.head;
    let previous = null;
    let i = 0;
    while (i < index) {
      previous = current;
      current = current.next;
      i++;
    }
    newNode.next = current;
    previous.next = newNode;
    this.size++;
    return true;
  }

  // 删除指定位置的节点
  removeAt(index) {
    if (index < 0 || index >= this.size) return null;
    let current = this.head;
    if (index === 0) {
      this.head = current.next;
    } else {
      let previous = null;
      let i = 0;
      while (i < index) {
        previous = current;
        current = current.next;
        i++;
      }
      previous.next = current.next;
    }
    this.size--;
    return current.value;
  }

  // 查找节点值是否存在
  contains(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) return true;
      current = current.next;
    }
    return false;
  }

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

  // 打印链表
  print() {
    let current = this.head;
    const values = [];
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    console.log(values.join(' -> '));
  }
}

使用示例

以下是单链表的简单使用示例：

const list = new LinkedList();
list.append(10); // 链表: 10
list.append(20); // 链表: 10 -> 20
list.prepend(5); // 链表: 5 -> 10 -> 20
list.insertAt(15, 2); // 链表: 5 -> 10 -> 15 -> 20
list.removeAt(1); // 链表: 5 -> 15 -> 20
console.log(list.contains(15)); // true
console.log(list.getSize()); // 3
list.print(); // 5 -> 15 -> 20