答案：双向链表通过每个节点的prev和next指针实现前后遍历，支持高效的插入删除操作。结构上包含头尾指针，核心操作有头部插入、尾部插入、删除指定值、正向反向遍历及清空链表，需注意空链表等边界情况处理。
实现一个双向链表需要理解其基本结构：每个节点包含数据、指向前一个节点的指针（prev）和指向下一个节点的指针（next）。相比单向链表，双向链表支持前后双向遍历，插入和删除操作更高效，尤其在已知节点位置时。
定义双向链表节点结构
首先定义链表中的节点类。每个节点保存数据值，并维护两个指针：
struct ListNode {
int data;
ListNode* prev;
ListNode* next;
// 构造函数
ListNode(int value) : data(value), prev(nullptr), next(nullptr) {}};
实现双向链表类
创建一个管理节点的链表类，包含头指针和尾指针，便于在两端高效操作：
class DoublyLinkedList {
private:
ListNode* head;
ListNode* tail;
int size;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
~DoublyLinkedList();
void push_front(int value);
void push_back(int value);
void pop_front();
void pop_back();
void insert(int index, int value);
void remove(int value);
void display_forward();
void display_backward();
bool empty() const;
int get_size() const;
};
核心操作实现
以下是几个关键成员函数的具体实现：
1. 头部插入
在链表头部添加新节点：
void DoublyLinkedList::push_front(int value) {
ListNode* newNode = new ListNode(value);
if (!head) {
head = tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
size++;
}
2. 尾部插入
在链表末尾追加节点：
void DoublyLinkedList::push_back(int value) {
ListNode* newNode = new ListNode(value);
if (!tail) {
head = tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
size++;
}
3. 删除指定值的节点
遍历查找并移除第一个匹配的节点：
void DoublyLinkedList::remove(int value) {
ListNode* current = head;
while (current) {
if (current->data == value) {
if (current == head
) {
pop_front();
} else if (current == tail) {
pop_back();
} else {
current->prev->next = current->next;
current->next->prev = current->prev;
delete current;
size--;
}
return;
}
current = current->next;
}
}
) {
pop_front();
} else if (current == tail) {
pop_back();
} else {
current->prev->next = current->next;
current->next->prev = current->prev;
delete current;
size--;
}
return;
}
current = current->next;
}
}
4. 正向与反向遍历输出
利用双向特性，分别从头到尾和从尾到头打印：
void DoublyLinkedList::display_forward() {
ListNode* current = head;
while (current) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
void DoublyLinkedList::display_backward() {
ListNode* current = tail;
while (current) {
std::cout << current->data << " ";
current = current->prev;
}
std::cout << std::endl;
}
内存管理与析构函数
确保资源正确释放，避免内存泄漏：
DoublyLinkedList::~DoublyLinkedList() {
while (head) {
ListNode* temp = head;
head = head->next;
delete temp;
}
tail = nullptr;
size = 0;
}
基本上就这些。这个实现覆盖了双向链表的基本功能，适合学习和实际应用。注意边界情况处理，比如空链表操作或删除不存在的值。只要理清指针关系，双向链表并不复杂但容易忽略细节。
