手撸 List：从零开始模拟实现 STL 容器底层原理

在 C++ 开发中，std::list 是一种非常常用的容器，尤其在需要频繁进行插入和删除操作的场景下。但是，仅仅会使用是不够的，深入理解其底层实现原理，能帮助我们更好地选择数据结构，避免性能陷阱。今天，我们就来一起模拟实现一个简单的 List，探究其背后的奥秘，顺便复习一下链表的相关知识。

在日常工作中，我们经常会遇到需要处理大量数据的场景，例如电商平台的订单处理、金融系统的交易记录等。如果使用不合适的数据结构，可能会导致程序性能瓶颈，例如 CPU 占用率过高、内存消耗过大等。这时候，理解 List 的底层实现，就能帮助我们更好地进行性能优化。这就像我们使用 Nginx 做反向代理时，只有了解其工作原理，才能更好地进行配置和优化，应对高并发连接数，甚至可以使用宝塔面板简化管理。

List 的底层原理：双向链表

std::list 的底层实现是双向链表。双向链表是一种链式存储结构，每个节点包含数据域和两个指针域，分别指向前一个节点和后一个节点。这种结构使得在链表中插入和删除节点的操作非常高效，时间复杂度为 O(1)。

双向链表的特点：

• 动态内存分配：链表的节点在运行时动态分配，可以灵活地调整链表的长度，避免了数组的固定大小限制。
• 插入和删除效率高：在已知节点位置的情况下，插入和删除操作只需要修改指针，不需要移动大量元素，时间复杂度为 O(1)。
• 随机访问效率低：由于链表的节点在内存中不是连续存储的，因此无法像数组那样通过索引进行随机访问，时间复杂度为 O(n)。

模拟实现 List 的基本要素：

1. 节点结构体 (Node)：包含数据域和指向前后节点的指针。
2. List 类：包含头节点、尾节点、大小等成员变量，以及插入、删除、查找等成员函数。

代码实现

下面是一个简单的 List 类的模拟实现：

#include <iostream>

// 节点结构体
template <typename T>
struct Node {
    T data; // 数据域
    Node<T>* prev; // 指向前一个节点的指针
    Node<T>* next; // 指向后一个节点的指针
    Node(const T& val) : data(val), prev(nullptr), next(nullptr) {}
};

// List 类
template <typename T>
class List {
private:
    Node<T>* head; // 头节点
    Node<T>* tail; // 尾节点
    size_t size; // 链表大小

public:
    List() : head(nullptr), tail(nullptr), size(0) {}
    ~List() {
        clear();
    }

    // 插入节点
    void push_back(const T& val) {
        Node<T>* newNode = new Node<T>(val);
        if (head == nullptr) {
            head = tail = newNode;
        } else {
            tail->next = newNode;
            newNode->prev = tail;
            tail = newNode;
        }
        size++;
    }

    // 删除节点
    void pop_back() {
        if (tail == nullptr) return;
        Node<T>* temp = tail;
        tail = tail->prev;
        if (tail == nullptr) {
            head = nullptr;
        } else {
            tail->next = nullptr;
        }
        delete temp;
        size--;
    }

    // 获取链表大小
    size_t getSize() const {
        return size;
    }

    // 清空链表
    void clear() {
        Node<T>* current = head;
        while (current != nullptr) {
            Node<T>* next = current->next;
            delete current;
            current = next;
        }
        head = tail = nullptr;
        size = 0;
    }

    // 打印链表元素
    void print() const {
        Node<T>* current = head;
        while (current != nullptr) {
            std::cout << current->data << " ";
            current = current->next;
        }
        std::cout << std::endl;
    }
};

int main() {
    List<int> myList;
    myList.push_back(10);
    myList.push_back(20);
    myList.push_back(30);
    myList.print(); // 输出: 10 20 30
    myList.pop_back();
    myList.print(); // 输出: 10 20
    std::cout << "Size: " << myList.getSize() << std::endl; // 输出: Size: 2
    return 0;
}

这个示例代码展示了 List 的基本功能：插入、删除、获取大小和打印。实际应用中，还需要根据具体需求添加更多的功能，例如插入到指定位置、删除指定元素、查找元素等。

实战避坑经验总结

• 内存泄漏：在链表操作中，一定要注意内存管理，避免内存泄漏。例如，在删除节点时，一定要释放节点占用的内存。
• 空指针异常：在链表操作中，一定要注意判断指针是否为空，避免空指针异常。例如，在访问头节点或尾节点之前，一定要判断链表是否为空。
• 迭代器失效：在使用迭代器遍历链表时，如果在遍历过程中修改了链表的结构（例如插入或删除节点），可能会导致迭代器失效，需要重新获取迭代器。例如，在使用 std::list 时，可以使用 erase 函数删除节点，并获取返回的迭代器，指向下一个节点。

总之，深入理解 List 的底层实现原理，可以帮助我们更好地使用 List，避免性能陷阱，提升程序性能。 希望这个简单的模拟实现能帮助你更好地理解 List。