实现一个双向链表， 具备添加节点、删除节点、在特定位置插入节点、查找节点、遍历等功能

要实现一个双向链表（Doubly Linked List），需要定义一个节点类和一个链表类。

双向链表中的每个节点都有两个指针，一个指向下一个节点（next），一个指向上一个节点（prev）。

链表类则包含了各种操作链表的方法，如添加节点、删除节点、在特定位置插入节点、查找节点和遍历链表。

以下是一个实现双向链表的示例：

1. 节点类（Node Class）

class Node {
  constructor(data) {
    this.data = data; // 节点存储的数据
    this.next = null; // 指向下一个节点的指针
    this.prev = null; // 指向上一个节点的指针
  }
}

2. 双向链表类（DoublyLinkedList Class）

class DoublyLinkedList {
  constructor() {
    this.head = null; // 链表的头节点
    this.tail = null; // 链表的尾节点
    this.size = 0; // 链表的节点数量
  }

  // 添加节点到链表的末尾
  append(data) {
    const newNode = new Node(data);
    if (this.head === null) {
      // 链表为空时，新节点是头节点和尾节点
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 链表非空时，更新尾节点的指针
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.size++;
  }

  // 在特定位置插入节点
  insertAt(position, data) {
    if (position < 0 || position > this.size) {
      throw new Error("Index out of bounds");
    }

    const newNode = new Node(data);

    if (position === 0) {
      // 插入到链表的头部
      if (this.head === null) {
        this.head = newNode;
        this.tail = newNode;
      } else {
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
      }
    } else if (position === this.size) {
      // 插入到链表的尾部
      this.append(data);
    } else {
      // 插入到链表的中间
      let current = this.head;
      for (let i = 0; i < position - 1; i++) {
        current = current.next;
      }
      newNode.next = current.next;
      newNode.prev = current;
      current.next.prev = newNode;
      current.next = newNode;
    }
    this.size++;
  }

  // 删除特定位置的节点
  removeAt(position) {
    if (position < 0 || position >= this.size) {
      throw new Error("Index out of bounds");
    }

    if (position === 0) {
      // 删除头节点
      if (this.head === this.tail) {
        // 只有一个节点
        this.head = null;
        this.tail = null;
      } else {
        this.head = this.head.next;
        this.head.prev = null;
      }
    } else if (position === this.size - 1) {
      // 删除尾节点
      this.tail = this.tail.prev;
      this.tail.next = null;
    } else {
      // 删除中间节点
      let current = this.head;
      for (let i = 0; i < position; i++) {
        current = current.next;
      }
      current.prev.next = current.next;
      current.next.prev = current.prev;
    }
    this.size--;
  }

  // 查找特定节点
  find(data) {
    let current = this.head;
    while (current) {
      if (current.data === data) {
        return current;
      }
      current = current.next;
    }
    return null; // 没有找到
  }

  // 遍历链表并打印节点数据
  traverse() {
    let current = this.head;
    while (current) {
      console.log(current.data);
      current = current.next;
    }
  }

  // 从尾部开始遍历链表并打印节点数据
  traverseReverse() {
    let current = this.tail;
    while (current) {
      console.log(current.data);
      current = current.prev;
    }
  }
}

用法示例

const list = new DoublyLinkedList();

list.append(1);
list.append(2);
list.append(3);
list.insertAt(1, 4); // 链表现在是 1 -> 4 -> 2 -> 3
list.traverse(); // 输出: 1, 4, 2, 3

list.removeAt(1); // 链表现在是 1 -> 2 -> 3
list.traverse(); // 输出: 1, 2, 3

console.log(list.find(2)); // 输出: Node { data: 2, next: Node { ... }, prev: Node { ... } }

list.traverseReverse(); // 输出: 3, 2, 1