循环双向链表：

循环双向链表的定义：

typedef struct CDLNode{
    LElemType data;
    struct CDLNode * pre;
    struct CDLNode * next;
    CDLNode(LElemType Data=0,struct CDLNode* Pre=NULL,struct CDLNode* Next=NULL){
        data=Data;  pre=Pre;    next=Next;
    }
}CDLNode,*CDLinkList;

循环双向链表基本操作的实现：

（1）、初始化操作  InitDuLinkList( &L )

（2）、建立单链表的操作  CreateDuLinkList（&L , n）

（3）、判断一个线性表是否为空表ListIsEmpty(L)

（4）、求线性表的长度ListLength( L )

（5）、取线性表中的第i个元素GetElem(L,i,&e)

（6）、查找元素e在线性表中的位序LocateElem(L,e)

（7）、插入操作ListInsert(&L,i,e)

（8）、删除操作LIstDelete(&L,i,&e)

（1）、初始化操作  InitDuLinkList( &L )

void InitCDLinkList(CDLinkList &L){
    L=new CDLNode(inf,NULL,NULL);
    L->next=L->pre;
    L->pre=L->next;
}

（2）、建立单链表的操作  CreateDuLinkList（&L , n）

void CreateLinkList_Tail(CDLinkList &L,int n=0){ //尾插法
    InitCDLinkList(L);
    CDLinkList p=L,Pre=L;
    Pre=L;
    LElemType Data;
    for(int i=1;i<=n;i++){
        printf("请输入第%d个data值:\n",i);
        cin>>Data;
        p=new CDLNode(Data,Pre,L);
        Pre->next=p;
        Pre=p;
    }
    L->pre=Pre;
}


void CreateLinkList_Head(CDLinkList &L,int n=0){ //头插法
    InitCDLinkList(L);
    CDLinkList p=L,Pre=L,s;
    LElemType Data;
    for(int i=1;i<=n;i++){
        printf("请输入第%d个data值:\n",i);
        cin>>Data;
        p=new CDLNode(Data,L,L->next);
        s=L->next;
        if(i==1){
            L->pre=p;
            p->next=L;
        }
        if(s){
            s->pre=p;
        }
        L->next=p;
    }
}

 

（3）、判断一个线性表是否为空表ListIsEmpty(L)

bool ListIsEmpty(CDLinkList &L){
    return L->pre==L->next?false:true;
}

（4）、求线性表的长度ListLength( L )

int ListLength(CDLinkList &L){
    CDLinkList p=L->next;
    int Len=0;
    while(p!=L){
        Len++;
        p=p->next;
    }
    return Len;
}

（5）、取线性表中的第i个元素GetElem(L,i,&e)

void GetElem(CDLinkList &L,int i,LElemType &e){
    int j=1;
    CDLinkList p=L->next;
    while(p!=L&&j<i){
        j++;p=p->next;
    }
    if(p==L||j>i){
        printf("\" GetElem \" index %d error!!!\n",i);
        return ;
    }
    e=p->data;
}

（6）、查找元素e在线性表中的位序LocateElem(L,e)

int LocateElem(CDLinkList &L,LElemType e){
    int j=1;
    CDLinkList p=L->next;
    while(p!=L&&p->data!=e){
        p=p->next;
        j++;
    }
    if(p==L){
        printf("\"LocateElem\" not found %d\n",e);
        return -1;
    }
    return j;
}

（7）、插入操作ListInsert(&L,i,e)

void ListInsert(CDLinkList &L ,int i,LElemType e){
    int j=0;
    CDLinkList p=L,s;
    while(j<i-1&&p->next!=L){
        j++;p=p->next;
    }
    if((p==L||j>i-1)&&i!=1){
        printf("\"ListInsert\" index : %d error!!!\n",i);
    }else{
        s=new CDLNode(e,p,p->next);
        p->next->pre=s;
        p->next=s;
    }
}

（8）、删除操作LIstDelete(&L,i,&e)

 

