C++ 进阶：手撸简易版 List，探秘底层原理与内存管理

内容摘要：C++ 进阶：手撸简易版 List，探秘底层原理与内存管理,

在 C++ 的学习过程中，STL 库中的 list 容器是常用的数据结构之一。它提供了双向链表的功能，方便我们在任意位置插入和删除元素。但是，直接使用 list 往往让我们忽略了其底层的实现细节。为了更好地理解 list 的工作原理，本文将带领大家手写一个简单的 list 模拟实现，并深入探讨相关的 C++ 知识点，就像我们平时在公司 review 代码一样，要知其然，更要知其所以然。这次，我们来聊聊如何进行 list 模拟实现。

为什么要模拟实现 List？

模拟实现 list 的好处有很多：

1. 深入理解数据结构： 通过自己动手实现，可以更深刻地理解链表的结构、节点的操作以及迭代器的实现。
2. 提升 C++ 编程能力： 涉及到指针、内存管理、模板编程等 C++ 核心知识点，是一个很好的练习机会。
3. 为阅读 STL 源码打下基础： 了解 list 的底层实现，有助于更好地理解 STL 源码，提升编程水平。在实际工作中，例如在使用 Nginx 的时候，对内存的管理和数据结构的选取，都需要有深刻的理解，才能避免出现内存泄漏等问题，毕竟线上服务稳定性是最重要的。

简易 List 的设计思路

我们的简易 list 需要包含以下基本功能：

• 节点的定义：每个节点包含数据和指向前后节点的指针。
• 构造函数：初始化 list，可以为空，也可以用已有的数据初始化。
• 插入操作：在头部、尾部或指定位置插入元素。
• 删除操作：删除头部、尾部或指定位置的元素。
• 迭代器：提供遍历 list 的方式。
• 析构函数：释放 list 占用的内存，避免内存泄漏。

代码实现

#include <iostream>

template <typename T>
struct ListNode {
    T data; // 数据
    ListNode<T>* prev; // 指向前一个节点的指针
    ListNode<T>* next; // 指向后一个节点的指针

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

template <typename T>
class SimpleList {
private:
    ListNode<T>* head; // 头节点
    ListNode<T>* tail; // 尾节点
    size_t size; // 元素个数

public:
    // 构造函数
    SimpleList() : head(nullptr), tail(nullptr), size(0) {}

    // 析构函数
    ~SimpleList() {
        ListNode<T>* current = head;
        while (current != nullptr) {
            ListNode<T>* next = current->next;
            delete current; // 释放节点内存
            current = next;
        }
        head = nullptr;
        tail = nullptr;
        size = 0;
    }

    // 在尾部插入元素
    void push_back(const T& val) {
        ListNode<T>* newNode = new ListNode<T>(val);
        if (head == nullptr) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        size++;
    }

    // 在头部插入元素
    void push_front(const T& val) {
        ListNode<T>* newNode = new ListNode<T>(val);
        if (head == nullptr) {
            head = newNode;
            tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        size++;
    }

    // 删除尾部元素
    void pop_back() {
        if (tail == nullptr) return; // 列表为空，直接返回
        if (head == tail) {
            delete head; // 只有一个节点
            head = nullptr;
            tail = nullptr;
        } else {
            ListNode<T>* temp = tail;
            tail = tail->prev;
            tail->next = nullptr;
            delete temp;
        }
        size--;
    }

    // 删除头部元素
    void pop_front() {
        if (head == nullptr) return; // 列表为空，直接返回
        if (head == tail) {
            delete head;
            head = nullptr;
            tail = nullptr;
        } else {
            ListNode<T>* temp = head;
            head = head->next;
            head->prev = nullptr;
            delete temp;
        }
        size--;
    }

    // 获取元素个数
    size_t get_size() const {
        return size;
    }

    // 打印 List
    void print_list() const {
        ListNode<T>* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    SimpleList<int> myList;
    myList.push_back(10);
    myList.push_back(20);
    myList.push_front(5);
    myList.print_list(); // 输出: 5 10 20
    myList.pop_back();
    myList.print_list(); // 输出: 5 10
    myList.pop_front();
    myList.print_list(); // 输出: 10
    std::cout << "Size: " << myList.get_size() << std::endl; // 输出: Size: 1
    return 0;
}

实战避坑经验总结

1. 内存管理： 在 list 的实现过程中，最容易出现的问题就是内存泄漏。一定要确保在删除节点时，释放其占用的内存。例如，在析构函数中要遍历整个链表，逐个删除节点。可以使用 Valgrind 等工具检测内存泄漏。
2. 指针操作： 指针操作要小心，避免出现空指针引用或者野指针。在修改指针之前，一定要检查指针是否为空。
3. 边界条件： 要考虑各种边界条件，例如空 list、只有一个节点的 list 等。在插入和删除操作时，要特别注意这些情况。
4. 迭代器失效： 在使用迭代器遍历 list 时，如果在遍历过程中修改了 list 的结构（例如插入或删除元素），可能会导致迭代器失效。需要重新获取迭代器。

总结

通过手写一个简单的 list 模拟实现，我们不仅可以更深入地理解 list 的工作原理，还可以提升 C++ 编程能力。希望这篇文章能帮助你更好地理解 C++ 中的 list 容器。