C++实现带头双向链表增删查改

C带头双向链表的增删查改模拟实现带头双向链表是一种常见的数据结构它使用一个哨兵头节点不存储实际数据来简化边界条件的处理。每个节点包含指向前一个节点和后一个节点的指针实现双向遍历。这种结构在插入和删除操作时效率较高时间复杂度通常为 $O(1)$ 或 $O(n)$取决于操作位置。下面我将逐步实现一个带头双向链表包括增加、删除、查找和修改功能。实现概述节点结构每个节点包含数据这里假设为整数、指向前一个节点的指针prev和指向后一个节点的指针next。链表类包含一个哨兵头节点head其prev和next在空链表时指向自身。我们实现以下方法push_front在链表头部插入元素。push_back在链表尾部插入元素。insert在指定位置插入元素。pop_front删除头部元素。pop_back删除尾部元素。remove删除特定值的元素。contains检查链表是否包含某个值。find查找特定值的节点返回指针。update修改特定值的节点。print打印链表内容辅助函数。内存管理使用动态内存分配注意在析构函数中释放所有节点。代码实现以下是完整的C代码实现。代码中使用了哨兵头节点来简化操作确保边界条件如空链表的正确处理。#include iostream // 节点结构定义 struct Node { int data; // 存储整数数据 Node* prev; // 指向前一个节点的指针 Node* next; // 指向后一个节点的指针 // 构造函数 Node(int val 0) : data(val), prev(nullptr), next(nullptr) {} }; // 带头双向链表类 class List { private: Node* head; // 哨兵头节点 int size; // 链表大小用于跟踪元素数量 public: // 构造函数初始化哨兵头节点 List() : size(0) { head new Node(); head-prev head; // 空链表时prev和next指向自身 head-next head; } // 析构函数释放所有节点内存 ~List() { Node* current head-next; while (current ! head) { // 遍历直到回到头节点 Node* next_node current-next; delete current; current next_node; } delete head; // 释放头节点 } // 在链表头部插入元素 void push_front(int val) { Node* new_node new Node(val); new_node-next head-next; new_node-prev head; head-next-prev new_node; head-next new_node; size; } // 在链表尾部插入元素 void push_back(int val) { Node* new_node new Node(val); new_node-prev head-prev; new_node-next head; head-prev-next new_node; head-prev new_node; size; } // 在指定位置插入元素位置从0开始0表示头部 void insert(int index, int val) { if (index 0 || index size) { std::cerr Invalid index for insertion. std::endl; return; } if (index 0) { push_front(val); } else if (index size) { push_back(val); } else { Node* current head-next; for (int i 0; i index; i) { current current-next; } Node* new_node new Node(val); new_node-prev current-prev; new_node-next current; current-prev-next new_node; current-prev new_node; size; } } // 删除链表头部元素 void pop_front() { if (size 0) { std::cerr List is empty. std::endl; return; } Node* to_delete head-next; head-next to_delete-next; to_delete-next-prev head; delete to_delete; size--; } // 删除链表尾部元素 void pop_back() { if (size 0) { std::cerr List is empty. std::endl; return; } Node* to_delete head-prev; head-prev to_delete-prev; to_delete-prev-next head; delete to_delete; size--; } // 删除特定值的元素删除所有匹配项 void remove(int val) { Node* current head-next; while (current ! head) { if (current-data val) { Node* to_delete current; current current-next; // 移动到下一个节点 to_delete-prev-next to_delete-next; to_delete-next-prev to_delete-prev; delete to_delete; size--; } else { current current-next; } } } // 检查链表是否包含某个值 bool contains(int val) const { Node* current head-next; while (current ! head) { if (current-data val) { return true; } current current-next; } return false; } // 查找特定值的节点返回指针如果不存在返回nullptr Node* find(int val) const { Node* current head-next; while (current ! head) { if (current-data val) { return current; } current current-next; } return nullptr; } // 修改特定值的节点将所有匹配项修改为新值 void update(int old_val, int new_val) { Node* current head-next; while (current ! head) { if (current-data old_val) { current-data new_val; } current current-next; } } // 打印链表内容辅助函数 void print() const { Node* current head-next; std::cout List: ; while (current ! head) { std::cout current-data ; current current-next; } std::cout std::endl; } }; // 示例测试函数 int main() { List list; list.push_back(10); list.push_front(5); list.insert(1, 7); // 插入在位置1中间 list.print(); // 输出List: 5 7 10 list.remove(7); list.print(); // 输出List: 5 10 std::cout Contains 10? list.contains(10) std::endl; // 输出1 (true) list.update(10, 20); list.print(); // 输出List: 5 20 list.pop_back(); list.print(); // 输出List: 5 return 0; }代码说明哨兵头节点head节点不存储数据其prev和next在初始化时指向自身这简化了空链表的处理。插入操作push_front和push_back时间复杂度为 $O(1)$insert在平均情况下为 $O(n)$需遍历。删除操作pop_front和pop_back为 $O(1)$remove为 $O(n)$需遍历。查找和修改contains、find和update时间复杂度均为 $O(n)$因为需要遍历链表。内存安全析构函数确保所有节点被释放避免内存泄漏。测试main函数演示了基本操作您可以根据需要扩展。这个实现模拟了C标准库中std::list的核心功能但更简单易懂。使用时注意边界条件和内存管理。如果您有其他需求如支持泛型数据类型可以进一步扩展。