void ListDelete(CDLinkList &L,int i,LElemType &e){
    int j=0;
    CDLinkList p=L,s;
    while(j<i-1&&p->next!=L){
        j++;p=p->next;
    }
    if((p==L||j>i-1)&&i!=1){
        printf("\"ListInsert\" index : %d error!!!\n",i);
    }else{
        s=p->next;
        p->next=s->next;
        s->next->pre=p;
        e=s->data;
        delete s;
    }
}

 
完整的调试代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#define LElemType int
#define inf 0x3f3f3f3f
using namespace std;
typedef struct CDLNode{
    LElemType data;
    struct CDLNode * pre;
    struct CDLNode * next;
    CDLNode(LElemType Data=0,struct CDLNode* Pre=NULL,struct CDLNode* Next=NULL){
        data=Data;  pre=Pre;    next=Next;
    }
}CDLNode,*CDLinkList;
void InitCDLinkList(CDLinkList &L){
    L=new CDLNode(inf,NULL,NULL);
    L->next=L->pre;
    L->pre=L->next;
}

void CreateLinkList_Tail(CDLinkList &L,int n=0){ //尾插法
    InitCDLinkList(L);
    CDLinkList p=L,Pre=L;
    Pre=L;
    LElemType Data;
    for(int i=1;i<=n;i++){
        printf("请输入第%d个data值:\n",i);
        cin>>Data;
        p=new CDLNode(Data,Pre,L);
        Pre->next=p;
        Pre=p;
    }
    L->pre=Pre;
}

void CreateLinkList_Head(CDLinkList &L,int n=0){ //头插法
    InitCDLinkList(L);
    CDLinkList p=L,Pre=L,s;
    LElemType Data;
    for(int i=1;i<=n;i++){
        printf("请输入第%d个data值:\n",i);
        cin>>Data;
        p=new CDLNode(Data,L,L->next);
        s=L->next;
        if(i==1){
            L->pre=p;
            p->next=L;
        }
        if(s){
            s->pre=p;
        }
        L->next=p;
    }
}
void OutputCDLinkList(CDLinkList &L){
    CDLinkList p=L->next;
    printf("\n顺序输出:\n");
    while(p!=L){
        printf("%d\n",p->data);
        p=p->next;
    }
    p=p->pre;
    printf("\n逆序输出:\n");
    while(p!=L){
        printf("%d\n",p->data);
        p=p->pre;
    }
    printf("\n");
}
bool ListIsEmpty(CDLinkList &L){
    return L->pre==L->next?false:true;
}
int ListLength(CDLinkList &L){
    CDLinkList p=L->next;
    int Len=0;
    while(p!=L){
        Len++;
        p=p->next;
    }
    return Len;
}
void GetElem(CDLinkList &L,int i,LElemType &e){
    int j=1;
    CDLinkList p=L->next;
    while(p!=L&&j<i){
        j++;p=p->next;
    }
    if(p==L||j>i){
        printf("\" GetElem \" index %d error!!!\n",i);
        return ;
    }
    e=p->data;
}
int LocateElem(CDLinkList &L,LElemType e){
    int j=1;
    CDLinkList p=L->next;
    while(p!=L&&p->data!=e){
        p=p->next;
        j++;
    }
    if(p==L){
        printf("\"LocateElem\" not found %d\n",e);
        return -1;
    }
    return j;
}
void ListInsert(CDLinkList &L ,int i,LElemType e){
    int j=0;
    CDLinkList p=L,s;
    while(j<i-1&&p->next!=L){
        j++;p=p->next;
    }
    if((p==L||j>i-1)&&i!=1){
        printf("\"ListInsert\" index : %d error!!!\n",i);
    }else{
        s=new CDLNode(e,p,p->next);
        p->next->pre=s;
        p->next=s;
    }
}
void ListDelete(CDLinkList &L,int i,LElemType &e){
    int j=0;
    CDLinkList p=L,s;
    while(j<i-1&&p->next!=L){
        j++;p=p->next;
    }
    if((p==L||j>i-1)&&i!=1){
        printf("\"ListInsert\" index : %d error!!!\n",i);
    }else{
        s=p->next;
        p->next=s->next;
        s->next->pre=p;
        e=s->data;
        delete s;
    }
}
int main()
{
    CDLinkList La;
    LElemType e,t;
    InitCDLinkList(La);
    if(!ListIsEmpty(La)){
        printf("La is empty!!!\n");
    }
    //头插、尾插
    //CreateLinkList_Tail(La,5);
    CreateLinkList_Head(La,5);
    OutputCDLinkList(La);

    /*
    获取长度，获取下标对应的值，判断是否非空
    int Len=ListLength(La);
    if(ListIsEmpty(La)){
        for(int i=0;i<=Len+1;i++){
            e=inf;
            GetElem(La,i,e);
            e!=inf?printf("%d\n",e):1;
        }
    }
    */

    /*
    查找
    printf("请输入一个代查找的数:\n");
    scanf("%d",&e);

    t=LocateElem(La,e);
    if(t!=-1){
        printf("%d Locate : %d\n",e,t);
    }
    */

    /*
    ListInsert(La,6,123);
    OutputCDLinkList(La);
    */

    e=inf;
    ListDelete(La,5,e);
    if(e!=inf){
        printf("Delete : %d\n",t);
    }
    OutputCDLinkList(La);
}


 

