在C++中實現雙向鏈表可以通過定義一個ListNode結構體來實現,該結構體包含三個成員變量:值val、指向下一個節點的指針next和指向前一個節點的指針prev。
以下是一個簡單的雙向鏈表的實現示例:
#include <iostream>
struct ListNode {
int val;
ListNode* next;
ListNode* prev;
ListNode(int x) : val(x), next(nullptr), prev(nullptr) {}
};
class DoubleLinkedList {
private:
ListNode* head;
ListNode* tail;
public:
DoubleLinkedList() : head(nullptr), tail(nullptr) {}
void insertAtHead(int val) {
ListNode* newNode = new ListNode(val);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
}
void insertAtTail(int val) {
ListNode* newNode = new ListNode(val);
if (tail == nullptr) {
head = newNode;
tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
}
void printList() {
ListNode* current = head;
while (current != nullptr) {
std::cout << current->val << " ";
current = current->next;
}
std::cout << std::endl;
}
};
int main() {
DoubleLinkedList dl;
dl.insertAtHead(1);
dl.insertAtTail(2);
dl.insertAtTail(3);
dl.printList();
return 0;
}
在上面的示例中,定義了一個DoubleLinkedList類來實現雙向鏈表的基本操作,包括在鏈表頭部插入節點和在鏈表尾部插入節點。通過調用insertAtHead和insertAtTail方法可以向雙向鏈表中插入節點,然后通過printList方法打印出整個鏈表的值。