如何在C++中高效地实现一个双向链表,并进行基本操作如插入、删除和遍历?请提供示例代码。
时间: 2024-12-07 12:34:19 浏览: 15
双向链表是一种复杂的数据结构,它允许在任何节点进行插入和删除操作,且可以在两个方向上遍历。为了高效地实现双向链表,我们需要理解其内部结构以及如何实现节点的插入、删除和遍历。在这个过程中,我们也会关注代码的优化和错误处理。
参考资源链接:[C++版《数据结构与算法分析》第三版详解](https://wenku.csdn.net/doc/4zvkhgbvn0?spm=1055.2569.3001.10343)
首先,我们需要定义双向链表的节点结构。每个节点包含三个部分:存储数据的成员、指向前一个节点的指针以及指向后一个节点的指针。以下是一个简单的双向链表节点的C++实现:
```cpp
struct Node {
int data;
Node* prev;
Node* next;
Node(int data) : data(data), prev(nullptr), next(nullptr) {}
};
```
接下来,我们定义双向链表类,其中包含用于插入、删除和遍历的基本操作:
```cpp
class DoublyLinkedList {
private:
Node* head;
Node* tail;
int size;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
~DoublyLinkedList() {
Node* current = head;
while(current != nullptr) {
Node* next = current->next;
delete current;
current = next;
}
head = nullptr;
tail = nullptr;
size = 0;
}
void insert(int data, int index) {
Node* newNode = new Node(data);
if(index == 0) {
newNode->next = head;
if(head) head->prev = newNode;
head = newNode;
if(size == 0) tail = newNode;
} else {
Node* current = head;
for(int i = 0; current != nullptr && i < index - 1; ++i) {
current = current->next;
}
newNode->next = current->next;
newNode->prev = current;
if(current->next) current->next->prev = newNode;
current->next = newNode;
if(newNode->next == nullptr) tail = newNode;
}
size++;
}
void remove(int index) {
if(index < 0 || index >= size) return;
Node* current = head;
for(int i = 0; i < index; ++i) {
current = current->next;
}
if(current->prev) current->prev->next = current->next;
if(current->next) current->next->prev = current->prev;
if(current == head) head = current->next;
if(current == tail) tail = current->prev;
delete current;
size--;
}
void traverse() {
Node* current = head;
while(current != nullptr) {
std::cout << current->data <<
参考资源链接:[C++版《数据结构与算法分析》第三版详解](https://wenku.csdn.net/doc/4zvkhgbvn0?spm=1055.2569.3001.10343)
阅读全文