有哨兵的双向循环链表、单向循环链表

  • 思路分析

    对于普通的双向循环链表,因为同其他节点相比,头尾元素是特别的,需要特别处理,所以在插入和删除节点的时候需要判断边界条件,这会让代码显得臃肿。头节点的特殊之处在于它的前驱是空指针,尾节点的特殊之处在于它的后继节点是空指针。

    如果能令头尾元素不再特别,就可以省去边界条件的处理了。那么问题来了,如何让他们不特殊呢?那就需要让每个元素的前驱和后继都不为空。自然会想到在头元素之前,尾元素之后分别添加一个无意义的节点,使得他们的前驱和后继不空。

    如此一来,一个空的链表从初始化就有了两个无意义的节点。然后你会发现,这里有了数据冗余,两个无意义的节点其实可以省略掉一个,让头尾节点都与同一个哨兵节点相连,到此,就形成了一个有哨兵的双向循环链表。哨兵的作用是可以降低运行时间中的常数因子。

    当链表为空的时候,哨兵的前驱和后继都是其自身。(以上内容总结自《算法导论》10.2例题)下面附上一个简单的C++实现。

struct Node
{
    Node* pPrev;    //前驱节点
    Node* pNext;    //后继节点
    int   key;        //当前节点的键值
};

class DoubleLinkedList
{
public:
    DoubleLinkedList();
    ~DoubleLinkedList();

    Node* Search(int key);    //查找键值为key的节点,若没有找到返回空指针
    void Insert(int key);                    //在头部插入一个键值为key的节点
    void Delete(Node* p);                    //删除节点p
private:
    Node m_sentinel;
};

DoubleLinkedList::DoubleLinkedList()
{
    m_sentinel.pPrev = &m_sentinel;    //初始化时链表为空,哨兵的前驱和后继都指向其自身。
    m_sentinel.pNext = &m_sentinel;
}

DoubleLinkedList::~DoubleLinkedList()
{
    Node* pCurrent = m_sentinel.pNext;
    Node* pNext = nullptr;
    while(pCurrent != &m_sentinel)
    {
        pNext = pCurrent->pNext;
        delete pCurrent;    //循环的每一步负责删除当前节点,并将pCurrent指向下一个节点,直到回到哨兵为止。
        pCurrent = pNext;
    }
}

Node* DoubleLinkedList::Search(int key)   //运行时间为O(n)
{
    Node* pCurrent = m_sentinel.pNext;
    while(pCurrent != &m_sentinel && pCurrent->key != key)
        pCurrent = pCurrent->pNext;
    return pCurrent == &m_sentinel ? nullptr : pCurrent;
}

void DoubleLinkedList::Insert(int key)     //运行时间为O(1)
{
    Node* pNew = new Node;                //构建新节点
    pNew->key = key;
    pNew->pPrev = &m_sentinel;             //新节点与前驱后继相互关联
    pNew->pNext = m_sentinel.pNext;
    m_sentinel.pNext->pPrev = pNew;
    m_sentinel.pNext = pNew;
}

void DoubleLinkedList::Delete(Node* p)    //运行时间为O(n)
{
    p->pPrev->pNext = p->pNext;    //将自身的前驱和后继相互关联
    p->pNext->pPrev = p->pPrev;
    delete p;                                     //删除自身
}
  • 优化方法

    Search方法的每一次循环都需要两步测试pCurrent != &m_sentinel 和 pCurrent->key != key,能不能省略前一个,只留下pCurrent->key != key?
    我们可以利用哨兵的键值,让其等于要找的key,这样一来,即使链表里没有找到key,也会在pCurrent回到哨兵的时候及时跳出循环。优化后的Search方法是这样的:

Node* DoubleLinkedList::Search(int key)
{
    Node* pCurrent = m_sentinel.pNext;
    m_sentinel.key = key;
    while(pCurrent->key != key)
        pCurrent = pCurrent->pNext;
    return pCurrent == &m_sentinel ? nullptr : pCurrent;
}
  • 带哨兵的单向循环链表
struct Node    //与双向链表不同的是,每个节点只保存一个后继节点
{
    Node* pNext;
    int key;
};

class SingleLinkedList
{
public:
    SingleLinkedList();
    ~SingleLinkedList();
    Node* Search(int key);    //Search和Insert方法的运行时间与双向链表一样,Search依然是O(n)
    void Insert(int key);        //Insert 依然是 O(1)
    void Delete(Node* p);       //但是Delete有所不同,因为删除过程需要拿到待删除元素的前驱和后继,其中前驱节点必须通过一次遍历查找得到,所以Delete的运行时间和Search一样,都是O(n)
private:
    Node m_sentinel;
};

SingleLinkedList::SingleLinkedList()
{
    m_sentinel.pNext = &m_sentinel;
}

SingleLinkedList::~SingleLinkedList()
{
    Node* pCurrent = m_sentinel.pNext;
    Node* pNext = nullptr;
    while(pCurrent != &m_sentinel)
    {
        pNext = pCurrent->pNext;
        delete pCurrent;
        pCurrent = pNext;
    }
}

Node* SingleLinkedList::Search(int key)
{
    m_sentinel.key = key;
    Node* pCurrent = m_sentinel.pNext;
    while(pCurrent->key != key)
        pCurrent = pCurrent->pNext;
    return pCurrent == &m_sentinel ? nullptr : pCurrent;
}

void SingleLinkedList::Insert(int key)
{
    Node* pNew = new Node;
    pNew->pNext = m_sentinel.pNext;
    pNew->key = key;
    m_sentinel.pNext = pNew;
}

void SingleLinkedList::Delete(Node* p)
{
    Node* pCurrent = m_sentinel.pNext;
    Node* pPrevious = &m_sentinel;
    while(pCurrent != p)
    {
        pPrevious = pCurrent;
        pCurrent = pCurrent->pNext;
    }
    pPrevious->pNext = pCurrent->pNext;
    delete pCurrent;
}
  • 将双向和单向链表加以对比,我们发现在插入和查找频繁,而删除不频繁的场景下,使用单向链表可以节省空间,而在需要频繁删除的场景下,使用双向链表,可以显著节省运行时间。

转载于:https://www.cnblogs.com/meixiaogua/p/9677957.html

    原文作者:weixin_30783913
    原文地址: https://blog.csdn.net/weixin_30783913/article/details/99870479
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