双向循环链表是在双向链表的基础上发展的，双向链表的最后一个节点指向起始节点，起始节点的上一个节点指向最后一个节点，就得到双向循环链表。
双向循环链表比双向链表具有更多的优势，节点的增加和删除有很多优化的地方，从起点开始不必循环完整个链表就可以增加或删除节点。
首先定义双向链表的基本类和节点的基本类：
链表类的操作有几个核心的地方，第一个是判断是否为最后一个节点，通过链表的相关特性，如单向链表最后一个节点的next属性为None、单向循环链表的最后一个节点的next属性等于头部节点；第二个是使用游标来替代节点指向，这个在操作节点的时候需要有时还需要两个游标，但是对于双向节点而言只需要一个游标，通过当前节点的属性可以找到上下节点。
下面我们添加基本属性方法的逻辑，注意判断是否为最后一个节点的方式是：最后一个节点的下一个节点是否指向头部指向的节点，具体源码如下：
class Node():
def __init__(self,item):
self.item = item   #该节点的值
self.next = None   #连接下一个节点的值
self.prev = None   #连接上一个节点的值
class DoubelCircularLinkedList():
#"""双向循环列表类"""
def __init__(self):
self.head = None
def is_empty(self):
return self.head == None
def length(self):
if self.is_empty():
return 0
else:
cur = self.head
num = 0
while cur.next != self.head:
cur = cur.next
num += 1
return num+1
def ergotic(self):
if self.is_empty():
raise ValueError("ERROR NULL")
else:
cur = self.head.next
print(self.head.item)
while cur != self.head:
print(cur.item)
cur = cur.next
def add(self,item):   #头部增加节点
node = Node(item)
if self.is_empty():
node.next = node
node.prev = node
self.head = node
else:
node.next = self.head
node.prev = self.head.prev
self.head.prev.next = node
self.head = node
def append(self,item):
if self.is_empty():
self.add(item)
else:
node = Node(item)
self.head.prev.next = node
node.prev = self.head.prev
node.next = self.head
self.head.prev = node
def insert(self,index,item):
if index == 0:
self.add(item)
elif index > self.length() - 1:
self.append(item)
else:
cur = self.head
num = 1
while cur.next != self.head:
if num == index:
break
cur = cur.next
num += 1
node = Node(item)
node.next = cur.next
cur.next.prev = node
node.prev = cur
cur.next = node
def delet(self,index):
if self.is_empty():
raise ValueError("ERROR NULL")
elif index == 0 and self.length() == 1:
self.head = None
elif index == 0 and self.length() > 1:
self.head.prev.next = self.head.next
self.head.next.prev = self.head.prev
self.head = self.head.next
elif index == self.length() - 1:
self.head.prev = self.head.prev.prev
self.head.prev.next = self.head    #已经改变了self.head.prev的值
else:
cur = self.head
num = 1
while cur.next != self.head:
if num == index:
break
cur = cur.next
num += 1
cur.next.next.prev = cur
cur.next = cur.next.next
只以基本的思路实现基本的方法，对于双向循环链表而言还有很多可以优化的地方，正向遍历和逆向遍历获得结果的时间是不一样的。

//双向链表,将头结点和尾结点链接起来,就构成了双向循环链表 

//双向循环链表是将头结点的前驱指针指向了尾结点,同时将尾结点的后劲指针指向了头结点. 

//空表,头结点的前驱和后继指针均指向了自己,这也是判断双向循环链表是否为空的条件, 

//双向循环链表具有对称性 

//缺点,是要付出空间代价的

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

代码



#pragma mark 定义结点类型
typedef int ElemType;
typedef struct DuLNode
{
    ElemType data;
    struct DuLNode *prior;//指向前驱结点
    struct DuLNode *next; //指向后继结点

}DuLNode,*DuLinkList;

#pragma mark 带头结点的双向循环链表的基本操作


#pragma mark ---1.初始化空的双向循环链表
void InitList(DuLinkList *L)
{ /* 产生空的双向循环链表L */
    *L=(DuLinkList)malloc(sizeof(DuLNode));
    if(*L){
        (*L)->next=*L;
        (*L)->prior=*L;
    } else
        exit(0);
}