双向循环链表
一、相关概念
1.什么是线性表
2.什么是顺序表
3.什么是链表
4.单链表、双链表、循环单链表、循环双链表
5.为什么需要循环链表？
6.为什么需要双向链表？
7.头结点和首结点
8.常见的栈和队列与线性表的关系
二、实现过程
1.提供节点类：DupNode
2.提供双向循环链表的实现类：DoubleLinkedTable
3.提供长度(length)、打印(display)、清空(clear)等方法
5.提供根据下标删除的方法：remove(int i)
6.提供根据下标获取方法(get(int i))、根据指定结点获取前一个结点方法(getPrior)、根据指定结点获取后一个结点信息方法(getNext)
三、总结
1.链表的缺点
2.链表的优点
3.如何使用链表


前言：

线性表是我们最常用的一种数据结构，线性表包含顺序表和链表，顺序表典型应用就是我们常用的ArrayList，链表的典型应用其中就有我们常用的LinkedList。LinkedList他的底层就是使用链表来存储数据元素的。这篇文章用以总结链表中的双向循环链表，为单链表的结点增加一个指向前驱的指针域，单链表就变成了双链表，将双链表的头尾相连，双链表就成了双向循环链表。

一、相关概念
第一部分主要介绍下和链表有关的相关概念，这里给出的概念都是书本上的官方定义，并不是作者胡诌的，为什么给出这些官方的定义呢 ？因为笔者认为官方给出的定义，是对一个概念最本质的解释，它的解释经过了时间的考验，被认为是解释的最合理深入简明扼要的。
1.什么是线性表
线性表是由n个数据元素构成的有限序列，n为线性表的表长，当n为0时表示当前线性表是空表。线性表有且仅有一个开始结点和终端节点。且开始结点没有前驱，终端节点没有后继，其余节点有且仅有一个前驱和后继。线性表一般分为顺序表和链表。
2.什么是顺序表
采用顺序存储结构存储数据元素的线性表被称为顺序表，顺序表，要求逻辑上相邻的数据元素在物理内存的存储上也是相邻的，当在顺序表的第i（0<=i<=n）插入一个数据元素时，需要后移n-i+1个数据元素，当删除第i个元素时需要移动n-i个数据元素。java实现顺序表
3.什么是链表
采用链式存储结构存储数据元素的线性表被称为链表，链表不要求逻辑上相邻的数据元素内存上必须相邻，链表的每个节点都包含两部分，一部分是数据域用以存储数据，一部分是指针域用以存储指向相邻结点的指针或者引用。链表通过每个节点的指针域将一串数据串联成链。当结点只有一个指针域时，被称为单链表。单链表-含头结点、单链表-不含头结点
4.单链表、双链表、循环单链表、循环双链表
当链表的结点只有一个指针域时被称为单链表，循环单链表是单链表的一种特殊变化，只是将尾结点又指向了头结点（也可能是首结点）。

当链表的结点有两个时，一个指向前驱，一个指向后继这种链表便是双链表，循环双链表是双链表的一种特殊变化，只是将尾结点又指向了头结点（也可能是首结点）。

