如何在C++中实现一个双向链表并完成基本操作,比如插入和删除?请提供代码示例。
时间: 2024-12-02 12:24:59 浏览: 19
当你需要在C++中实现一个双向链表并进行基本操作时,如插入和删除节点,推荐查看《C++编程:包含数据结构的程序设计(第五版)》这本书。本书由D.S. Malik编撰,详细介绍了包括双向链表在内的各种数据结构的实现方法,以及它们在程序设计中的应用。接下来,我将为你提供一个简单的双向链表实现示例,包括插入和删除节点的方法。
参考资源链接:[C++编程:包含数据结构的程序设计(第五版)](https://wenku.csdn.net/doc/6401ac43cce7214c316eb35a?spm=1055.2569.3001.10343)
首先,我们需要定义双向链表的节点结构体和双向链表类。节点结构体通常包含三个成员:存储数据的变量以及指向前后节点的指针。双向链表类将包含头节点指针,并提供插入和删除节点的方法。
以下是一个简单的双向链表实现的代码示例:
```cpp
#include <iostream>
// 定义双向链表的节点结构体
struct Node {
int data;
Node* prev;
Node* next;
Node(int d) : data(d), prev(nullptr), next(nullptr) {}
};
// 定义双向链表类
class DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
// 在链表末尾插入节点
void append(int data) {
Node* newNode = new Node(data);
if (head == nullptr) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next != nullptr) {
temp = temp->next;
}
temp->next = newNode;
newNode->prev = temp;
}
// 删除链表中的节点
void remove(int data) {
if (head == nullptr) return;
Node* current = head;
while (current != nullptr) {
if (current->data == data) {
if (current == head) {
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
}
} else {
Node* prevNode = current->prev;
Node* nextNode = current->next;
prevNode->next = nextNode;
if (nextNode != nullptr) {
nextNode->prev = prevNode;
}
}
delete current;
return;
}
current = current->next;
}
}
};
int main() {
DoublyLinkedList dll;
dll.append(10);
dll.append(20);
dll.append(30);
dll.remove(20); // 删除节点20
// 输出剩余节点的数据,验证删除操作
Node* temp = dll.head;
while (temp != nullptr) {
std::cout << temp->data <<
参考资源链接:[C++编程:包含数据结构的程序设计(第五版)](https://wenku.csdn.net/doc/6401ac43cce7214c316eb35a?spm=1055.2569.3001.10343)
阅读全文