C++STL链表实现全解析-编程阁

C++ STL list 模拟实现：从底层链表到容器封装

在C++标准模板库（STL）中，list是一个基于双向链表实现的序列容器，它提供高效的插入和删除操作，时间复杂度通常为$O(1)$。下面我将从底层链表结构开始，逐步模拟实现一个简化版的list容器，涵盖节点定义、链表操作、迭代器实现和容器封装。整个过程使用C++语言，并遵循面向对象设计原则。

1. 底层链表实现：节点定义

双向链表的基本单位是节点（Node），每个节点包含数据元素、指向前驱节点的指针和指向后继节点的指针。定义如下：

template <typename T> struct Node { T data; // 存储的数据 Node* prev; // 指向前驱节点的指针 Node* next; // 指向后继节点的指针 // 构造函数，初始化节点 Node(const T& val, Node* p = nullptr, Node* n = nullptr) : data(val), prev(p), next(n) {} };

这里，T是模板参数，允许链表存储任意类型的数据。每个节点通过prev和next指针形成双向链接。

2. 容器封装：list类实现

接下来，封装一个MyList类来管理链表，提供类似STL list的接口。类中包含头尾哨兵节点（dummy nodes）以简化边界操作，并记录链表大小。

template <typename T> class MyList { private: Node<T>* head; // 头哨兵节点，不存储数据 Node<T>* tail; // 尾哨兵节点，不存储数据 size_t size; // 链表大小 public: // 默认构造函数：初始化空链表 MyList() : size(0) { head = new Node<T>(T()); tail = new Node<T>(T()); head->next = tail; tail->prev = head; } // 析构函数：释放所有节点 ~MyList() { clear(); delete head; delete tail; } // 清空链表 void clear() { Node<T>* curr = head->next; while (curr != tail) { Node<T>* temp = curr; curr = curr->next; delete temp; } head->next = tail; tail->prev = head; size = 0; } // 获取链表大小 size_t get_size() const { return size; } // 在尾部插入元素 void push_back(const T& val) { Node<T>* newNode = new Node<T>(val, tail->prev, tail); tail->prev->next = newNode; tail->prev = newNode; ++size; } // 在头部插入元素 void push_front(const T& val) { Node<T>* newNode = new Node<T>(val, head, head->next); head->next->prev = newNode; head->next = newNode; ++size; } // 删除尾部元素 void pop_back() { if (size == 0) return; Node<T>* temp = tail->prev; tail->prev = temp->prev; temp->prev->next = tail; delete temp; --size; } // 删除头部元素 void pop_front() { if (size == 0) return; Node<T>* temp = head->next; head->next = temp->next; temp->next->prev = head; delete temp; --size; } };

在这个实现中：

使用哨兵节点避免了空链表或边界操作的额外检查。
push_back和push_front操作的时间复杂度为$O(1)$，因为只需修改指针。
pop_back和pop_front同样为$O(1)$。
内存管理：析构函数确保释放所有节点。

3. 迭代器实现

STL list支持双向迭代器，允许遍历和修改元素。我们定义一个Iterator类：

template <typename T> class MyListIterator { private: Node<T>* current; // 当前指向的节点 public: // 构造函数 MyListIterator(Node<T>* node) : current(node) {} // 解引用操作符 T& operator*() { return current->data; } // 前置递增（移动到下一个节点） MyListIterator& operator++() { current = current->next; return *this; } // 前置递减（移动到前一个节点） MyListIterator& operator--() { current = current->prev; return *this; } // 比较操作符 bool operator!=(const MyListIterator& other) const { return current != other.current; } };

在MyList类中添加迭代器支持：

// 在MyList类中添加以下方法 public: using iterator = MyListIterator<T>; iterator begin() { return iterator(head->next); } iterator end() { return iterator(tail); }

迭代器允许遍历链表：

MyList<int> list; list.push_back(1); list.push_back(2); for (auto it = list.begin(); it != list.end(); ++it) { std::cout << *it << " "; } // 输出: 1 2

4. 性能分析

时间复杂度：
- 插入和删除操作：在头部或尾部为$O(1)$。
- 随机访问：链表不支持随机访问，时间复杂度为$O(n)$。
空间复杂度：每个元素额外占用指针空间，总体为$O(n)$。

5. 完整示例代码

以下是一个简化版的完整实现：

#include <iostream> template <typename T> struct Node { T data; Node* prev; Node* next; Node(const T& val, Node* p = nullptr, Node* n = nullptr) : data(val), prev(p), next(n) {} }; template <typename T> class MyListIterator { private: Node<T>* current; public: MyListIterator(Node<T>* node) : current(node) {} T& operator*() { return current->data; } MyListIterator& operator++() { current = current->next; return *this; } MyListIterator& operator--() { current = current->prev; return *this; } bool operator!=(const MyListIterator& other) const { return current != other.current; } }; template <typename T> class MyList { private: Node<T>* head; Node<T>* tail; size_t size; public: using iterator = MyListIterator<T>; MyList() : size(0) { head = new Node<T>(T()); tail = new Node<T>(T()); head->next = tail; tail->prev = head; } ~MyList() { clear(); delete head; delete tail; } void clear() { Node<T>* curr = head->next; while (curr != tail) { Node<T>* temp = curr; curr = curr->next; delete temp; } head->next = tail; tail->prev = head; size = 0; } void push_back(const T& val) { Node<T>* newNode = new Node<T>(val, tail->prev, tail); tail->prev->next = newNode; tail->prev = newNode; ++size; } iterator begin() { return iterator(head->next); } iterator end() { return iterator(tail); } }; int main() { MyList<int> list; list.push_back(10); list.push_back(20); for (auto it = list.begin(); it != list.end(); ++it) { std::cout << *it << " "; } // 输出: 10 20 return 0; }