C++入门自学Day11-- List类型的自实现

   往期内容回顾

          List类型（初识）

          Vector类的自实现

         Vector类（注意事项）

          初识Vector

          String类的自实现

         String类的使用（续）  

         String类（续）

         String类（初识）

前言

        在 C++ 标准模板库（STL）中，std::list 是一个基于 双向链表（doubly linked list） 的容器，适用于频繁的插入、删除操作，且对元素的位置操作较多的场景。

相比于 vector 的连续内存存储，list 的节点是分散存储的，这带来了 插入/删除 O(1) 的优势，但随机访问性能较差（O(n)）。

学习 list 的最佳方式，不仅是掌握它的 基本使用，要学会它的底层逻辑实现，自己实现一遍，这可以加深对链表结构、内存管理以及 STL 设计思想的理解。

今天，我们就从头构建一个自己的 mylist 类型，并逐步实现其核心功能。

---

主要内容介绍

本篇将围绕以下几个方面展开：

1. 1、list 的数据结构设计

2. 2、构造与析构

3. 3、迭代器的实现

4. 4、常用接口实现（push_back、push_front、insert、erase 等）

5. 5、拷贝构造与赋值运算符

6. 6、迭代器失效问题与注意事项

7. 7、简单的测试与总结

---

一、list 的数据结构设计

1.1 节点结构（Node）

和 vector 不同，list 的元素不是连续存储的，每个节点都有三个部分：

template<typename T>
struct ListNode {T _data;ListNode* _prev;ListNode* _next;ListNode(const T& val = T()): _data(val), _prev(nullptr), _next(nullptr) {}
};

• _data 存储元素

• _prev 指向前一个节点

• _next 指向后一个节点

---

1.2 带哨兵位（sentinel）的链表设计

为了简化插入、删除的边界处理，我们使用一个 头结点（head） 作为哨兵：

• 空链表时：head->_next = head，head->_prev = head

• 非空时：头尾节点之间循环连接

template<typename T>
class mylist {
public:mylist() {_head = new ListNode<T>();_head->_next = _head;_head->_prev = _head;}~mylist() {clear();delete _head;}void clear() {ListNode<T>* cur = _head->_next;while (cur != _head) {ListNode<T>* next = cur->_next;delete cur;cur = next;}_head->_next = _head;_head->_prev = _head;}private:ListNode<T>* _head;
};

 构造函数初始化哨兵节点

 析构函数中调用 clear() 释放节点内存

---

二、迭代器的实现

迭代器本质上是一个包装了指针的类，使得我们的 list 能像 STL 一样用 begin()、end() 遍历。

template<typename T>
struct list_iterator {typedef ListNode<T> Node;Node* _node;list_iterator(Node* node = nullptr) : _node(node) {}T& operator*() { return _node->_data; }T* operator->() { return &_node->_data; }list_iterator& operator++() {_node = _node->_next;return *this;}list_iterator operator++(int) {list_iterator tmp = *this;_node = _node->_next;return tmp;}bool operator!=(const list_iterator& other) const {return _node != other._node;}
};

mylist 中提供：

list_iterator<T> begin() { return list_iterator<T>(_head->_next); }
list_iterator<T> end() { return list_iterator<T>(_head); }

---

三、常用接口实现

3.1 push_back

void push_back(const T& val) {insert(end(), val);
}

---

3.2 push_front

void push_front(const T& val) {insert(begin(), val);
}

---

3.3 insert

list_iterator<T> insert(list_iterator<T> pos, const T& val) {Node* cur = pos._node;Node* prev = cur->_prev;Node* newNode = new Node(val);prev->_next = newNode;newNode->_prev = prev;newNode->_next = cur;cur->_prev = newNode;return list_iterator<T>(newNode);
}

---

3.4 erase

list_iterator<T> erase(list_iterator<T> pos) {Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return list_iterator<T>(next);
}

---

四、拷贝构造与赋值运算符

mylist(const mylist& other) : mylist() {for (auto& e : other) {push_back(e);}
}mylist& operator=(mylist other) {swap(other);return *this;
}void swap(mylist& other) {std::swap(_head, other._head);
}

注意：深浅拷贝问题！！！

---

六、注意事项（迭代器失效）

• list 的插入、删除不会使已有迭代器失效（指向被删除节点的迭代器除外）

• vector 不同：在扩容时所有迭代器失效

• string 同 vector，连续存储结构中迭代器更容易失效

---

七、总结

        通过手写一个简易版 list，我们可以直观感受到：

         string、vector 依赖连续内存，适合随机访问

• list 依赖节点链式存储，适合频繁插入/删除

• 不同容器在 性能、内存管理、迭代器失效规则 上有很大区别

• 自己实现一次 STL 容器，可以更深刻地理解 C++ 的内存管理与数据结构设

如果你已经能手写 vector 和 list，基本就能理解 STL 容器的核心思想，并且在实际开发中能做出更合理的容器选择。

---

【面试题】

1、vector个list的区别？

特性	vector	list
内存布局	连续内存	节点链表（双向链表）
随机访问	支持 O(1)	不支持，需要遍历 O(n)
插入/删除	中间操作 O(n)；尾部 O(1) 均摊	已知位置插入/删除 O(1)
缓存局部性	高，遍历快	较差，遍历慢
内存开销	小	每个节点多两个指针（前驱/后继）
迭代器/指针稳定性	扩容或中间插入删除会失效	除被删元素外通常稳定
使用场景	主要是顺序访问、随机访问、多遍历	插入删除频繁、需要稳定迭代器/引用

---

2、vector和list的底层是如何实现？

vector：

• 本质是 动态数组。

• 内存连续存储，每次扩容时申请更大的连续内存，并把原有元素拷贝/移动过去。

• 支持随机访问（通过指针运算）。list：

list：

• 本质是 双向链表。
• 每个元素包装成节点，节点存放元素 + 前驱/后继指针。
• 内存不连续，插入/删除通过修改指针连接完成，随机访问需遍历。

---

3. vector 是如何进行增容的

当 vector 空间不足时，会触发 扩容：

1. 申请 更大连续内存（通常是原容量的 1.5~2 倍）。

2. 将原数组元素 拷贝或移动 到新内存。

3. 释放旧内存。

扩容的复杂度：

• 单次扩容是 O(n)

• 均摊成本是 O(1)（因为扩容次数相对较少，摊销到每次插入）。

---

4、什么是迭代器失效？

迭代器失效指的是 迭代器、指针或引用指向的对象在容器修改后不再有效。

不同容器的失效规则不同：

• vector：

  • 扩容 → 所有迭代器失效

  • 中间插入/删除 → 被移动的元素迭代器失效

  • 尾部 push_back/pop_back → 扩容时失效，否则尾部迭代器失效

• list：

  • 插入 → 现有元素迭代器通常有效

  • 删除 → 被删元素迭代器失效，其他仍有效。

• string（连续内存）与 vector 类似

简单理解：迭代器失效就是“原来的指针或引用不再安全使用了”。

---