js 实现链表

链表的基本概念

链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。与数组不同，链表在内存中是非连续存储的，插入和删除操作效率较高。

链表的实现

在 JavaScript 中，链表可以通过对象和引用来实现。以下是链表的常见操作实现方式。

定义链表节点

链表的基本单位是节点，每个节点包含数据（value）和指向下一个节点的指针（next）。

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

创建链表

可以通过实例化多个 ListNode 并设置 next 指针来创建链表。

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

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

遍历链表

使用循环从链表头部开始依次访问每个节点。

let current = node1;
while (current !== null) {
  console.log(current.value);
  current = current.next;
}

插入节点

在链表中插入节点需要调整相邻节点的指针。

在头部插入：

const newNode = new ListNode(0);
newNode.next = node1;
const head = newNode;

在中间插入：

const newNode = new ListNode(1.5);
newNode.next = node2;
node1.next = newNode;

删除节点

删除节点需要将被删除节点的前驱节点的 next 指向被删除节点的后继节点。

// 删除 node2
node1.next = node3;

完整链表类实现

可以将链表封装为一个类，提供常用操作方法。

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

  // 删除指定值的节点
  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;
    }
  }

  // 查找节点
  find(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) {
        return current;
      }
      current = current.next;
    }
    return null;
  }

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

示例用法

const list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.prepend(0);
list.delete(2);
console.log(list.find(3)); // 输出节点 { value: 3, next: null }
console.log(list.getSize()); // 输出 3

双向链表实现

双向链表的每个节点包含指向前驱和后继节点的指针。

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

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

  append(value) {
    const newNode = new DoublyListNode(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }
}

循环链表实现

循环链表的尾节点指向头节点，形成一个环。

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

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