33_双向循环链表的实现

关键词：双向循环链表

0. 课程目标

  • 使用Linux内核链表实现双向循环链表
  • template < typename T > class DualCircleList

1. 双向循环链表的设计思路

数据结点之间在逻辑上构成双向循环链表，头结点仅用于在结点的定位。

双向循环链表原理图

双向循环链表继承层次结构图

2. 双向循环链表的实现思路

  • 通过模板定义DualCircleList类，继承自DualLinkList类
  • 在DualCircleList内部使用Linux内核链表进行实现
  • 使用struct list_head定义DualCircleList的头结点
  • 特殊处理：循环遍历时忽略头结点

3. 双向循环链表的实现要点

  • 通过list_head进行目标结点定位position(i)
  • 通过list_entry将list_head指针转换为目标结点指针
  • 通过list_for_each实现int find(const T& e)函数
  • 遍历函数中的next()和pre()需要考虑跳过头结点

4. 代码实现

DualCircleList.h

#ifndef DUALCIRCLELIST_H
#define DUALCIRCLELIST_H

#include "LinuxList.h"
#include "DualLinkList.h"

namespace DTLib
{

template < typename T >
class DualCircleList : public DualLinkList<T>
{
protected:
    struct Node : public Object
    {
        list_head head;
        T value;
    };

    list_head m_header;
    list_head* m_current;
    list_head* position(int i) const;
    int mod(int i) const;

public:
    DualCircleList();
    bool insert(const T& e);               // O(n)
    bool insert(int i, const T& e);        // O(n)
    bool remove(int i) ;                   // O(n)
    bool set(int i, const T& e);           // O(n)
    T get(int i) const;            // O(n)
    bool get(int i, T& e) const;           // O(n)
    int find(const T &e) const;            // O(n)
    int length() const ;                   // O(1)
    void clear();                          // O(n)

    /* 游标遍历相关函数 */
    bool move(int i, int step);
    bool end();
    bool next();
    bool pre();
    T current();
    ~DualCircleList();
};

template < typename T >
list_head* DualCircleList<T>::position(int i) const
{
    list_head* ret = const_cast<list_head*>(&m_header);

    for(int pos=0; pos<i; ++pos)
    {
        ret = ret->next;
    }

    return ret;
}

template < typename T >
int DualCircleList<T>::mod(int i) const
{
    return (this->m_length == 0) ? 0 : (i % this->m_length);
}

}

template < typename T >
DualCircleList<T>::DualCircleList()
{
    m_current = NULL;
    this->m_length = 0;
    this->m_step = 1;

    INIT_LIST_HEAD(&m_header);  //  初始化头结点
}

template < typename T >
bool DualCircleList<T>::insert(const T& e)
{
    return insert(this->m_length, e);
}

template < typename T >
bool DualCircleList<T>::insert(int i, const T& e)
{
    bool ret = true;

    i = i % (this->m_length + 1);

    Node* node = new Node();

    if( node != NULL )
    {
        node->value = e;
        list_add_tail(&(node->head), position(i)->next);
        ++this->m_length;
    }
    else
    {
        THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to insert new element in DualCircleList...");
    }

    return ret;
}

template < typename T >
bool DualCircleList<T>::remove(int i)
{
    bool ret = true;

    i = mod(i);

    ret = ((0 <= i) && (i < this->m_length));

    if( ret )
    {
        list_head* toDel = position(i)->next;

        if( this->m_current == toDel )
        {
            this->m_current = this->m_current->next;
        }

        list_del(toDel);
        --this->m_length;
        delete list_entry(toDel, Node, head);
    }

    return ret;
}

template < typename T >
bool DualCircleList<T>::set(int i, const T& e)
{
    bool ret = true;

    i = mod(i);

    ret = ((0 <= i) && (i < this->m_length));

    if( ret )
    {
        list_entry(position(i)->next, Node, head)->value = e;
    }

    return ret;
}

template < typename T >
T DualCircleList<T>::get(int i) const
{
    T ret;

    if( get(i, ret) )
    {
        return ret;
    }
    else
    {
        THROW_EXCEPTION(IndexOutOfBoundsException, "Invaild parameter i to get element...");
    }

    return ret;
}

