实现双向链表需定义含数据域和前后指针的节点结构，通过类封装插入、删除、查找和遍历等操作，利用head和tail指针管理链表两端，确保可在O(1)时间完成头尾插入，同时支持双向遍历。
实现一个双向链表的关键在于每个节点保存前驱和后继指针，这样可以从任意方向遍历。C++中通过类封装数据结构，能更好地管理内存和操作逻辑。
定义双向链表节点
每个节点包含三个部分：数据域、指向前面节点的指针和指向后面节点的指针。
struct Node {
int data;
Node* prev;
Node* next;
Node(int value) : data(value), prev(nullptr), next(nullptr) {}};
使用构造函数初始化节点值，并将前后指针设为空，避免野指针问题。
立即学习“C++免费学习笔记（深入）”；
创建双向链表类
封装链表操作，包括插入、删除、查找和遍历等常用功能。
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
~DoublyLinkedList();
void insertFront(int value);
void insertBack(int value);
void remove(int value);
bool find(int value);
void displayForward();
void displayBackward();
};
head 指向第一个节点，tail 指向最后一个节点。构造函数初始化为空链表。
实现基本操作方法
常见操作需要处理空链表、单节点和多节点等多种情况。
头插法：
在链表头部添加新节点。
void DoublyLinkedList::insertFront(int value) {
Node* newNode = new Node(value);
if (!head) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
尾插法：
在链表末尾追加节点。
void DoublyLinkedList::insertBack(int value) {
Node* newNode = new Node(value);
if (!tail) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
}
正向遍历输出：
从头到尾打印所有节点值。
void DoublyLinkedList::displayForward() {
Node* current = head;
while (current) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
反向遍历输出：
利用 prev 指针从尾部回溯。
void DoublyLinkedList::displayBackward() {
Node* current = tail;
while (current) {
std::cout << current->data << " ";
current = current->prev;
}
std::cout << std::endl;
}
析构函数释放资源
手动管理内存时，必须在对象销毁前释放所有节点。
DoublyLinkedList::~DoublyLinkedList() {
Node* current = head;
while (current) {
Node* nextNode = current->next;
delete current;
current = nextNode;
}
}
逐个删除节点，防止内存泄漏。注意保存下一个节点地址再释放当前节点。
基本上就这些。双向链表比单向链表灵活，支持双向访问和高效地在两端插入删除，适合实现双端队列或需要频繁反向遍历的场景。关键点是维护好 prev 和 next 指针的一致性，特别是在删除节点时要小心处理边界情况。