所有的链表的实现均有两种方式，一种是带有头结点，一种是不带有头结点的实现方式，两种实现略有区别。
5.为什么需要循环链表？
循环链表一般就是指循环单链表，不特殊指明是双向循环链表，那么该名称描述的就是单项循环链表，之所以需要循环链表是因为在操作系统中，循环链表有特定的应用场景，在一些场景中，链表中的元素需要循环的执行，但是在实际的开发中应用最多的还是双向循环链表。
6.为什么需要双向链表？
若是给定了一个结点，根据当前结点获取该结点的上一个结点，那么我们是没有办法直接获取的，只能是遍历链表，但若是使用了双向链表，我们则可以直接获取到该元素的上一个结点，时间复杂度就变成了O(1)。所以双向链表的实际应用意义更强，将双向链表的首尾相连就成了双向循环链表，双向循环链表的应用最常见的就是LinkedList。
7.头结点和首结点
首节点：真正存储第一个数据元素的结点被称为首节点。

头结点：当链表采用带头结点方式实现时，会创建一个数据域为null的节点，该节点的指针域存储的指针指向首节点的指针，他的唯一作用是标识链表的开始，带有头结点的链表更易于操作。
8.常见的栈和队列与线性表的关系
栈和队列也是常见的数据结构，但是栈和队列并不是线性表的一种，线性表只包含了顺序表和链表。不过我们可以将栈和队列看成是特殊的线性表。怎么特殊呢，栈是被限制了只能在一端进行插入和删除操作的线性表，所以栈的特性是先入后出，队列是被限制了只能在一端插入另一端删除的线性表，所以队列的特性是先入先出。既然栈和队列都是特殊的线性表，那么栈和队列自然就可以使用线性表来实现了，通常可以使用线性表中的顺序表和队列来实现栈和队列。
二、实现过程
单链表-含头结点

单链表-不含头结点

上面是两种单链表的实现方式，其实无论是双链表还是双向循环链表他的实现方式都是类似的，区别都很有限，上面两篇文章里详细实现了单链表的各种常用方法，因此在该文章里只会总结必须用到的几个方法，比如插入、删除、清空、长度、判空、根据下标获取等，其他方法的实现都不难，就不一一展示了。
1.提供节点类：DupNode
双向循环链表的实现，我们首先必须为其提供一个结点类，该类需要有三个属性，一个数据域，一个指向前驱的指针域，还有一个指向后继的指针域，然后提供必要的构造方法即可，如下：
/**
 * @author pcc
 * @version 1.0.0
 * @className DupNode
 * @date 2021-04-19 16:43
 * 该类是双向链表的结点类
 * 该类包含了数据域，后继指针域、前驱指针域三个属性。
 */
public class DupNode {
    Object object;
    DupNode prior;//前驱指针域
    DupNode next;//后继指针域

    public DupNode(){
        this(null);
    }
    public DupNode(Object object){
        this(object,null,null);
    }
    public DupNode(Object object,DupNode prior,DupNode next){
        this.object = object;
        this.prior = prior;
        this.next = next;
    }
}

2.提供双向循环链表的实现类：DoubleLinkedTable
采用带有头结点的方式实现双向循环链表，因此我们需要定义一个头结点。然后提供初始化它的构造器。值得注意的是，在初始化头结点时，我们必须将他的前驱和后继都声明为自己，这样才是一个空的双向循环链表。
public class DoubleLinkedTable {
    //头结点
    DupNode head;

    public DoubleLinkedTable(){
        head = new DupNode();
        head.prior = head;
        head.next = head;
    }
}

3.提供长度(length)、打印(display)、清空(clear)等方法
这些方法的实现原理都很简单，求链表长就是遍历链表计数即可，打印也是遍历链表，清空则是将头结点的前驱和后继都声明为自己，下面是三个方法的实现：
    //长度
    public int length(){
        DupNode node = head.next;
        int j = 0;
        while(!node.equals(head)){
            j++;
            node = node.next;
        }
        return j;
    }

    //打印
    public void display(){
        DupNode node = head.next;
        while(!node.equals(head)){
            System.out.println(node.object);
            node = node.next;
        }
    }
    //清空
    public void clear(){
        head.next = head;
        head.prior = head;
    }

4.提供根据下标插入方法：insert(int i,Object object)

