当前位置：首页 > news >正文

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

news 2026/4/20 6:05:10

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

带头双向链表是一种常见的数据结构，它包含一个头节点（dummy node），该节点不存储实际数据，仅用于简化链表操作。每个节点都有prev和next指针，指向前后节点，实现双向遍历。这种结构在插入和删除操作时效率较高，因为可以直接访问相邻节点。下面我将逐步实现带头双向链表的增（insert）、删（delete）、查（find）、改（modify）操作。

实现思路

节点类（Node）：定义链表节点，包含数据（data）、前驱指针（prev）和后继指针（next）。
链表类（List）：管理链表，包含头节点和成员函数。
- 头节点初始化时指向自己，形成循环。
- 实现增删查改操作，注意指针更新和边界处理。
内存管理：使用动态分配内存，需在析构函数中释放节点，避免泄漏。

以下是完整的C++代码实现，包含注释解释关键步骤：

#include <iostream> // 用于输入输出 // 节点类模板 template <typename T> class Node { public: T data; // 存储数据 Node* prev; // 前驱指针 Node* next; // 后继指针 // 构造函数 Node(T val) : data(val), prev(nullptr), next(nullptr) {} }; // 带头双向链表类模板 template <typename T> class List { private: Node<T>* head; // 头节点（哨兵节点） public: // 构造函数：初始化头节点 List() { head = new Node<T>(T()); // 创建头节点，数据使用默认值 head->prev = head; // 初始时，头节点指向自己 head->next = head; } // 析构函数：释放所有节点内存 ~List() { Node<T>* current = head->next; while (current != head) { // 遍历链表 Node<T>* nextNode = current->next; delete current; // 释放当前节点 current = nextNode; } delete head; // 释放头节点 } // 增：在指定位置插入节点（位置从0开始，0表示头节点后第一个位置） void insert(T val, int pos) { if (pos < 0) return; // 位置无效，直接返回 Node<T>* newNode = new Node<T>(val); // 创建新节点 Node<T>* current = head->next; // 当前节点从第一个实际节点开始 int count = 0; // 遍历找到插入位置的前驱节点 while (current != head && count < pos) { current = current->next; count++; } // 插入新节点：更新指针 newNode->prev = current->prev; newNode->next = current; current->prev->next = newNode; current->prev = newNode; } // 删：删除指定位置的节点 void deleteNode(int pos) { if (pos < 0) return; // 位置无效，直接返回 Node<T>* current = head->next; int count = 0; // 遍历找到要删除的节点 while (current != head && count < pos) { current = current->next; count++; } if (current == head) return; // 位置超出链表范围 // 删除节点：更新指针并释放内存 current->prev->next = current->next; current->next->prev = current->prev; delete current; } // 查：查找指定值的节点，返回节点指针（若不存在返回nullptr） Node<T>* find(T val) { Node<T>* current = head->next; // 从头节点后开始遍历 while (current != head) { if (current->data == val) { return current; // 找到匹配节点 } current = current->next; } return nullptr; // 未找到 } // 改：修改指定位置节点的值 void modify(int pos, T newVal) { if (pos < 0) return; // 位置无效，直接返回 Node<T>* current = head->next; int count = 0; // 遍历找到要修改的节点 while (current != head && count < pos) { current = current->next; count++; } if (current != head) { current->data = newVal; // 修改数据 } } // 打印链表：用于测试 void print() { Node<T>* current = head->next; // 跳过头节点 std::cout << "链表: "; while (current != head) { std::cout << current->data << " "; current = current->next; } std::cout << std::endl; } }; // 测试示例 int main() { List<int> list; list.insert(10, 0); // 插入到位置0 list.insert(20, 1); // 插入到位置1 list.insert(30, 2); // 插入到位置2 list.print(); // 输出: 链表: 10 20 30 list.deleteNode(1); // 删除位置1的节点 list.print(); // 输出: 链表: 10 30 Node<int>* found = list.find(30); // 查找值为30的节点 if (found) { std::cout << "找到节点: " << found->data << std::endl; // 输出: 找到节点: 30 } list.modify(0, 50); // 修改位置0的节点值为50 list.print(); // 输出: 链表: 50 30 return 0; }