30_双向链表的实现

2018-07-10 本文已影响6人编程半岛

关键词：双向链表

0. 单链表的另一个缺陷

单向性：只能从头结点开始高效访问链表中的数据元素
缺陷：如果需要逆向访问单链表中的数据元素，则会及其低效

int main()
{
    LinkList<int> list;
    for(int i=0; i<5; ++i)  // O(n)
    {
        list.insert(o, i);
    }

    for(int i=list.length()-1; i>=0; --i)  // O(n^2)
    {
        cout << list.get(i) << endl;
    }

    return 0;
}

在LinkList中插入元素的时间复杂度为O(n)，逆向访问的时间复杂度为O(n^2)。

1. 双向链表设计思路

在单链表的结点中增加一个指针pre，用于指向当前结点的前驱结点。

双向链表原理图

双向链表继承层次结构图

2. 双向链表实现

DualLinkList.h

#ifndef DUALLINKLIST_H
#define DUALLINKLIST_H

#include "List.h"
#include "Exception.h"

namespace DTLib
{

template < typename T >
class DualLinkList : public List<T>
{
protected:
    struct Node : public Object
    {
        T value;
        Node* next;
        Node* pre;
    };

    mutable struct : public Object {
        char reserved[sizeof(T)];
        Node* next;
        Node* pre;
    } m_header;      // mutable突破const的限制
    int m_length;
    Node* m_current;    // 定义游标 m_current
    int m_step;
    Node* position(int i) const;  // 定位元素， 返回i的前一个结点的指针
    virtual Node* create();      // 内部进行create封装
    virtual void destroy(Node* pn);     // 内部进行destroy封装

public:
    DualLinkList();
    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)
    virtual 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)

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

template < typename T >
DualLinkList<T>::DualLinkList()        // 构造函数, 设置成员初始状态
{
    m_header.next = NULL;
    m_header.pre = NULL;
    m_length = 0;
    m_step = 1;
    m_current = NULL;
}

template < typename T>
typename DualLinkList<T>::Node* DualLinkList<T>::position(int i) const
{
    Node* ret = reinterpret_cast<Node*>(&m_header);

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

    return ret;
}

template < typename T >
typename DualLinkList<T>::Node* DualLinkList<T>::create()
{
    return new Node();
}

template < typename T >
void DualLinkList<T>::DualLinkList::destroy(Node* pn)
{
    delete pn;
}

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

    if( ret )
    {
        Node* node = create();

        if( node != NULL )
        {
            Node* current = position(i);
            Node*  next = current->next;

            node->value = e;
            node->next = next;
            current->next = node;

            if( current != reinterpret_cast<Node*>(&m_header) ) // 判断current结点是否为头结点
            {
                node->pre = current;    // 如果不是头结点，则将node->pre = current
            }
            else
            {
                node->pre = NULL;   // 如果是头结点，则node->pre = NULL
            }

            if( next != NULL )
            {
                next->pre = node;   // 如果next不为空，将next->pre = node；如果next为空，则什么也不用做
            }

            ++m_length;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to insert new element...");
        }
    }

    return ret;
}

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

template <typename T>
bool DualLinkList<T>::remove(int i)
{
    bool ret = ((i >= 0) && (i < m_length));

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

        if(  m_current == toDel )       // 如果游标指针指向要删除的指针
        {
            m_current = toDel->next;    // 移动游标指针
        }

        current->next = next;
        if( next != NULL )
        {
            next->pre = toDel->pre;
        }

        --m_length;                     // 先将length-1
        destroy(toDel);                 // 然后再destroy对象，因为如果destroy如果出现异常，此时的length信息还是正确的
    }

    return ret;
}

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

    if( ret )
    {
        position(i)->next->value = e;       // i的位置为current的next
    }

    return ret;
}

template < typename T >
T DualLinkList<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 DualLinkList<T>::get(int i, T& e) const
{
    bool ret = ((i >= 0) && (i < m_length));

    if( ret )
    {
        e = position(i)->next->value;
    }

    return ret;
}

template < typename T >
int DualLinkList<T>::find(const T &e) const
{
    int ret = -1;
    int pos = 0;
    Node* node = m_header.next;

    while( node )
    {
        if( node->value == e )
        {
            ret = pos;
            break;
        }
        else
        {
            node = node->next;
            ++pos;
        }
    }

    return ret;
}

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

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

template < typename T >
bool DualLinkList<T>::move(int i, int step = 1)
{
    bool ret = (i >= 0) && (i < m_length) && (step > 0);

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

    return ret;
}

template < typename T >
bool DualLinkList<T>::end()
{
    return m_current == NULL;
}

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

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

    return (i == m_step);
}

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

    while( ( i<m_step ) && ( !end() ) )
    {
        m_current = m_current->pre;
        ++i;
    }

    return (i == m_step);
}

template < typename T >
T DualLinkList<T>::current()
{
    if( !end() )
    {
        return m_current->value;
    }
    else
    {
        THROW_EXCEPTION(InvalidOperationExcetion, "No value at current position...");
    }
}

template < typename T >
DualLinkList<T>:: ~DualLinkList()
{
    clear();
}

}

#endif // DUALLINKLIST_H

3. 小结

双向链表是为了弥补单链表的缺陷而重新设计的
在概念上，双向链表不是单链表， 没有继承关系
双向链表中的游标能够直接访问当前结点的前驱和后继
双向链表时线性表概念的最终实现，更加贴近理论上的线性表

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

30_双向链表的实现

0. 单链表的另一个缺陷

1. 双向链表设计思路

2. 双向链表实现

3. 小结

猜你喜欢

热点阅读