C++ list 模拟实现详解

在C++标准模板库(STL)中，list是一个非常重要的容器，它底层采用带头双向链表实现。本文将带你手动模拟实现一个简化版的list，重点关注其增删查改操作，通过模拟实现加深对数据结构和C++内存管理的理解。

1. 结点定义

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

2. List类框架

templateclass List {public:    typedef ListNode Node;    List() {        head = new Node();  // 头结点不存储数据        head->prev = head;        head->next = head;    }    ~List() {        clear();        delete head;    }    // ... 其他成员函数private:    Node* head;};

3. 增操作

插入包括头插、尾插和指定位置插入。这些操作都基于双向链表的指针修改。

void push_back(const T& val) {    Node* newNode = new Node(val);    Node* tail = head->prev;    tail->next = newNode;    newNode->prev = tail;    newNode->next = head;    head->prev = newNode;}void push_front(const T& val) {    Node* newNode = new Node(val);    Node* first = head->next;    head->next = newNode;    newNode->prev = head;    newNode->next = first;    first->prev = newNode;}void insert(Node* pos, const T& val) {    Node* newNode = new Node(val);    Node* prevNode = pos->prev;    prevNode->next = newNode;    newNode->prev = prevNode;    newNode->next = pos;    pos->prev = newNode;}

4. 删操作

void pop_back() {    if (empty()) return;    Node* tail = head->prev;    Node* newTail = tail->prev;    newTail->next = head;    head->prev = newTail;    delete tail;}void pop_front() {    if (empty()) return;    Node* first = head->next;    Node* newFirst = first->next;    head->next = newFirst;    newFirst->prev = head;    delete first;}void erase(Node* pos) {    if (pos == head) return; // 不能删除头结点    Node* prevNode = pos->prev;    Node* nextNode = pos->next;    prevNode->next = nextNode;    nextNode->prev = prevNode;    delete pos;}

5. 查操作

Node* find(const T& val) const {    Node* cur = head->next;    while (cur != head) {        if (cur->data == val)            return cur;        cur = cur->next;    }    return head; // 返回头结点表示未找到}

6. 改操作

修改通常通过查找后直接修改结点数据，或通过迭代器修改。这里展示通过查找修改：

bool modify(const T& oldVal, const T& newVal) {    Node* node = find(oldVal);    if (node != head) {        node->data = newVal;        return true;    }    return false;}

7. 辅助函数与测试

bool empty() const { return head->next == head; }void clear() {    while (!empty()) pop_front();}void print() const {    Node* cur = head->next;    while (cur != head) {        std::cout << cur->data << " ";        cur = cur->next;    }    std::cout << std::endl;}

通过上述代码，我们完整模拟实现了带头双向链表的增删查改操作。实际STL的list更加复杂，包含迭代器、分配器等，但核心思想与此类似。希望这篇教程能帮助你理解C++ list的底层原理。