C++ 中如何实现双向链表的插入和删除操作

2026-01-19 作者 stdcpp

双向链表（Doubly Linked List）是一种常见的数据结构，每个节点包含指向前驱和后继节点的指针。在 C++ 中实现双向链表时，核心是节点结构、链表类以及插入、删除等基本操作。下面以一个简洁而完整的实现为例，说明如何在 C++ 中完成这些功能，并讨论其中的细节与常见陷阱。

1. 节点结构（Node）

template<typename T>
struct Node {
    T data;                // 存储的数据
    Node* prev;            // 前驱指针
    Node* next;            // 后继指针

    Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}
};

节点结构非常简单：数据域、前驱指针和后继指针。模板化使得链表可以存储任何类型。

2. 链表类（DoublyLinkedList）

template<typename T>
class DoublyLinkedList {
private:
    Node <T>* head;   // 指向链表头部
    Node <T>* tail;   // 指向链表尾部
    size_t sz;       // 记录链表长度

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), sz(0) {}
    ~DoublyLinkedList() { clear(); }

    // 取得链表长度
    size_t size() const { return sz; }

    // 清空链表
    void clear();

    // 插入操作
    void insert_front(const T& value);
    void insert_back(const T& value);
    void insert_at(size_t index, const T& value);   // 在指定位置插入

    // 删除操作
    void remove_front();
    void remove_back();
    void remove_at(size_t index);                  // 删除指定位置

    // 访问元素
    T& at(size_t index);
    const T& at(size_t index) const;

    // 输出链表（用于调试）
    void print() const;
};

2.1 析构函数与清空

template<typename T>
void DoublyLinkedList <T>::clear() {
    Node <T>* curr = head;
    while (curr) {
        Node <T>* tmp = curr;
        curr = curr->next;
        delete tmp;
    }
    head = tail = nullptr;
    sz = 0;
}

2.2 插入操作

template<typename T>
void DoublyLinkedList <T>::insert_front(const T& value) {
    Node <T>* node = new Node<T>(value);
    node->next = head;
    if (head) head->prev = node;
    head = node;
    if (!tail) tail = node;  // 第一个节点
    ++sz;
}

template<typename T>
void DoublyLinkedList <T>::insert_back(const T& value) {
    Node <T>* node = new Node<T>(value);
    node->prev = tail;
    if (tail) tail->next = node;
    tail = node;
    if (!head) head = node;  // 第一个节点
    ++sz;
}

template<typename T>
void DoublyLinkedList <T>::insert_at(size_t index, const T& value) {
    if (index > sz) throw std::out_of_range("Index out of range");
    if (index == 0) { insert_front(value); return; }
    if (index == sz) { insert_back(value); return; }

    Node <T>* curr = head;
    for (size_t i = 0; i < index; ++i) curr = curr->next;  // 移动到目标位置

    Node <T>* node = new Node<T>(value);
    node->prev = curr->prev;
    node->next = curr;
    curr->prev->next = node;
    curr->prev = node;
    ++sz;
}

2.3 删除操作

template<typename T>
void DoublyLinkedList <T>::remove_front() {
    if (!head) return;
    Node <T>* tmp = head;
    head = head->next;
    if (head) head->prev = nullptr;
    else tail = nullptr;  // 链表变为空
    delete tmp;
    --sz;
}

template<typename T>
void DoublyLinkedList <T>::remove_back() {
    if (!tail) return;
    Node <T>* tmp = tail;
    tail = tail->prev;
    if (tail) tail->next = nullptr;
    else head = nullptr;  // 链表变为空
    delete tmp;
    --sz;
}

template<typename T>
void DoublyLinkedList <T>::remove_at(size_t index) {
    if (index >= sz) throw std::out_of_range("Index out of range");
    if (index == 0) { remove_front(); return; }
    if (index == sz - 1) { remove_back(); return; }

    Node <T>* curr = head;
    for (size_t i = 0; i < index; ++i) curr = curr->next;  // 移动到目标节点

    curr->prev->next = curr->next;
    curr->next->prev = curr->prev;
    delete curr;
    --sz;
}

2.4 访问与打印

template<typename T>
T& DoublyLinkedList <T>::at(size_t index) {
    if (index >= sz) throw std::out_of_range("Index out of range");
    Node <T>* curr = head;
    for (size_t i = 0; i < index; ++i) curr = curr->next;
    return curr->data;
}

template<typename T>
const T& DoublyLinkedList <T>::at(size_t index) const {
    if (index >= sz) throw std::out_of_range("Index out of range");
    Node <T>* curr = head;
    for (size_t i = 0; i < index; ++i) curr = curr->next;
    return curr->data;
}

template<typename T>
void DoublyLinkedList <T>::print() const {
    Node <T>* curr = head;
    while (curr) {
        std::cout << curr->data << (curr->next ? " <-> " : "");
        curr = curr->next;
    }
    std::cout << "\n";
}

3. 常见陷阱与改进

内存泄漏：所有 new 必须配对 delete。使用 clear() 或在析构函数中释放所有节点即可。
空指针检查：插入和删除时需判断头尾是否为空，避免访问空指针。
异常安全：在插入时若构造函数抛异常，需确保链表状态不被破坏。可以使用 try-catch 或先创建节点再更新链表。
性能优化：如果频繁在中间位置插入/删除，维护双向指针能在 O(1) 时间完成操作；但若需要随机访问，链表并不适合，可使用 std::vector 或 std::deque。
模板与类型安全：上述实现基于模板，能支持任意类型，但如果类型不支持复制/移动，需要显式定义拷贝/移动构造函数。

4. 示例用法

int main() {
    DoublyLinkedList <int> list;
    list.insert_back(10);
    list.insert_front(5);
    list.insert_at(1, 7);          // 5 <-> 7 <-> 10
    list.print();

    list.remove_at(1);             // 5 <-> 10
    list.print();

    std::cout << "Size: " << list.size() << "\n";
    std::cout << "Element at 1: " << list.at(1) << "\n";
}

运行结果：

5 <-> 7 <-> 10
5 <-> 10
Size: 2
Element at 1: 10

5. 小结

双向链表通过前驱后继指针实现双向遍历，插入和删除只需要修改相邻节点指针，时间复杂度为 O(1)。
在 C++ 中实现时，需要注意内存管理、边界检查和异常安全。
结合模板化，链表可以存储任意类型的数据，灵活性较高。
了解其优势与劣势，可在需要频繁插入删除且不关注随机访问时使用；否则考虑使用更高层的数据结构如 std::deque 或 std::list。

发表评论取消回复