《夏目友人帐》

List是C标准模板库(STL)中的一个成员其本质为带头双向循环链表。

不同于连续的、紧密排列的数组容器VectorList容器的内部是由双向链表构成的使得它在插入和删除操作上就如同行云流水一般顺畅不需移动其它元素。

1.1

List容器的底层结构是一个经典的带头双向循环链表。

每个节点包含

这种结构赋予了List灵动的特性它能够轻松地在任意位置增加或移除元素而这种操作几乎是与容器大小无关的体现了时间复杂度上的优势。

但这种优势的代价是与数组相比List在访问元素时的速度会较慢因为它需要从头开始遍历。

这也决定了list的更适合频繁插入的动态数据。

template

例如如果你正在管理一个动态变化的列表如任务调度、人员排队等场景List的特性将大放异彩。

但是如果你的应用场景更多地需要随机访问元素那么向量Vector或者数组可能是更佳的选择。

因为List的顺序访问性能相比之下会显得有些力不从心。

所以如果需要频繁随机的访问数据那么选择vector容器如果需要频繁插入删除数据那么选择list容器排序不要选择list

1.3

插入与删除List的插入和删除操作非常高效它可以在任意位置快速地添加或移除元素而不需要像连续内存容器那样进行大量元素的移动。

多种构造类都应该包含多种构造函数支持迭代器迭代器是C重要的特性我们写的list

框架搭建

:_next(nullptr),_prev(nullptr),_data(x){}//ListNode(T

T())

};这里使用模版来适配更多的情景然后基本的数据前后指针都很简单。

在编写一个构造函数构造函数使用初始化列表并不是必须使用。

析构函数避免野指针出现将指针赋值为nullptr就可以了。

2.2

我们先进行简单的框架书写构造函数需要创建一个头结点因为我们要创建双向循环链表所以头尾都要指向头结点本身。

templateclass

};接下来我们来逐步完成功能书写由于我们还没有进行迭代器的书写

2.3

--当然是不能的因为链表的物理地址并不是连续的对原生指针的或–操作是没有意义的所以我们需要自行编写迭代器类对原生指针进行封装来满足我们特殊的和–操作。

先简单写一下templateclass

_node-_data;}};这样迭代器类就大致写好了那么一般我们的迭代器应该还要支持const不然我们传入一个不可修改的链表const

list

l,就会反生报错那么我们还要书写一份const版的迭代器。

如果进行编写那么是不是会有大部分与刚才我们书写的迭代器重复

都是一样的只有operator*()和operator-()返回值不一致

listT

这些操作受影响的是operator*()和operator-()返回值该情况下链表本身是只读的又因为不能将权限进行扩大所以返回值应该也是只读的const。

那这样就发现了不同常迭代器应该为

const

,所以有没有一种办法可以简单解决呢当然有了我们设置一个新模版带有三个参数创建的时候就传入对应参数

我们将模版修改为这样

_node-_data;}那么类实例化的时候传入对应参数就好了

typedef

const_iterator;这样就实现了迭代器的创建是不是就非常简洁了呢

功能实现

使用迭代器即可注意end()是头结点因为遍历过程中全部遍历后会回到头结点所以直接判断是否为头结点就能控制结束位置。

typedef

插入操作我们很熟悉步骤是创建一个新节点然后通过改变指针指向来完成插入操作

来看尾插操作

}任意位置插入操作思路依然是对前后节点与新节点的指针指向进行操作来完成插入。

void

删除操作同样是使用指针操作来达到删除的效果。

注意要对删除的节点进行释放空间操作delete不然会发生内存泄漏

void

}需要注意的是任意位置删除因为使用了迭代器删除后会造成迭代器失效所以需要更新迭代器返回被删除节点的下一个节点的迭代器即可。

3.4

的模拟实现其中最重要莫过于迭代器的封装类的书写这是前所未有的操作对于我来说我是第一次使用这种结构。

通过list

的模拟实现也帮我们巩固了类与对象的知识也强化了指针操作的思路。

欢迎大家讨论分析。

Thanks♪(ω)谢谢阅读