JavaScript 双向链表

双向链表是一种数据结构，它允许在链表的任何位置高效地插入和删除节点。与单向链表相比，双向链表中的每个节点不仅存储了指向下一个节点的指针，还存储了一个指向前一个节点的指针。

定义双向链表节点

双向链表的基本组成是节点，每个节点包含三个部分：数据、指向下一个节点的指针和指向前一个节点的指针。

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

创建双向链表类

接下来，我们创建一个双向链表类，该类将包含对链表进行操作的方法。

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

在双向链表末尾添加元素

在双向链表中添加元素到末尾是最常见的操作之一。这个方法首先检查链表是否为空，然后决定如何添加新元素。

// www.javascriptcn.com code example
addAtEnd(data) {
    const newNode = new Node(data);
    if (!this.head) { // 如果链表为空
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
    }
    this.size++;
}

在双向链表开头添加元素

除了在链表末尾添加元素外，还可以在开头添加元素。这同样是一个常见的操作，用于快速增加元素。

// www.javascriptcn.com code example
addAtBeginning(data) {
    const newNode = new Node(data);
    if (!this.head) { // 如果链表为空
        this.head = newNode;
        this.tail = newNode;
    } else {
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
    }
    this.size++;
}

在指定位置添加元素

在双向链表中，还可以根据索引值来添加新的节点。需要注意的是，这个操作需要遍历链表直到找到指定位置。

// www.javascriptcn.com code example
insertAt(index, data) {
    if (index < 0 || index > this.size) return;
    let newNode = new Node(data);
    if (index === 0) {
        this.addAtBeginning(data);
    } else if (index === this.size) {
        this.addAtEnd(data);
    } else {
        let currentNode = this.head;
        for (let i = 0; i < index - 1; i++) {
            currentNode = currentNode.next;
        }
        newNode.next = currentNode.next;
        newNode.prev = currentNode;
        currentNode.next.prev = newNode;
        currentNode.next = newNode;
        this.size++;
    }
}

删除双向链表中的元素

删除链表中的元素同样分为几种情况：删除头部节点、删除尾部节点以及删除中间的节点。

// www.javascriptcn.com code example
removeAt(index) {
    if (index < 0 || index >= this.size) return;
    let currentNode = this.head;
    if (index === 0) { // 删除头结点
        this.head = this.head.next;
        if (this.head) this.head.prev = null;
        else this.tail = null;
    } else if (index === this.size - 1) { // 删除尾结点
        this.tail = this.tail.prev;
        this.tail.next = null;
    } else {
        for (let i = 0; i < index; i++) {
            currentNode = currentNode.next;
        }
        currentNode.prev.next = currentNode.next;
        currentNode.next.prev = currentNode.prev;
    }
    this.size--;
}

查找双向链表中的元素

查找链表中的元素也是一个基本的操作。可以通过遍历链表直到找到目标值或者遍历到链表末尾。

// www.javascriptcn.com code example
find(data) {
    let currentNode = this.head;
    while (currentNode) {
        if (currentNode.data === data) {
            return currentNode;
        }
        currentNode = currentNode.next;
    }
    return null;
}

遍历双向链表

遍历双向链表可以从前向后遍历，也可以从后向前遍历。

// www.javascriptcn.com code example
traverseForward(callback) {
    let currentNode = this.head;
    while (currentNode) {
        callback(currentNode.data);
        currentNode = currentNode.next;
    }
}

traverseBackward(callback) {
    let currentNode = this.tail;
    while (currentNode) {
        callback(currentNode.data);
        currentNode = currentNode.prev;
    }
}

以上就是关于双向链表的一些基础操作，通过这些方法我们可以实现对双向链表的各种操作，从而满足不同的应用场景。