当前位置：首页 > JavaScript

js中如何实现单链表

2026-04-04 23:41:40JavaScript

单链表的基本概念

单链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。最后一个节点的指针指向null，表示链表结束。

定义链表节点

使用class或构造函数定义节点，每个节点包含value（数据）和next（指向下一个节点的指针）。

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

创建链表类

定义一个链表类，包含头节点（head）和基础操作方法。

js中如何实现单链表

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0; // 可选：记录链表长度
  }
}

插入节点

头部插入：将新节点作为链表的头节点。

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

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

js中如何实现单链表

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

删除节点

删除指定值节点：遍历链表找到目标节点，调整指针跳过该节点。

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

查找节点

遍历链表，检查是否存在匹配的值。

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

打印链表

将链表的值转换为数组或字符串输出。

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

完整示例

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

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

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

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

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

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

  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.insertLast(1);
list.insertLast(2);
list.insertFirst(0);
list.print(); // 输出: 0 -> 1 -> 2
list.delete(1);
list.print(); // 输出: 0 -> 2