学习双向循环链表建议还是先学习单链表，会了单链表双向循环链表就是窗户纸，一桶就破，因为他们的实现思路都是一样的，只是稍微的变化而已。单链表的遍历我们的退出条件是找到尾结点就退出（node.next == null）,循环链表肯定没有尾结点了，退出循环的条件就成了碰到头结点再退出（node ==head）,另外一点区别就是双向循环链表的赋值问题，我们需要为新结点的前驱指针和后继指针赋值，同时需要为新结点的上一个节点的后继后继指针从新赋值，还需要为新节点的后继结点的前驱指针重新赋值，代码实现如下：
   /**
     * 思路：
     * 1.寻找下标为i-1的数据元素，注意退出循环的条件应该是node！=head
     * 2.赋值即可，循环链表的核心就是空表也会有循环体系
     * 3，赋值时，i+1位置的元素应该是node.next 所以，应为node.next最后赋值
     * @param i
     * @param object
     * @throws Exception
     */
    public void insert(int i,Object object) throws Exception{
        if(i<0 || i>length())
            throw new Exception("下标不合法");
         DupNode node = head;
         int j = 0;
         while(!node.next.equals(head) && j<i){
             j++;
             node = node.next;
         }
//         DupNode newNode = new DupNode(object);
//         node.next.prior = newNode;
//         newNode.prior = node;
//         newNode.next = node.next;
//         node.next = newNode;

        //写成以下这种和上面注释的部分，效果一样，无区别
         DupNode newNode = new DupNode(object,node,node.next);
         node.next.prior = newNode;
         node.next = newNode;
    }

到了这里，我们就可以初步测试下，双向链表的插入是否有效了，下面创建一个测试类测试下，如下图所示，将几个元素插入到了双向循环链表中，然后输出结果正常，说明插入方法实现无误。有了这些头插法、尾插法直接根据下标即可轻松实现，这里不展示了。


5.提供根据下标删除的方法：remove(int i)
实现思路其实和单链表的删除是没有区别的：寻找到下标为i-1的数据元素，然后将他的后继更改为i+1的数据元素，然后将下标为i+1的数据元素的前驱更改为，下标为i-1的数据元素即可，实现如下：
    //删除
    public void remove(int i) throws Exception{
        if(i<0 || i>length()-1)
            throw new Exception("下标不合法");
        DupNode node = head;
        int j = 0;
        while(!node.next.equals(head) && j<i){
            j++;
            node = node.next;
        }
        node.next = node.next.next;
        node.next.prior = node;
    }

然后来测试下删除方法，就测试下删除下标为2的元素吧，理论上删除后，输出的应该是：张三、李四、赵柳，如下图可见，输出无误，可见删除方法实现时无误的。


6.提供根据下标获取方法(get(int i))、根据指定结点获取前一个结点方法(getPrior)、根据指定结点获取后一个结点信息方法(getNext)
上面也说过，双向链表解决的问题就是在获取指定结点的上一个结点时是无需遍历链表的，这样大大节省了时间成本，这里就测试下该方法的实现。三个方法的实现如下所示：
    //根据下标获取
    public Object get(int i) throws Exception{
        return getNode(i).object;
    }

    //根据下标获取其前一个元素
    public Object getPrior(int i) throws Exception{
        return getNode(i).prior.object;
    }

    //根据下标获取其后一个元素
    public Object getNext(int i) throws Exception{
        return getNode(i).next.object;
    }

    public DupNode getNode(int i) throws Exception{
        if(i<0 || i>length())
            throw new Exception("下标不合法");
        DupNode node = head.next;
        int j =0;
        while(node.equals(head) && j<i){
            j++;
            node = node.next;
        }
        return node;
    }

下面我们来测试下这三个方法是否正确，使用李四所在结点来进行测试，李四的下标应该是1，传入1分别运行三个方法，若是正确应该输出的是：李四、张三、王五，如下图可见结果正确。


