在C++中,双向链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据部分和两个指针,分别指向前一个节点和后一个节点。 以下是手写双向链表并完成基本的增删改查功能的示例代码: #include <iostream>
// 定义双向链表的节点结构
struct Node {
int data;
Node* prev;
Node* next;
Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};
// 双向链表类
class DoublyLinkedList {
private:
Node* head;
Node* tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// 在链表头部添加元素
void push_front(int value) {
Node* newNode = new Node(value);
newNode->next = head;
if (head != nullptr) {
head->prev = newNode;
} else {
tail = newNode; // 如果链表为空,tail也指向新节点
}
head = newNode;
}
// 在链表尾部添加元素
void push_back(int value) {
Node* newNode = new Node(value);
if (tail != nullptr) {
tail->next = newNode;
newNode->prev = tail;
} else {
head = newNode; // 如果链表为空,head也指向新节点
}
tail = newNode;
}
// 删除链表头部的元素
void pop_front() {
if (head == nullptr) return;
Node* temp = head;
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
} else {
tail = nullptr; // 如果链表只有一个元素,删除后链表变空
}
delete temp;
}
// 删除链表尾部的元素
void pop_back() {
if (tail == nullptr) return;
Node* temp = tail;
if (tail->prev != nullptr) {
tail = tail->prev;
tail->next = nullptr;
} else {
head = nullptr; // 如果链表只有一个元素,删除后链表变空
}
delete temp;
}
// 查找元素并修改
bool update(int value, int newValue) {
Node* current = head;
while (current != nullptr) {
if (current->data == value) {
current->data = newValue;
return true;
}
current = current->next;
}
return false;
}
// 删除指定值的元素
bool remove(int value) {
Node* current = head;
while (current != nullptr) {
if (current->data == value) {
if (current->prev != nullptr) {
current->prev->next = current->next;
} else {
head = current->next; // 如果删除的是头节点
}
if (current->next != nullptr) {
current->next->prev = current->prev;
} else {
tail = current->prev; // 如果删除的是尾节点
}
delete current;
return true;
}
current = current->next;
}
return false;
}
// 打印链表
void print() {
Node* current = head;
while (current != nullptr) {
std::cout << current->data << " ";
current = current->next;
}
std::cout << std::endl;
}
// 析构函数,释放链表内存
~DoublyLinkedList() {
while (head != nullptr) {
pop_front();
}
}
};
int main() {
DoublyLinkedList list;
// 测试双向链表功能
list.push_front(10);
list.push_back(20);
list.push_front(30);
list.push_back(40);
list.print(); // 应该输出: 30 10 20 40
list.pop_front();
list.pop_back();
list.print(); // 应该输出: 20 40
list.update(20, 50);
list.print(); // 应该输出: 50 40
if (list.remove(40)) {
std::cout << "40 removed" << std::endl;
}
list.print(); // 应该输出: 50
return 0;
}
这段代码定义了一个Node 结构体,用于存储数据和指向前后节点的指针。 DoublyLinkedList 类包含了双向链表的基本操作,如在头部和尾部添加元素、删除头部和尾部的元素、查找并修改元素、删除指定值的元素以及打印链表。
在main 函数中,我们创建了一个双向链表的实例,并测试了它的各种功能。
(责任编辑:admin) |