js中如何实现单链表

单链表的基本概念

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

定义节点类

使用class或构造函数定义链表节点，每个节点包含value（存储数据）和next（指向下一个节点）属性。

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

创建链表实例

初始化链表时，通常需要定义头节点（head）和尾节点（tail），初始时链表为空。

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

实现插入操作

头部插入：将新节点作为链表的头节点，并更新head指针。

insertAtHead(value) {
  const newNode = new ListNode(value);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    newNode.next = this.head;
    this.head = newNode;
  }
  this.length++;
}

尾部插入：将新节点追加到链表末尾，并更新tail指针。

insertAtTail(value) {
  const newNode = new ListNode(value);
  if (!this.head) {
    this.head = newNode;
    this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.length++;
}

实现删除操作

删除头部节点：移除头节点并更新head指针。

deleteAtHead() {
  if (!this.head) return null;
  const removedValue = this.head.value;
  this.head = this.head.next;
  this.length--;
  if (this.length === 0) this.tail = null;
  return removedValue;
}

删除尾部节点：遍历链表找到倒数第二个节点，更新其next指针。

deleteAtTail() {
  if (!this.head) return null;
  let current = this.head;
  let removedValue;
  if (this.length === 1) {
    removedValue = this.head.value;
    this.head = null;
    this.tail = null;
  } else {
    while (current.next !== this.tail) {
      current = current.next;
    }
    removedValue = this.tail.value;
    current.next = null;
    this.tail = current;
  }
  this.length--;
  return removedValue;
}

遍历链表

通过循环从头节点开始依次访问每个节点。

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

查找节点

根据值或索引查找链表中的节点。

findByValue(value) {
  let current = this.head;
  while (current) {
    if (current.value === value) return current;
    current = current.next;
  }
  return null;
}

findByIndex(index) {
  if (index < 0 || index >= this.length) return null;
  let current = this.head;
  for (let i = 0; i < index; i++) {
    current = current.next;
  }
  return current;
}

链表反转

通过迭代或递归反转链表。

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

示例用法

const list = new LinkedList();
list.insertAtTail(1);
list.insertAtTail(2);
list.insertAtHead(0);
list.traverse(); // 输出: 0, 1, 2
list.reverse();
list.traverse(); // 输出: 2, 1, 0

通过上述方法，可以实现单链表的基本操作，包括插入、删除、遍历和反转等。