#pragma mark ---2.销毁双向循环链表
void DestroyList(DuLinkList L)
{
    DuLinkList q,p=L->next; /* p指向第一个结点 */
    while(p!=L) /* p没到表头 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    free(L);
    L=NULL;
}

#pragma mark ---2.将双向循环链表置空
void ClearList(DuLinkList L) /* 不改变L */
{
    DuLinkList q,p=L->next; /* p指向第一个结点 */
    while(p!=L) /* p没到表头 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    L->next=L->prior=L; /*头结点的两个指针域均指向自身 */
}
#pragma mark ---3 验证表是否为空表
int ListEmpty(DuLinkList L)
{
    /* 初始条件：线性表L已存在 */
   if(L->next==L&&L->prior==L)
   return 1;
   else
   return 0;

}

#pragma mark 计算元素的个数
int ListLength(DuLinkList L)
{ /* 初始条件：L已存在。操作结果： */
    int i=0;
    DuLinkList p=L->next; /* p指向第一个结点 */
    while(p!=L) /* p没到表头 */
    {
        i++;
        p=p->next;
    }
    return i;
}

#pragma mark 赋值
Status GetElem(DuLinkList L,int i,ElemType *e)
{ /* 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR */
    int j=1; /* j为计数器 */
    DuLinkList p=L->next; /* p指向第一个结点 */
    while(p!=L&&j<i)
    {
        p=p->next;
        j++;
    }
    if(p==L||j>i) /* 第i个元素不存在 */
        return ERROR;
    *e=p->data; /* 取第i个元素 */
    return OK;
}
//查找元素前驱

Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */
    /* 否则操作失败，pre_e无定义 */
    DuLinkList p=L->next->next; /* p指向第2个元素 */
    while(p!=L) /* p没到表头 */
    {
        if(p->data==cur_e)
        {
            *pre_e=p->prior->data;
            return OK;
        }
        p=p->next;
    }
    return ERROR;
}
//查找元素后继

Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)
{ /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */
    /* 否则操作失败，next_e无定义 */
    DuLinkList p=L->next->next; /* p指向第2个元素 */
    while(p!=L) /* p没到表头 */
    {
        if(p->prior->data==cur_e)
        {
            *next_e=p->data;
            return OK;
        }
        p=p->next;
    }
    return ERROR;
}
//查找元素地址

DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */
{ /* 在双向链表L中返回第i个元素的地址。i为0，返回头结点的地址。若第i个元素不存在，*/
    /* 返回NULL */
    int j;
    DuLinkList p=L; /* p指向头结点 */
    if(i<0||i>ListLength(L)) /* i值不合法 */
        return NULL;
    for(j=1;j<=i;j++)
        p=p->next;
    return p;
}
//元素的插入

Status ListInsert(DuLinkList L,int i,ElemType e)
{ /* 在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1 */
    /* 改进算法2.18，否则无法在第表长+1个结点之前插入元素 */
    DuLinkList p,s;
    if(i<1||i>ListLength(L)+1) /* i值不合法 */
        return ERROR;
    p=GetElemP(L,i-1); /* 在L中确定第i个元素前驱的位置指针p */
    if(!p) /* p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱) */
        return ERROR;
    s=(DuLinkList)malloc(sizeof(DuLNode));
    if(!s)
        exit(0);
    s->data=e;
    s->prior=p; /* 在第i-1个元素之后插入 */
    s->next=p->next;
    p->next->prior=s;
    p->next=s;
    return OK;
}

Status ListDelete(DuLinkList L,int i,ElemType *e)
{ /* 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长 */
    DuLinkList p;
    if(i<1) /* i值不合法 */
        return ERROR;
    p=GetElemP(L,i); /* 在L中确定第i个元素的位置指针p */
    if(!p) /* p=NULL,即第i个元素不存在 */
        return ERROR;
    *e=p->data;
    p->prior->next=p->next;
    p->next->prior=p->prior;
    free(p);
    return OK;
}


