1. 必须学知识1.1 list 的介绍list - C Reference链表示意图 1.1list 链表底层主要实现的是一个带头循环链表。1.2 list的使用list 链表 与 vector 相同也是一个模板类vector 是一个开辟的是一个连续空间list 不连续的空间。void Print(listT L) { auto it L.begin(); for (; it ! L.end(); it) { std::cout *it ; } std::cout std::endl; } int main() { listint L; L.push_back(1); L.push_back(2); L.push_back(3); L.push_front(0); Print(L); cout endl; }1.2.1 list 的构造函数免责声明下面只介绍经常会常用的相关函数比较少用的函数没有介绍list::list - C Reference构造函数constructor功能list()头指针创建一个节点节点前指针和后指针指向头节点自己。list(size_t n, const value_type val value_type())将 n 个 val 作为初始化对象并构成链表template class InputIterator list(InputIterator first, InputIterator last)将[firstlast) 之间的内容作为初始化对象并构成链表。list(const list x)拷贝构造注释typedef T value_type; typedef const T const_value_type;1.2.2 list iterator的使用__list_iterator是 list 的指针来遍历链表中的元素类型。list 的 相关迭代器函数声明接口说明iterator begin; const_iterator beginconst返回_head-nextiterator end; const_iterator endconst返回 _head 本身1.2.3 listCapacity:函数声明接口说明bool empty () const判断 list 是否为空size_t size () const计算已有的节点个数1.2.4 list element access函数声明接口说明reference front() const_reference front() const放回第一个的节点内的内容注意这样与begin不同是要里面的内容reference back () const_reference back () const放回最后一个节点内的内容注意不能直接用end是end后一个位置注释typedef T reference;// 应用 typedef const T const_reference;//const 应用1.2.5 list Modifiers 修改器:清除相关 clear erase pop函数声明 Modifiers接口说明iterator erase(iterator position)定点删除重点返回 position-next 位置iterator erase(iterator first, iterator last)[ first, last) 的区间删除返回 last 位置void clear()删除所有保留一个头节点void pop_back()删除尾节点void pop_front()删除首节点插入 insert push函数声明 Modifiers接口说明iterator insert(iterator position, const value_type val)定点插入一个 val重点返回新插入位置void insert(iterator position, size_t n, const value_type val)定点插入 n 个 val无返回void insert(iterator position, InputIterator first, InputIterator last)定点插入 [ first , last 的内容void push_front(const value_type val)头插入void push_back (const value_type val)尾插入2. 难点知识2.1 如何实现 list 类(List_6_3 · 浪子·悠仁/日常练习代码库 - 码云 - 开源中国 list C语言简单实现相关代码。在 C 语言里实现链表可以拆成两个结构体一个是节点结构体Node另一个是链表结构体list。主函数里为了方便遍历还会单独定义节点指针用来访问链表。换到 C如果要封装成list类同样需要节点结构体还需要一个专门用来遍历节点的指针类这个指针类就是 list 类的迭代器。2.2 模拟实现 __list_iterator 迭代器__list_iterator 可以作为 list 类遍历更加方便的工具目标__list_iterator 的相关成员函数功能要求operator* ()返回 _it-_node;operator-()访问本身指针内的内容做到可以liststring it-_str it-_size it-_capacityoperator()指针移动到下一个节点并且返回移动后本身地址operator--()指针移动到上一个节点并且返回移动后本身地址operator(const Self it)判断指针是否相同operator!(const Self it)判断指针是否不相同成员变量Node* _it;模拟实现// 链表的迭代器 templatetypename T// 类型 引用 指针 struct __list_iterator { typedef list_nodeT Node; typedef __list_iteratorT Self; __list_iterator(Node* node) { _it node; } // 运算符重载 T* operator* () { return _it -_node; } T operator-() { return _it-_node; }// // 该代码意义就是进行访问 Node 一个单元内的成员的成员变量例如 auto it L.begin liststring it-_str it-_size it-_capacity // 注意实现的 -- 都是前缀 -- Self operator() { _it _it-_next; return *this; } Self operator--() { _it _it-_prev; return *this; } // bool 类型 bool operator(const Self it) { return _it it._it; } bool operator!(const Self it) { return _it ! it._it; } Node* _it; };如果我们需要支持只读遍历不修改链表内容是不是就得额外写一个const_list_iterator类型其实不用这么麻烦模板可以解决这个问题。我们只需要在模板里增加类型参数用来接收T/const T、T*/const T*就不用单独再写一套 const 迭代器类了。// 链表的迭代器 templatetypename T,typename Ref,typename Ptr// 类型 引用 指针 struct __list_iterator { typedef list_nodeT Node; typedef __list_iteratorT, Ref, Ptr Self; __list_iterator(Node* node) { _it node; } // 运算符重载 Ref operator* () { return _it -_node; } Ptr operator-() { return _it-_node; }// // 该代码意义就是进行访问 Node 一个单元内的成员的成员变量例如 auto it L.begin liststring it-_str it-_size it-_capacity // 注意实现的 -- 都是前缀 -- Self operator() { _it _it-_next; return *this; } Self operator--() { _it _it-_prev; return *this; } // bool 类型 bool operator(const Self it) { return _it it._it; } bool operator!(const Self it) { return _it ! it._it; } Node* _it; };3. 实现与模拟 list3.1 实现模拟想法以单个元素 insert作为底层核心函数push 头插、尾插、批量插入、构造函数都调用它erase 同理以单节点 erase 为基础实现批量删除。✅优点代码逻辑集中只需维护一套插入 / 删除逻辑简洁好读减少多处实现带来的 bug。❌缺点批量操作时循环逐个处理节点重复修改链表指针常数开销更大多次内存分配。算法时间复杂度不变小数据场景影响不大。3.2 模拟实现节点结构体template typename T // 链表的成员变量 struct list_node { list_node(const T node T()) { _node node; _next _prev nullptr; } T _node;//元素 list_nodeT* _next;//下一位指针 list_nodeT* _prev;//上一位指针 };迭代器 begin endtypedef __list_iteratorT, T, T* iterator; typedef __list_iteratorT, const T, const T* const_iterator; //iterator 迭代器 iterator begin() { return iterator(_head-_next); } iterator end() { return iterator(_head); } const_iterator begin()const { return const_iterator(_head-_next); } const_iterator end() const { return const_iterator(_head); }插入 insert 和 删除 erasevoid insert(iterator position, size_t n, const value_type val) { iterator it position; size_t i 0; while (i n) { it insert(it, val); i; } } template class InputIterator void insert(iterator position, InputIterator first, InputIterator last)//[first,last) { iterator it position; InputIterator ptr first; while (ptr ! last) { insert(it, *ptr); ptr; } } // push void push_front(const value_type val) { insert(begin(), val); } void push_back (const value_type val) { insert(end() , val); } // 清除相关 clear erase pop // erase 删除空间 //***** 重点关注 *****// iterator erase(iterator position) { Node* del_node position._it; position; del_node-_next-_prev del_node-_prev; del_node-_prev-_next del_node-_next; delete del_node; return iterator(position); } iterator erase(iterator first, iterator last)// [first,last) delete 范围 { iterator it first; while (it ! last) { it erase(it); } return last; } // clear 清除现有空间 void clear() { iterator it begin(); while (it ! end()) { it erase(it); } _head-_next _head-_prev _head; } // pop 删除 void pop_back() { if (empty()) return; erase(--end()); } void pop_front() { if (empty()) return; erase(begin()); }26_10_2 list/Youren_list.h · 浪子·悠仁/C 知识库 - 码云 - 开源中国感谢观看悠仁さん