JavaScript 双向链表操作实例分析【创建、增加、查找、删除等】

下面就是 JavaScript 双向链表的完整攻略：

什么是双向链表

双向链表是一种链式数据结构，每个节点都包含两个指向前后节点的指针。相对于单向链表，双向链表可以在 O(1) 时间复杂度下进行前后节点的查找、插入、删除等操作。

双向链表的结构

• Node: 双向链表的节点，包含三个属性
  • data: 存储节点的数据
  • prev: 指向前一个节点的指针
  • next: 指向下一个节点的指针
• DoublyLinkedList: 双向链表，包含两个属性
  • head: 指向链表头部的指针
  • tail: 指向链表尾部的指针

双向链表的操作

创建一个双向链表

创建一个双向链表需要定义一个 DoublyLinkedList 类，该类包含两个属性：头节点 head 和尾节点 tail。在创建过程中，head 和 tail 都是 null，表示链表为空。我们可以定义以下代码：

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

在双向链表尾部插入一个节点

在双向链表尾部插入一个节点需要做以下事情：

1. 创建一个新节点，该节点的 data 属性为插入的数据，prev 指针为上一个节点，next 指针为 null。
2. 判断链表是否为空。如果链表为空，则将新节点设置为头节点和尾节点。
3. 如果链表不为空，则将新节点插入到链表的尾部，即将新节点的 prev 指针设为链表的尾节点，把尾节点的 next 指针设为新节点，然后更新链表的尾节点为新节点。

可以参考以下代码：

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

  // 在链表尾部插入一个节点
  insertAtTail(data) {
    const newNode = {
      data: data,
      prev: null,
      next: null
    };

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }
}

在双向链表中查找一个节点

在双向链表中查找一个节点需要遍历链表，逐个比对节点的值，直到找到匹配的节点或遍历到链表末尾。操作可参考以下代码：

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

  // 在链表尾部插入一个节点
  insertAtTail(data) {
    const newNode = {
      data: data,
      prev: null,
      next: null
    };

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  // 查找一个节点
  searchNode(data) {
    let currentNode = this.head;

    while (currentNode) {
      if (currentNode.data === data) {
        return currentNode;
      }
      currentNode = currentNode.next;
    }

    return null;
  }
}

以上就是双向链表的创建、插入和查找的攻略和示例。删除操作的实现原理跟单向链表类似，可以自行尝试实现。