一、list的底层结构双向循环链表在C标准库中std::list是一个双向链表容器它采用双向循环链表作为底层数据结构。这种设计使得list在任意位置插入和删除元素的时间复杂度都是O(1)但随机访问的效率较低。1.1 节点结构定义list的底层是一个双向循环链表每个节点通常包含三个部分数据域data)存储元素值前驱指针(prev)指向前一个节点后继指针(next)指向后一个节点在STL实现中节点结构通常定义如下templatetypename T struct list_node { list_node* prev; // 前驱指针 list_node* next; // 后继指针 T data; // 数据域 };1.2 循环链表设计list采用循环链表设计即头节点的prev指向尾节点尾节点的next指向头节点。这种设计简化了边界条件的处理空链表时头节点指向自身插入第一个元素时头尾节点都指向该元素删除最后一个元素时恢复为空链表状态以下是链表节点的实现namespace lx { templateclass T struct list_node { T _data; list_nodeT*_prev; list_nodeT*_next; list_node(const TxT()) :_data(x) ,_prev(nullptr) ,_next(nullptr) {} }; }二、list的核心接口实现2.1 构造函数list提供了多种构造函数包括默认构造、拷贝构造、范围构造等list() //默认构造 { _head new node; _head-_prev_head; _head-_next_head; } list(const listTlt) //拷贝构造 { _head new node; _head-_prev_head; _head-_next_head; for(auto e: lt) { push_back(e); } }2.2 insertpush_backlist的插入操作是其核心优势时间复杂度为O(1)// 在指定位置前插入元素 iterator insert(iterator pos, const T x) { Node *curpos.node; Node *prevcur-_prev; newnode new Node(x); prev-_next newnode; //prev newnode pos newnode-_nextcur; cur-_prevnewnode; newnode-_prevprev; } // push_back实现 void push_back(const T x) { insert(end(),x); } // push_front实现 void push_front(const T x) { insert(begin(),x); }2.3 erasepop_back删除操作同样高效时间复杂度为O(1)// 删除指定位置的元素 iterator erase(iterator pos) { NodeT* curpos.node; NodeT* prevcur-_prev; //prev pos next NodeT* nextcur-_next; prev-_nextnext; next-_prevprev; delete cur; return iterator(next); } // pop_back实现 void pop_back() { if (!empty()) { erase(--end()); } } // pop_front实现 void pop_front() { if (!empty()) { erase(begin()); } }2.4 clearclear函数用于清空list中的有效元素void clear() { iterator it begin(); while(it!end()) { iterase(it); } }三、迭代器设计3.1 普通迭代器list的迭代器是双向迭代器支持前向和后向移动templateclass T,class Ref struct list_iterator { using Self list_iteratorT,Ref; using Nodelist_nodeT; Node*_node; list_iterator(Node*node) :_node(node) {} Ref operator*() { return _node-_data; } Selfoperator() { _node_node-_next; return *this; } Selfoperator(int) { Self tmp(*this); _node_node-_next; return tmp; } Selfoperator--() { _node_node-_prev; return *this; } Selfoperator--(int) { Self tmp(*this); _node_node-_prev; return tmp; } bool operator!(const Selfs)const { return _node!s._node; } bool operator(const Selfs)const { return _nodes._node; } };3.2 const迭代器const迭代器是容器内部定义的只读迭代器本质是一个“指向常量的指针”可以移动它但不能通过它修改所指向的元素。templateclass T,class Ref struct __list_iterator { typedef list_nodeT Node; Node*_node; typedef __list_iteratorT,Ref self; __list_iterator(Node*_node); : _node(node) {} const self operator*() { return _node-_data; } self operator() { _node_node-_next; return *this; } selfoperator(int) { self tmp(*this); _node _node-_next; return tmp; } selfoperator--() { _node_node-_prev; return *this; } Self operator--(int) { Self tmp(*this);//浅拷贝 _node _node-prev; return *this; } bool operator!(const Self it)const { return _node ! it._node; } bool operator(const Self it)const { return _node it._node; } };3.3 迭代器失效问题list的迭代器在以下情况下不会失效插入元素所有迭代器保持有效删除元素只有指向被删除元素的迭代器失效其他迭代器保持有效这是list相对于vector和deque的一个重要优势。四、list的优缺点总结6.1 优点高效的插入删除任意位置O(1)时间复杂度迭代器稳定性插入删除不会使其他迭代器失效动态大小不需要预分配内存支持双向遍历可以从前往后或从后往前遍历6.2 缺点随机访问慢需要遍历时间复杂度O(n)内存开销大每个元素需要额外存储两个指针缓存不友好节点分散在内存中缓存命中率低空间局部性差连续访问性能不如vector6.3 适用场景1.需要频繁在中间位置插入删除元素的场景2.元素大小较大移动成本高的场景3.需要稳定迭代器的场景4.不需要随机访问的场景五、与vector和deque的对比特性listvectordeque底层结构双向链表动态数组分段数组随机访问O(n)O(1)O(1)头部插入O(1)O(n)O(1)中间插入O(1)O(n)O(n)尾部插入O(1)O(1)平摊O(1)内存连续性否是部分连续迭代器失效插入不失效删除仅当前失效插入删除可能全部失效中间插入删除可能失效