首页 > 代码库 > 第33课 双向循环链表的实现
第33课 双向循环链表的实现
1. DTLib中双向链表的设计思路
(1)数据结点之间在逻辑上构成双向循环,这有别于Linux内核链表的实现。
(2)头结点仅用于结点的定位,而Linux内核链表是将头结点作为循环的一部分。
2. 实现思路
(1)通过模板定义DualCircleList类,继承自DualLinkList类
(2)在DualCircleList内部使用Linux内核链表进行实现(另类实现)
(3)使用struct list_head定义DualCircleList的头结点
(4)特殊处理:循环遍历时忽略头结点
3. 实现要点
(1)通过list_head进行目标结点定位(position(i))
(2)通过list_entry将list_head指针转换为目标结点指针
(3)通过list_for_each实现int find(const T& e)函数
(4)遍历函数中的next和prev需要考虑跳过头结点
【编程实验】基于Linux内核链表的双向循环链表
//DualCircleList.h
4.思考题:pn1==pn2吗?
struct Node : public Object //注意Object是个虚基类 { list_head head; T value; }; Node node; list_head* ld = &node.head; Node* pn1 = reinterpret_cast<Node*>(ld); //error, 遗漏了虚函数表指针字段 Node* pn2 = list_entry(ld, Node, head); //ok
5. 小结
(1)Linux内核链表是带头结点的双向循环链表
(2)DualCircleList使用Linux内核链表进行内部实现
(3)DualCircleList在循环遍历时需要跳过头结点
(4)将list_head指针转换为目标结点指针时,使用list_entry宏。
第33课 双向循环链表的实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。