三、总结
1.链表的缺点
线性表的两种实现顺序表、链表。相比于顺序表，链表的缺点就是查找元素比较慢，查找元素的时间复杂度是O(n),而顺序表的时间复杂度是O(1)，在查找上顺序表要优于链表,链表查找慢，就是它的缺点了，但是双向循环链表在一定程度上减少了查找时的时间复杂度，但是依然是不及顺序表的查找效率的，所以具体的使用场景还是静态数据适合使用顺序表，动态数据适合使用链表。
2.链表的优点
顺序表在指定下标x位置插入元素，组需要后移n-x+1个元素，若是删除下标为x的数据元素，则需要向前移动n-x个数据元素，但是链表则不需要移动任何元素，链表需要做的只是找到对应的元素将指针域中的指针进行更新即可。链表的插入和删除的时间复杂度可以看成O(1)，而顺序表插入和删除操作的都是O(n).所以链表的优点就是插入和删除比较快。
3.如何使用链表
所以综合链表的优点与缺点我们可以发现，顺序表更适合存储“静态”型数据，而链表更适合存储“动态”型数据，何为动态型呢，就是那些插入、删除操作比较频繁的数据。这类数据更适合使用链表存储。而数据结构不易改变的数据使用顺序表存储更合适。顺序表可类比java中的ArrayList，链表可类比java中的LinkedList。这两者都是顺序表与链表的典型应用。

/**
 * 循环双链表的简单实现
 * 
 * @author Linging
 * @date 2019/2/9
 * 
 * 注：java自带的集合包有实现双链表
 */

public class DoubleList<T> {
	//表头
	public DNode<T> head;
	
	//节点个数
	private int Count;
	
	//定义节点结构体
	class DNode<T>{
		private DNode pre;    //链接前一个节点
		private DNode next;   //链接下一个节点
		private T value;      //节点值
		
		public DNode(T value, DNode pre, DNode next) {
			this.next = next;
			this.pre = pre;
			this.value = value;
		}
	}
	
	//构造函数
	public DoubleList() {
		//创建头节点并制为null。（头节点为空节点）
		head = new DNode<T>(null, null, null);
		head.next = head.pre = head;
		Count = 0;
	}
	
	//返回节点个数
	public int size() {
		return Count;
	}
	
	//判断双链表是否为空
	public boolean isEmpty() {
		return Count == 0;
	}
	
	//返回index位置的节点
	public DNode<T> getNode (int index){
		if(index <= 0 || index > Count) 
			throw new IndexOutOfBoundsException();
		
		//正向查找
		if(index <= Count/2) {
			DNode<T> node = head.next;  //指向首节点
			for(int i = 1; i < index; i++) {
				node = node.next;
			}
			return node;
		}
		
		//反向查找
		DNode<T> node = head.pre;    //指向尾节点
		int rindex = Count - index;
		for(int j = 0; j < rindex; j++) {
			node = node.pre;
		}
		return node;
	}
	
	//获取第index位置的节点值
	public T get(int index) {
		return getNode(index).value;
	}
	
	//获取第一个节点的值
	public T getFirst() {
		return getNode(1).value;
	}
	
	//获取最后一个节点的值
	public T getLast() {
		return getNode(Count).value;
	}
	
	//将节点t插入到index位置
	public void insert(int index, T t) {
		if(index == 1) {
			DNode<T> tnode = new DNode<T>(t, head, head.next);
			head.next.pre = tnode;
			head.next = tnode;
			Count++;
			return;
		}
		 DNode<T> inode = getNode(index);
		 DNode<T> tnode = new DNode<T>(t, inode.pre, inode);
		 inode.pre.next = tnode;
		 inode.pre = tnode;
		 Count++;
		 return ;
	}
	
	 // 将节点追加到链表的末尾
	    public void appendLast(T t) {
	       DNode<T> node = new DNode<T>(t, head.pre,head);
	       head.pre.next = node;
	       head.pre = node;
	       Count++;
	    }
	     
	  //打印全部节点
	     public void print() {
	    	 for(int i = 1; i <= Count; i++) {
	    		 System.out.println(getNode(i).value);
	    	 }
	     }
	   
	  //删除index位置的节点
	   public void delete(int index) {
		   DNode<T> node = getNode(index);
		   node.next.pre = node.pre;
		   node.pre.next = node.next;
		   node = null;
		   Count--;
	   }
	   