void visit(ElemType c)
{
    printf("%d ",c);
}


调用



int main(int argc, const char * argv[]) {
    // insert code here...
    DuLinkList L;
    ElemType e;
    int j;
    Status i;
    InitList(&L); /* 初始化单循环链表L */

    ListInsert(L, 1, 15);
    ListInsert(L, 2, 25);
    ListInsert(L, 3, 35);
    ListInsert(L, 4, 45);


    j=ListLength(L);
    printf("L中数据元素个数=%d\n",j);

    ListTraverse(L,visit);

    PriorElem(L,25,&e); /* 求元素5的前驱 */
    printf("25前面的元素的值为%d。\n",e);
    NextElem(L,35,&e); /* 求元素3的后继 */
    printf("35后面的元素的值为%d。\n",e);
    printf("L是否空 %d(1:空 0:否)\n",ListEmpty(L));


    //删除第二个元素
    ListDelete(L, 2, &e);
    j=ListLength(L);
    printf("L中数据元素个数=%d\n",j);
    ListTraverse(L,visit);
    return 0;
}


运行结果 


10.总结一下线性表的顺序实现和链试实现的比较 

比较两者的时间性能和空间性能进行比较 
1.位置查找运算 顺序表示随机存取,时间复杂度为O(1),单链表需要对表元素进行扫描,它的时间复杂度为O(n) 
2.定位运算 基本操作是比较 ,两者均为O(n) 
3.插入,删除运算 在顺序表和链表中,都需要进行定位. 

顺序表,其基本操作是元素的比较和结点的移动,平均时间复杂度为O(n). 

单链表,基本操作是元素的比较,尽管不需要移动,其平均时间复杂度依然为O(n).

各有优缺点,具体问题,具体分析

单链表的每个结点包括数据域和指针域,指针域需要占用额外的空间

从整体考虑,顺序表需要提前分配空间,如果分配过大,造成浪费,分配过小,内存溢出;单链表不需要预先分配空间,只要内存空间没有耗尽.单链表的结点就没有限制

    
思路分析
对于普通的双向循环链表，因为同其他节点相比，头尾元素是特别的，需要特别处理，所以在插入和删除节点的时候需要判断边界条件，这会让代码显得臃肿。头节点的特殊之处在于它的前驱是空指针，尾节点的特殊之处在于它的后继节点是空指针。
如果能令头尾元素不再特别，就可以省去边界条件的处理了。那么问题来了，如何让他们不特殊呢？那就需要让每个元素的前驱和后继都不为空。自然会想到在头元素之前，尾元素之后分别添加一个无意义的节点，使得他们的前驱和后继不空。
如此一来，一个空的链表从初始化就有了两个无意义的节点。然后你会发现，这里有了数据冗余，两个无意义的节点其实可以省略掉一个，让头尾节点都与同一个哨兵节点相连，到此，就形成了一个有哨兵的双向循环链表。哨兵的作用是可以降低运行时间中的常数因子。
当链表为空的时候，哨兵的前驱和后继都是其自身。（以上内容总结自《算法导论》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

双向循环链表C++实现
 
1.单链表：
结构图：

2.双向链表：

3.双向循环链表：
对于本程序中，则是给定一个_head  头结点，而不是指针，因为这样更加方便避免一些空判断问题

 

/*
版权信息：狼
文件名称：BidCirList.h
文件标识:
文件摘要：
    利用C++实现简单的双向链表功能。增，删，查，改
    //太烦了。。我直接给个 带头结点的  表
    //swap 移花接木已经是个给力的方法。。just try
当前版本：1.1
作    者：狼
完成时间：2015-12-13

*/
#ifndef _BIDCIRLIST_H
#define _BIDCIRLIST_H

#include"afxstd.h"

typedef int DataType;
typedef struct ListNode
{
    ListNode(DataType x=0)
    : _data(x)
    //默认初始化是自环而非  NULL
    , _prev(this)
    , _late(this)
    {}

    DataType _data;
    struct ListNode* _prev;
    struct ListNode* _late;
}ListNode;

class BidCirList
{
public:
    BidCirList()
        :_head(0)
    {}

