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 的核心功能，但更简单易懂。使用时注意边界条件和内存管理。如果您有其他需求（如支持泛型数据类型），可以进一步扩展。