	public static void main(String[] args) {
		DoubleList<String> dl = new DoubleList<String>();
		try {
			//按顺序依次插入节点1,2,3,4
			System.out.println("依次插入节点1、2、3、4：");
			dl.appendLast("1");
			dl.appendLast("2");
			dl.appendLast("3");
			dl.appendLast("4");
			dl.print();
			System.out.println("节点个数为："+dl.Count);
			
			//在双链表第4个节点处插入一个节点7
			System.out.println("\n"+"在双链表第4个节点处插入一个节点7：");
			dl.insert(4, "7");
			dl.print();
			System.out.println("节点个数为："+dl.Count);
			
			//删除第3个节点
			System.out.println("\n"+"删除第3个节点");
			dl.delete(3);
			dl.print();
			System.out.println("节点个数为："+dl.Count);
			
			//打印双链表
			System.out.println("\n"+"打印双链表：");
			dl.print();	
			System.out.println("节点个数为："+dl.Count);
			System.out.println("双链表是否为空："+dl.isEmpty());
			
		}catch(IndexOutOfBoundsException e) {
			e.getStackTrace();
		}
		
	}
}

转载请注明出处：http://www.cnblogs.com/skywang12345/p/3561803.html

我们常用的是单链表的算法。虽然双链表和循环双链表的算法常常被拿来作为一种设计的思路，也常假想有一个循环双链表，对它进行操作，实际上我从没动手写过循环双链表。

在手动实现单链表的习题多道以后，有了一种对简单代码的熟悉度，以及轻微的掌控感。我觉得自己知道自己写的是什么，并能在大脑中视觉化执行路径了。作为一个开始时，在自己大脑中跑代码会有轻微恐慌的人来说，这是一个进步了。

也让我明白，行动是打开枷锁的钥匙。不敢说唯一，因为或许还要其他的途径。

通过写算法的过程，我感受到的不仅仅是作为一个coder写作的乐趣，更能慢慢实践那些听到的道理。很长时间，我会在一天中不专注的时间里，有轻度的抑郁症患者才有的症状。比如，怀疑一个明显的道理，逼着自己去证明，证明不了就会引起下一次的雪崩式的恐慌。担心自己就此分崩离析。然后任由它去后才发现，不过是柳暗花明的又一番景象，什么都没改变。

开始深深赞同，颠倒妄想或许指的就是这些念头。善护念的重要性就隐含其中。我不清楚颠倒妄想究竟能不能带来物质上变化，曾经我担心会让自己变得不能思考，变得更笨或者怎样，发现并没有。只是当你的念头沉浸在痛苦的妄想中时，内心好痛苦。

我说的话都是自己经历过，痛苦过。我很多次挣扎时，希望有人过来和我讲一讲其中的道理，告诉我不要怕。没有任何人来。但是我很感激，它逼着你去思考，去从其他途径去了解我们是什么。最感激的是遇到了书中的老师，遇到了佛经中那些让我升起信心的佛陀的话。

好像跑偏了。但是，我想说的仍然是：写代码是一种思考。思考本身是无为法，那么对其他事物的思考，和写代码都是殊途同归。

我们总是在自己的脑海中构建一个交织的世界。每天吸收新的知识，新的知识将添加进原有的知识网路。每天的思考，会让头脑中的知识互相之间再次加强连接或者形成新的连接。

这样的过程便会让你认知像指数于洋爆炸。想一想，人真的是一个神奇物种。可以不断去套索认知的边界。

希望以上的文字能给你带来的是信心而不是困惑。

回到循环双链表的构建问题。

由一道题目开始：


  
判断一个带头的循环双链表是否对称


思路：首先得构建一个循环双链表，主要是明晰结点的特征是有两个指针域。单纯的双链表会有两个结点的指针域为空：头结点的prior指针域和尾结点的next指针域。循环就是让头结点的prior指针域指向尾结点，尾结点的next指针指向头结点。判断是否对称只需要两个方向遍历，如果有奇数个结点，两个方向游走的指针相同时表示对称。偶数个结点，判断的是正向指针的next结点与反向指针的prior结点相同并且数值相同。正反向遍历时，结点值相同时才相向移动。否则，途中有不同的就退出，判断为不对称。

代码会更清晰：



#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>


using namespace std;
typedef int ElemType;
#define MAX 100

