第二代营销网站,全渠道营销的概念,个人网站设计,hexo和wordpress相比前言 链表作为一个像是用“链子”链接起来的容器#xff0c;在数据的存储等方面极为便捷。虽然单链表单独在实际的应用中没用什么作用#xff0c;但是当他可以结合其他结构#xff0c;比如哈希桶之类的。不过今天学习的list其实是一个带头双向链表。
言归正传#xff0c;让…前言 链表作为一个像是用“链子”链接起来的容器在数据的存储等方面极为便捷。虽然单链表单独在实际的应用中没用什么作用但是当他可以结合其他结构比如哈希桶之类的。不过今天学习的list其实是一个带头双向链表。
言归正传让我们看一下list的特性。
一、list的特性
这里我还是推荐去cplusplus上阅读英文原文档。这里我总结了几条 1. list 是可以在常数范围内 在任意位置进行插入和删除的序列式容器 并且该容器 可以前后双向迭代。 2. list 的底层是 双向链表结构 双向链表中每个 元素存储在互不相关的独立节点 中在节点中通过指针指向其前一个元素和后一个元素。 3. list 与 forward_list 非常相似最主要的不同在于 forward_list是单链表 只能朝前迭代已让其更简单高效。 4. 与其他的序列式容器相比 (array vector deque) list 通常 在任意位置进行插入、移除元素的执行效率更好。 5. 与其他序列式容器相比 list 和 forward_list 最大的缺陷是 不支持任意位置的随机访问 比如要访问 list的第6 个元素必须从已知的位置 ( 比如头部或者尾部 ) 迭代到该位置在这段位置上迭代需要线性的时间开销list 还需要一些 额外的空间 以保存每个节点的相关联信息 ( 对于存储类型较小元素的大 list 来说这可能是一个重要的因素)。 其物理模型简化后如下图 二、list的基本结构
前面我们提到list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。那么他每个小结点的结构就变得清楚明了了。 templateclass Tstruct list_node{list_nodeT* _prev;list_nodeT* _next;T _val;list_node(const T val T()): _prev(nullptr), _next(nullptr), _val(val){} };
随后我们就可以写list的本体了 templateclass Tclass list{typedef list_nodeT Node;private:Node* _head;//哨兵位size_t _size;};
加一个表示size的数据是因为list的空间是不连续的。
三、list的基础构造 void empty_init(){_head new Node;_head-_prev _head;_head-_next _head;_size 0;}list(){empty_init();}
将empty经行再封装是因为这样的构造函数设计可以方便地创建空的list对象并且避免了在创建list对象时必须显式地指定初始大小。同时通过将初始化代码封装在empty_init()函数中可以简化list类的实现提高代码的可读性和可维护性。
四、list的插入与删除
与vector不同的是list的其他几种构造或多或少的依赖插入而且哨兵位的初始化就可以继续后面的操作。当然插入和删除是list的重要点。 我们先从尾插写起如图当插入一个节点时我们可以先新建一个新的节点将值存入其中。然后将末尾(_head-_prev)的_next与newnode链接然后将new的_prev与末尾链接最后将头节点的_prev指向newnode,newnode的_next与_head链接。 void push_back(const Tx){Node* newnode new Node(x);Node* tail _head-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;_size;}
而对于任意位置插入其实和上面的逻辑相似。 //在pos之前插入返回新插入元素位置iterator insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;_size;return newnode;}
与次对立的是list任意位置的删除。逻辑就是他反过来。 iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;--_size;return next;}
但是list的删除面临着迭代器的失效前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节 点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。
比如下面的案例
void TestListIterator1()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){l.erase(it); it;}// erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给
其赋值改正后
void TestListIterator()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){l.erase(it); // it l.erase(it);}
}
当这两个比较泛型的插入与删除实现后其余代码就变得简单了。
//拷贝构造 list(const listT lt)//list(const list lt){empty_init();for (auto e : lt){push_back(e);}}
//析构函数~list(){clear();delete _head;_head nullptr;}
//头插void push_front(const T x){insert(begin(), x);}
//尾删void pop_back(){erase(--end());}
//头删void pop_front(){erase(begin());}
//清空void clear(){iterator it begin();while (it ! end()){it erase(it);}_size 0;}
五、list的迭代器
list的迭代器我们要实现的主要就是他的与--问题而就是返回当前位置的_next --就是返回当前位置的_prev。
templateclass T,class Ref,class Ptrstruct _list_iterator{typedef list_nodeT Node;typedef _list_iteratorT, Ref,Ptr self;Node* _node;_list_iterator(Node* node):_node(node){}Ref operator*(){return _node-_val;}Ptr operator-(){return _node-_val;}self operator() {_node _node-_next;return *this;}self operator(int)//后置{self tmp(*this);_node _node-_next;return tmp;}self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}bool operator!(const self it)const{return _node ! it._node;}bool operator(const self it)const{return _node it._node;}};
_list_iterator类模板的三个类型参数分别为T元素类型、Ref引用类型和Ptr指针类型。这个类包含一个成员变量_node它是一个指向list_node对象的指针用于存储当前迭代器所指向的节点。这里的Ref与Ptr主要用于分辨const与非const.
六、list与vector的对比 vector list 底 层 结 构 动态顺序表一段连续空间 带头结点的双向循环链表 随 机 访 问 支持随机访问访问某个元素效率 O(1) 不支持随机访问访问某个元素 效率 O(N) 插 入 和 删 除 任意位置插入和删除效率低需要搬移元素时间复杂 度为 O(N) 插入时有可能需要增容增容开辟新空 间拷贝元素释放旧空间导致效率更低 任意位置插入和删除效率高不 需要搬移元素时间复杂度为 O(1) 空 间 利 用 率 底层为连续空间不容易造成内存碎片空间利用率 高缓存利用率高 底层节点动态开辟小节点容易 造成内存碎片空间利用率低 缓存利用率低 迭 代 器 原生态指针 对原生态指针 ( 节点指针 ) 进行封装 迭 代 器 失 效 在插入元素时要给所有的迭代器重新赋值因为插入 元素有可能会导致重新扩容致使原来迭代器失效删 除时当前迭代器需要重新赋值否则会失效 插入元素不会导致迭代器失效 删除元素时只会导致当前迭代 器失效其他迭代器不受影响 使 用 场 景 需要高效存储支持随机访问不关心插入删除效率 大量插入和删除操作不关心随 机访问
