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