typedef struct Node
{
    ElemType data;
    struct Node *prior; // 前向指针
    struct Node *next; // 后向指针
}SNode, *SList;

// 生成一个循环双链表，数值随机生成
// 返回指向生成链表的头结点指针

SList generateSymList(int n) // n是结点个数
{
    srand((unsigned)time(NULL));
    // 定义头结点
    SList sl = (SList)malloc(sizeof(SNode));
    sl->prior = NULL;
    sl->next = NULL;

    SNode *r = sl;

    //尾插法建立链表：元素递增有序
    for(int i = 0; i < n; i++)
    {
        SNode *s = (SNode*)malloc(sizeof(SNode));
        s->data = rand() % MAX; // 随机值
        s->prior = r;
        s->next = sl; //

        r->next = s;
        sl->prior = s; //需要更新的是sl的prior，r跟踪是工作结点

        r = s;
    }
    return sl;
}


bool IsSymmetrical(SList sl) // sl是循环双链表的头结点
{
    SNode *p = sl->next; // 第一个结点
    SNode *q = sl->prior; // 最后一个结点

    while(p && q)
    {
        if(p == q || (p->next == q && q->prior == p && p->data == q->data))// 如果比较到p和q相等或者对称
        {
            return true;
        }
        else
        {
            if(p->data == q->data) // 只有数据相同时，才有机会进行下一次的比较
            {
                p = p->next;
                q = q->prior;
            }
            else // 否则直接判定不对称
            {
                return false;
            }
        }
    }
    return false;
}

int main()
{
    int n;
    cout << "Input the number of nodes: ";
    cin >> n ;
    SList sl = generateSymList(n);

    // 正向输出
    SNode *p = sl->next; //指向第一个结点
    cout << "正向 : ";
    while(p != sl->prior) //p指向最后一个结点时结束
    {
        cout << p->data << " ";
        p = p->next;
    }
    cout << p->data; //最后一个结点值需要特别输出

    cout << endl;

    // 反向输出
    p = sl->prior; //指向最后一个结点
    cout << "反向 : ";
    while(p != sl->next) //p指向第一个结点时结束
    {
        cout << p->data << " ";
        p = p->prior;
    }
    cout << p->data; //第一个结点也需要特别输出
    cout << endl;

    // 题目的主要逻辑

    bool b = IsSymmetrical(sl);
    if(b)
    {
        cout << "Yes!" << endl;
    }
    else
    {
        cout << "No!" << endl;
    }
    return 0; 
}

如果要代码解析的话，先看结点特征:



typedef struct Node
{
    ElemType data;
    struct Node *prior; // 前向指针
    struct Node *next; // 后向指针
}SNode, *SList;

生成过程：

SList generateSymList(int n) // n是结点个数
{
    srand((unsigned)time(NULL));
    // 定义头结点
    SList sl = (SList)malloc(sizeof(SNode));
    sl->prior = NULL;
    sl->next = NULL;

    SNode *r = sl;

    //尾插法建立链表
    for(int i = 0; i < n; i++)
    {
        SNode *s = (SNode*)malloc(sizeof(SNode));
        s->data = rand() % MAX; // 随机值
        s->prior = r;
        s->next = sl; //新的结点next域指向头结点，因为用r在跟踪当前工作结点，因此，这个结点的next域会更新为指向下一个结点

        r->next = s; // 这句就是在更新新结点的前驱的next域指向新结点
        sl->prior = s; //需要更新的是sl的prior，r跟踪是工作结点

        r = s;
    }
    return sl;
}

判断过程：



bool IsSymmetrical(SList sl) // sl是循环双链表的头结点
{
    SNode *p = sl->next; // 第一个结点
    SNode *q = sl->prior; // 最后一个结点

    while(p && q)
    {
        if(p == q || (p->next == q && q->prior == p && p->data == q->data))// 如果比较到p和q相等或者对称
        {
            return true;
        }
        else
        {
            if(p->data == q->data) // 只有数据相同时，才有机会进行下一次的比较
            {
                p = p->next;
                q = q->prior;
            }
            else // 否则直接判定不对称
            {
                return false;
            }
        }
    }
    return false;
}

这种是直接反应思路的一种代码结构，看着有些丑，至于怎样重构，我没有思路。

以上。