首页 > 代码库 > 第30课 双向链表的实现

第30课 双向链表的实现

1. 单链表的另一个缺陷

(1)单向性只能从头结点开始高效访问链表中的数据元素

(2)缺陷:如果需要逆序访问单链表中的数据元素,效率将极其低下(O(n2))

2. 双向链表

(1)设计思路:在“单链表”的结点中增加一个prev指针,用于指向当前结点的前驱结点

技术分享 

(2)继承层次结构

技术分享 

(3)DualLinkList的定义

template <typename T>
class DualLinkList : public List<T>
{
protected:
    struct Node : public Object{
        T value;
        Node* next;
        Node* prev;
    };
    
    mutable struct : public Object{
        char reserved[sizeof(T)];
        Node* next;
        Node* prev;    
    }m_header;
    
    //...
};

3. 双向链表的主要操作

(1)插入元素操作

技术分享 

(2)删除元素操作

技术分享 

【编程实验】双向链表的实现

//Iterator.h

//DualLinkList.h

//main.cpp

4. 开放性问题

(1)DualLinkList和LinkList中存在很多完全一样的代码,如何进行重构降低代码的冗余性?冗余代码的出现是否意味着DualLinkList和LinkList之间应该是继承关系

(2)自行实现双向链表的两个子类(DualStaticLinkList和 DualCircleList子类)

5. 小结

(1)双向链表是为了弥补单链表的缺陷而重新设计的

(2)在概念上,双向链表不是单链表,没有继承关系

(3)双向链表中的游标能够直接访问当前结点的前驱和后继

(4)双向链表是线性表概念的最终实现更贴近理论上的线性表

第30课 双向链表的实现