    BidCirList(DataType *array, size_t n = 0)
        :_head(0)
    {
        size_t i = 0;
        while (n--)
        {
            InsertAter(array[i++]);
        }
    }

    BidCirList(BidCirList & list)
        :_head()
    {
        ListNode* cur = list._head._prev;
        while (cur)
        {
            InsertAter(cur->_data);
            cur = cur->_prev;
            if (cur == &list._head)
                break;
        }
    }

    ~BidCirList()
    {
        Destoty();
    }
    
    BidCirList operator+(BidCirList& list)
    {
        BidCirList tmp(*this);
        ListNode* cur = list._head._prev;

        while (cur != &list._head)
        {
            tmp.InsertAter(cur->_data);
            cur = cur->_prev;
        }
        return tmp;
    }

    BidCirList& operator = (BidCirList& list)
    {
        if (this != &list)
        {
            BidCirList S(list);

            Swap(S);
        }
        return *this;
    }

    //清空空间
    void Destoty()
    {
        ListNode*cur = &_head;
        while (cur->_prev != &_head)
        {
            DelPrev();
        }
    }

    //删除结点之前的结点。默认为头
    void DelPrev(ListNode *del = NULL)
    {
        if (_head._prev == &_head)
            return;
        if (del == NULL)
        {
            //删除头之前
            _head._prev = _head._prev->_prev;
            delete _head._prev->_late;

            _head._prev->_late = &_head;
        }
        else
        {
            del->_prev = del->_prev->_prev;
            delete del->_prev->_late;

            del->_prev->_late = del;
        }
    }

    //删除结点之后一个，，默认为头
    void DelLate(ListNode *del = NULL)
    {
        if (_head._prev == &_head)
            return;
        if (del == NULL)
        {
            _head._late = _head._late->_late;
            delete _head._late->_prev;

            _head._late->_prev = &_head;
        }
        else
        {
            del->_late = del->_late->_late;
            delete del->_late->_prev;

            del->_late->_prev = del;
        }
    }

    //在结点之前插入,默认为头
    void InsertAter(DataType x ,ListNode* ins= NULL)
    {
        ListNode* tmp = new ListNode(x);

        if (ins == NULL)
        {
            tmp->_prev = &_head;
            tmp->_late = _head._late;

            tmp->_late->_prev = tmp;
            tmp->_prev->_late = tmp;
        }
        else
        {
            tmp->_prev = ins;
            tmp->_late = ins->_late;

            tmp->_late->_prev = tmp;
            tmp->_prev->_late = tmp;
        }
    }

    ListNode* Find(DataType x)
    {
        ListNode* cur = _head._prev;
        while (cur)
        {
            if (cur == &_head)
                return NULL;
            if (cur->_data == x)
            {
                return cur;
            }
            cur = cur->_prev;
        }
    }

    void Erase(ListNode * node)
    {
        if (node == &_head)
        {
            return;
        }
        else
        {
            ListNode* tmp = node;
            node->_prev->_late = node->_late;
            node->_late->_prev = node->_prev;
            delete tmp;
            tmp = NULL;
        }
    }

    //反向打印
    void PrintPrev()
    {
        ListNode* cur = _head._prev;
        while (cur)
        {
            if (cur == &_head)
                break;
            cout << cur->_data << " -> ";
            cur = cur->_prev;
        }
        cout << " Over! " << endl;
    }
    //正向打印
    void PrintLate()
    {
        ListNode* cur = _head._late;

        while (cur)
        {
            if (cur == &_head)
                break;
            cout << cur->_data << " -> ";
            cur = cur->_late;
        }
        cout << " Over! " << endl;
    }

    void Swap(BidCirList &list)
    {
        ::swap(_head._prev->_late, list._head._prev->_late);
        ::swap(_head._prev, list._head._prev);

        ::swap(_head._late->_prev, list._head._late->_prev);
        ::swap(_head._late, list._head._late);

    }
    
private:
    ListNode _head;
};

#endif

 
转载于:https://www.cnblogs.com/lang5230/p/5046960.html