c++模拟实现list——详讲双链表--链表
在C语言中我们已经模拟实现了list,现在对比c++看看二者的区别
双链表————详讲
个人博客主页:
个人主页
个人码云
码云代码
文章目录
-
目录
文章目录
编辑
前言
一、list是什么?
二、list的使用
三、模拟实现list和搭建list的结构
1.节点结构
2.迭代器的详讲(这是和vector的区别)
3.list基础结构
4.修改器
四、测试list
总结
链表就像这个火车
前言
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就是带头双向链表,头节点存有链表的最后一个节点的地址和第一个节点的地址(链表的物理空间是不连续的,每一个节点的物理空间都是独立的),每一个节点中都存有上一个节点的地址和下一个节点的地址。
二、list的使用
list中的接口比较多,此处类似,只需要掌握如何正确的使用,然后再去深入研究背后的原理,已达到可扩展 的能力。以下为list中一些常见的重要接口。
#include #include #include #include using namespace std; #include void test_list1() { //定义链表和插入数据 list lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); //迭代器的遍历 list::iterator it = lt.begin(); while (it != lt.end()) { cout
还没有评论,来说两句吧...