template < typename T >
bool DualCircleList<T>::get(int i, T& e) const
{
    bool ret = true;

    i = mod(i);

    ret = ((0 <= i) && (i < this->m_length));

    if( ret )
    {
        e = list_entry(position(i)->next, Node, head)->value;
    }

    return ret;
}

template < typename T >
int DualCircleList<T>::find(const T &e) const
{
    int ret = -1;
    int i = 0;
    list_head* slider = NULL;

    list_for_each(slider, &m_header)
    {
        if( list_entry(slider, Node, head)->value == e )
        {
            ret = i;
            break;
        }

        ++i;
    }

    return ret;
}

template < typename T >
int DualCircleList<T>::length() const
{
    return this->m_length;
}

template < typename T >
void DualCircleList<T>::clear()
{
    while(this->m_length > 0)
    {
        remove(0);
    }
}


template < typename T >
bool DualCircleList<T>::move(int i, int step = 1)
{
    bool ret = true;

    i = mod(i);

    ret = ret && (i >= 0) && (i < this->m_length) && (step > 0);

    if( ret )
    {
        this->m_current =position(i)->next;
        this->m_step = step;
    }

    return ret;
}

template < typename T >
bool DualCircleList<T>::end()
{
    return (this->m_length == 0) || (this->m_current == NULL);
}

template < typename T >
bool DualCircleList<T>::next()
{
    int i = 0;

    while( ( i<this->m_step ) && ( !end() ) )
    {
        if(this->m_current != &this->m_header)
        {
            this->m_current = this->m_current->next;
            ++i;
        }
        else
        {
            this->m_current = this->m_current->next;
        }
    }

    if( this->m_current == &this->m_header )
    {
        this->m_current = this->m_current;
    }

    return (i == this->m_step);
}

template < typename T >
bool DualCircleList<T>::pre()
{
    int i = 0;

    while( ( i<this->m_step ) && ( !end() ) )
    {
        if(this->m_current != &this->m_header)
        {
            this->m_current = this->m_current->prev;
            ++i;
        }
        else
        {
            this->m_current = this->m_current->prev;
        }
    }

    if( this->m_current == &this->m_header )
    {
        this->m_current = this->m_current;
    }

    return (i == this->m_step);
}

template < typename T >
T DualCircleList<T>::current()
{
    if( !end() )
    {
        return list_entry(this->m_current, Node, head)->value;
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No value at current position...");
    }
}
template < typename T >
DualCircleList<T>::~DualCircleList()
{
    clear();
}

#endif // DUALCIRCLELIST_H

5. 小结

  • Linux内核链表是带头结点的双向循环链表
  • DualCircleList使用Linux内核链表进行内部实现
  • DualCircleList在循环遍历时需要跳过头结点
  • 将list_head指针转换为目标结点指针时，使用list_entry宏

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • Linux内核设计与实现笔记（6）----内核数据结构
    内核数据结构 本章介绍几种Linux内核常用的内建数据结构，其中最常用的有： 链表 队列 映射 二叉树 1. 链表...
    micro虾米阅读 2,422评论 0赞 4
  • 数据结构基础概念篇
    一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且确保经过这...
    Winterfell_Z阅读 6,006评论 0赞 13
  • 数据结构——链表
    目录 1、属性 2、链表和数组的区别 2.1、数组概述 2.2、数组和链表优缺点 2.3、链表和数组的比较 3、单...
    我哈啊哈啊哈阅读 2,850评论 1赞 41
  • 互联网营销
    最近参与了一系列在网上的营销推广类活动。主要是在微博、微信两大平台上。一个是参与微博转发，微信分享。另一个创意微博...
    许远山阅读 261评论 0赞 1
  • 也谈雾霾
    也谈“雾霾” 这个冬天，生活在帝都，离不开的一个关键词，一定是雾霾。 刚开始接触到雾霾，完全没有在意，生活中的隐雷...
    日光知不初阅读 145评论 0赞 0