双向链表（Doubly Linked List）是一种常见的线性数据结构，与传统的单向链表不同，双向链表中的每个节点除了包含一个指向下一个节点的指针外，还包含一个指向前一个节点的指针。这种双向连接的特性使得双向链表在某些情况下更加灵活和方便，但也带来了额外的空间开销。
概念与特点
双向链表由一系列节点组成，每个节点包含三个主要部分：
数据元素：存储节点所需的数据。
指向前驱节点的指针：指向链表中的前一个节点。
指向后继节点的指针：指向链表中的后一个节点。
这种前后连接的结构使得双向链表可以在某些场景下更高效地进行双向遍历，而无需从头节点开始遍历。
操作
双向链表支持一系列常见的操作，包括插入、删除和遍历等。
插入操作
在双向链表中插入一个新节点需要以下步骤：
创建一个新节点，并设置其数据。
将新节点的前驱指针指向待插入位置的前一个节点。
将新节点的后继指针指向待插入位置的后一个节点。
更新待插入位置的前一个节点的后继指针，将其指向新节点。
更新待插入位置的后一个节点的前驱指针，将其指向新节点。
删除操作
在双向链表中删除一个节点需要以下步骤：
找到待删除节点。
更新待删除节点的前一个节点的后继指针，将其指向待删除节点的后一个节点。
更新待删除节点的后一个节点的前驱指针，将其指向待删除节点的前一个节点。
删除待删除节点。
遍历操作
双向链表可以从前往后或从后往前遍历。从前往后遍历可以通过跟随每个节点的后继指针实现，而从后往前遍历则可以通过跟随每个节点的前驱指针实现。
双向链表与树的关系
尽管双向链表和树是不同的数据结构，但它们之间存在一些相似之处和联系。特别是在树的实现中，有时可以使用双向链表的思想来简化树节点之间的连接关系。
当我们考虑二叉搜索树（Binary Search Tree，BST）。在BST中，每个节点都有一个值，并且左子树中的节点值小于当前节点的值，右子树中的节点值大于当前节点的值。对于一个BST，可以使用双向链表的概念来实现一个中序遍历（Inorder Traversal）序列，其中节点的前驱节点即为左子树中的右下节点，后继节点为右子树中的左上节点。这样，就可以通过修改节点的指针，将整个BST转化为一个有序的双向链表。
这种树和链表之间的关系在一些特定应用中非常有用。我们在数据库系统中，可以使用类似的思想来优化范围查询操作，从而提高查询效率。
这里我们简单用C++来简述双向链表：
#include <iostream>
class Node {
public:
int data;
Node* prev;
Node* next;
Node(int value) : data(value), prev(nullptr), next(nullptr) {}
};
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
void insertFront(int value) {
Node* newNode = new Node(value);
if (!head) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
void insertEnd(int value) {
Node* newNode = new Node(value);
if (!tail) {
head = tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
}
void display() {
Node* current = head;
while (current) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
~DoublyLinkedList() {
Node* current = head;
while (current) {
Node* next = current->next;
delete current;
current = next;
}
}
};
int main() {
DoublyLinkedList dll;
dll.insertEnd(1);
dll.insertEnd(2);
dll.insertFront(0);
dll.display(); // Output: 0 1 2
return 0;
}
双向链表在需要同时考虑前后关系的情况下具有优势，虽然相较于单向链表增加了一些额外的指针操作，但它提供了更多的灵活性和便利性。在选择使用链表作为数据结构时，根据实际情况选用单向链表还是双向链表能够更好地满足需求。而双向链表与树之间的关系则展示了数据结构之间的契合与转化。
最后笔者再用灵魂字符来给大家呈现下他的过程
null <-> A <-> B <-> C <-> D <-> null
在这个示意图中，每个节点由一个大写字母表示，箭头表示指针的方向。箭头的左侧表示前驱指针，箭头的右侧表示后继指针。链表的头节点之前和尾节点之后的箭头指向null，表示链表的开始和结束。
其中节点A是头节点，节点D是尾节点。节点A的后继指向节点B，节点B的前驱指向节点A，以此类推。节点D的后继指向null，表示链表的结束。
