一、双向循环链表
 

 
 
二、用C语言实现双向循环链表
 
1、构造存储结构
 
typedef int datatype;

typedef struct doublelist{
      datatype data;
      struct doublelist *next, *prev;
}double_list, *double_plist;
 
2、初始化
 
 
 
初始化主要工作：①申请头结点内存空间；②head->next = head; head->prev = head;
 
 
 
3、插入结点
 
(1)、向p指向的结点后面插入new指向的结点
 
 
 
 
步骤①：new->next = p->next;
 步骤②：p->next->prev = new;
 步骤③：new->prev =p;
 步骤④：p->next = new;
 
 
/* 向p指向的结点后面插入new指向的结点 */
void insert_doublelist_behind(double_plist p, double_plist new)
{
      new->next = p->next;
      p->next->prev = new;
      new->prev = p;
      p->next = new;
}
 
(2)、向p指向的结点前面插入new指向的结点
 
 
 
 
步骤①：new->prev = p->prev;
 步骤②：p->prev->next = new;
 步骤③：new->next = p;
 步骤④：p->prev = new;
 
 
/* 向p指向的结点前面插入new指向的结点 */
void insert_doublelist_tail(double_plist p, double_plist new)
{
      new->prev = p->prev;
      p->prev->next = new;
      new->next = p;
      p->prev = new;
}
 
4、删除结点
 
(1)、删除p指向的结点后面的结点
 
 
 
 
t = p->next;
 p->next = t->next;
 t->next->prev = p;
 free(t);
 
 
/* 删除p指向的结点后面的结点 */
void delete_doublelist_post(double_plist p)
{      
      double_plist t = NULL;
      
      t = p->next;
      p->next = t->next;
      t->next->prev = p;
      free(t);
}
 
(2)、删除p指向的结点前面的结点
 
 
 
 
t = p->prev;
 p->prev = t->prev;
 t->prev->next = p;
 free(t);
 
 
/* 删除p指向的结点前面的结点 */
void delete_doublelist_prev(double_plist p)
{
      double_plist t = NULL;

      t = p->prev;
      p->prev = t->prev;
      t->prev->next = p;
      free(t);
}
 
(3)、删除p指向的结点
 
 
 
 
p->prev->next = p->next;
 p->next->prev = p->prev;
 free(p);
 
 
/*  删除p指向的结点*/
void delete_doublelist(double_plist p)
{
      p->prev->next = p->next;
      p->next->prev = p->prev;
      free(p);
}
 
5、判断链表是否为空
 
 
 
判断head->next == head 是否成立即可。
 
 
/* 判断链表是否为空 */
bool isempty_doublelist(double_plist head)
{
      if (head == head->next)
      {
            return true;
      }
      else
      {
            return false;
      }  
}
 
6、打印链表
 
void show_doublelist(double_plist head)
{
      double_plist p = NULL;

      for (p = head->next; p != head; p = p->next)
      {
            printf("%d\t", p->data);
      }
      printf("\n");
}
 

 
三、练习题
 
 
 
用双向循环链表实顺序递增存储若干自然数，比如输入一个整数10，则建立一个双向循环链表，里面的每个节点分别存放1，2，3，4，5，6，7，8，9，10，然后通过某些操作，将其重新排列成1，3，5，7，9，10，8，6，4，2，即奇数升序偶数降序，并在屏幕上打印出来。
 
 
1、创建链表
 
/* 创建链表 */
void create_doublelist(double_plist head)
{
      int n = 0;
      int i = 0;
      double_plist new = NULL;

      printf("请输入要插入的数据个数：");
      scanf("%d", &n);

      for (i=0; i<n; i++)
      {
            new = (double_plist)malloc(sizeof(double_list));
            if (NULL == new)
            {
                  perror("malloc");
                  exit(1);
            }
            printf("输入要插入的第%d个数据：", i+1);
            scanf("%d", &(new->data));

            /* 使用前插方法 */
            insert_doublelist_tail(head, new);
            show_doublelist(head);
      }
}
 
2、排序
 
/* 排序 */
void sort_doublelist(double_plist head)
{
      double_plist p = NULL;
      double_plist t = NULL;

      p = head->prev;   /* p指向最后那个结点，从后往前找 */
      while (p != head)
      {
            if (1 == (p->data % 2))    /* 判断是否为奇数 */
            {
                  p = p->prev; /* 如果是奇数，p往前移 */
            }
            else  /* 偶数 */
            {
                  t = p; /* 保存这个结点的数据 */
                  p = p->prev; /* p继续往前移 */
                  delete_doublelist(t);   /* 删除这个结点，但不释放它，还继续保存数据 */
                  insert_doublelist_tail(head, t); /* 将t结点作为新结点插入到head结点后面 */
                  show_doublelist(head);
            }
            
      }
}
 
3、main函数
 
int main(void)
{
      double_plist head = NULL;

      init_doublelist(&head);
      create_doublelist(head);
      sort_doublelist(head);

      return 0;
}
 
4、实验结果
 
 
四、完整代码
 
https://github.com/sanjaywu/DataStructure

声明：以下头指针都是指向链表的第一个结点（有头节点就指向头结点，没有头节点就指向第一个存储数据的结点），并且默认一下头结点的数据域不存储数据信息
 
1、单链表
 
无头结点
 
分析：带有头节点的链表若为空，只需要整条链表只剩一个头节点，这是和不带头节点的链表的一个很大的区别（不带头结点的链表若要为空，整个链表不能存在一个结点），怎样使带头节点的链表只剩一个头节点呢？只需要第一个存储数据的节点不存在即可，即头节点的后继结点不存在即可，所以只需要头节点的next指针域不存在即可（实质上使指向NULL），所以带头点的单链表的判空条件为 head->next=NULL
 
有头节点
 
 
分析：若要不带头结点的链表为空，需要链表中所有结点都不能存在，怎样使所有节点都不存在呢？只需要第一个结点不存在即可，所有只需要头指针head=NULL即可
 
2、双链表
 
带有头节点
 
 判空条件和带头节点的单链表一样
不带头结点
 
 判空条件和单链表一样，分析方法也一样
 3、循环单链表
带头结点
 
 
分析：链表为空头节点仍存在，但是同时要满足循环，所以判空条件为head->next=head;
 
无头结点
 和单链表分析相同直接head=NULL即可
 4、循环双链表
带头节点
 
 
分析：循环双链表的判空条件有很多，如head->next=head或head->next=head->prior或head->prior=head或head->next=head&&head->prior=head
 
5、无头节点
 和前面的单链表分析一样，直接head=NULL;

 
双向循环链表
 
一、相关概念
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。这两者都是顺序表与链表的典型应用。

一、双向循环链表特点
 
双向循环链表的结构是在双向链表的基础上使头节点的前驱指针指向末尾的节点，而使末尾的节点的一个指针指向开始节点，形成一个循环结构。 
  
 双向循环链表在进行节点的删除的时候的操作： 
 
 
双向循环链表在进行节点的插入时的操作： 
 
 
二、双向循环链表的实现
 
AL_Node.h文件
 
#ifndef AL_NODE_INCLUDE
#define AL_NODE_INCLUDE

#include <windows.h>
template<typename T> class AL_ListCircuarDouble;

template<typename T>
class AL_Node
{
    //声明一个朋友类，使这个朋友类可以访问这个类的私有元素
    friend class AL_ListCircuarDouble<T>;
public:
    ~AL_Node();
private:
    AL_Node();
    AL_Node(const T &tTemplate);
    AL_Node(const AL_Node<T>& cAL_Node);
    T m_data;//存储数据
    AL_Node *m_pPre;//记录链表的头结点地址
    AL_Node *m_pNext; //指向下一个节点地址
};

template<typename T>
AL_Node<T>::AL_Node() :m_pPre(NULL), m_pNext(NULL)
{


}

template<typename T>
AL_Node<T>::AL_Node(const T &tTemplate) :m_pPre(NULL), m_pNext(NULL), m_data(tTemplate)
{

}

template<typename T>
AL_Node<T>::~AL_Node()
{
    m_pPre = NULL;
    m_pNext = NULL;
}

#endif // AL_NODE
 
AL_ListCircularDouble.h文件
 
#ifndef AL_LISTCIRCULARDOUBLE_INCLUDE
#define AL_LISTCIRCULARSINGLE_INCLUDE

#include <windows.h>
#include "AL_Node.h"

template<typename T>
class AL_ListCircuarDouble
{
public:
    static const DWORD LISTDOUBLE_POSITION_INVALID = 0xffffffff;
    AL_ListCircuarDouble();
    ~AL_ListCircuarDouble();
    //获取当前链表中节点的个数
    DWORD Length() const;
    //寻找当前值在节点中的位置
    DWORD Find(const T &tTemplate) const;
    //判断当前元素是否存在
    bool IsElement(const T& tTemplate) const;
    //插入元素
    bool Insert(DWORD dwIndex, const T& tTemplate);
    bool InsertBegin(const T& tTemplate);
    bool InsertEnd(const T& tTemplate);
    //移除元素
    bool Remove(const T& tTemplate);
    //判断链表是否为空
    bool IsEmpty() const;
    //获取链表中的元素
    bool Get(T& tTypeOut, DWORD dwIndex) const;
    //修改链表中的元素值
    bool Set(T& tTypeOut, DWORD dwIndex, const T& tTemplate);
    //删除整个表中的节点
    void Clear();
private:
    //根据索引寻找链表中的节点
    AL_Node<T>* GetNodeByIndex(DWORD dwIndex) const;
    DWORD    m_dwSize;//记录当前链表中节点的个数
    AL_Node<T>* m_pHeader;//节点数据结构对象。
};



#endif

template<typename T>
inline AL_ListCircuarDouble<T>::AL_ListCircuarDouble():m_pHeader(NULL),m_dwSize(0x00)
{
    m_pHeader = new AL_Node<T>();
    m_pHeader->m_pPre = m_pHeader;
    m_pHeader->m_pNext = m_pHeader;
}

template<typename T>
inline AL_ListCircuarDouble<T>::~AL_ListCircuarDouble()
{
    Clear();
    if (m_pHeader!=NULL)
    {
        delete m_pHeader;
        m_pHeader = NULL;
    }

}

template<typename T>
inline DWORD AL_ListCircuarDouble<T>::Length() const
{
    return m_dwSize;
}

template<typename T>
inline DWORD AL_ListCircuarDouble<T>::Find(const T & tTemplate) const
{
    if (IsEmpty()==true)
    {
        return LISTDOUBLE_POSITION_INVALID;
    }
    AL_Node<T> *pMvoe = NULL;
    DWORD dwCount = 1;
    pMvoe = m_pHeader->m_pNext;
    while(pMvoe->m_pNext!=NULL)
    {
        if (pMvoe->m_data==tTemplate)
        {
            return dwCount - 1;
        }
        dwCount++;
        pMvoe = pMvoe->m_pNext;
    }

    if (pMvoe->m_data==tTemplate)
    {
        return dwCount - 1;
    }

    return LISTDOUBLE_POSITION_INVALID;
}

template<typename T>
inline bool AL_ListCircuarDouble<T>::IsElement(const T & tTemplate) const
{
    if (Find(tTemplate) == LISTDOUBLE_POSITION_INVALID);
    {
        return false;
    }
    return true;
}

template<typename T>
inline bool AL_ListCircuarDouble<T>::Insert(DWORD dwIndex, const T & tTemplate)
{
    if (dwIndex>Length())
    {
        return false;
    }

    AL_Node<T> *pInsert = new AL_Node<T>();
    pInsert->m_data = tTemplate;
    AL_Node<T> *pPer = NULL;

    if (dwIndex==0x00)
    {
        pPer = m_pHeader;
    }
    else
    {
        pPer = GetNodeByIndex(dwIndex - 1);
    }

    if (pPer==NULL)
    {
        return false;
    }

    if (dwIndex==Length())
    {
        pPer->m_pNext = pInsert;
        pInsert->m_pPre = pPer;
        pInsert->m_pNext = m_pHeader;
        m_pHeader->m_pPre = pInsert;
    }
    else
    {
        AL_Node<T> *IndexNode = pPer->m_pNext;
        if (IndexNode==NULL)
        {
            return false;
        }
        pPer->m_pNext = pInsert;
        pInsert->m_pPre = pPer;
        pInsert->m_pNext = IndexNode;
        IndexNode->m_pPre = pInsert;
    }

    m_dwSize++;
    return true;
}

template<typename T>
inline bool AL_ListCircuarDouble<T>::InsertBegin(const T & tTemplate)
{
    return Insert(0x00, tTemplate);
}

template<typename T>
inline bool AL_ListCircuarDouble<T>::InsertEnd(const T & tTemplate)
{
    return Insert(Length(),tTemplate);
}

template<typename T>
inline bool AL_ListCircuarDouble<T>::Remove(const T & tTemplate)
{
    if (IsEmpty()==true)
    {
        return false;
    }
    DWORD dwPosition = Find(tTemplate);
    if (dwPosition==LISTDOUBLE_POSITION_INVALID)
    {
        return false;
    }
    AL_Node<T> *pDelete =GetNodeByIndex(dwPosition);
    if (pDelete==NULL)
    {
        return false;
    }

    AL_Node<T> *pPer = NULL;
    if (dwPosition==0x00)
    {
        pPer= m_pHeader;
    }
    else
    {
        pPer = pDelete->m_pPre;
    }

    if (pPer==NULL)
    {
        return false;
    }

    pPer->m_pNext = pDelete->m_pNext;
    delete pDelete;
    pDelete = NULL;
    m_dwSize--;
    return true;
}

template<typename T>
inline bool AL_ListCircuarDouble<T>::IsEmpty() const
{
    //判断是否循环指向头结点。
    return (m_pHeader->m_pNext==m_pHeader)?true:false;
}

template<typename T>
inline bool AL_ListCircuarDouble<T>::Get(T & tTypeOut, DWORD dwIndex) const
{
    if (IsEmpty() == true)
    {
        return false;
    }

    if (dwIndex>Length()-1)
    {
        return false;
    }
    AL_Node<T> *pGet = GetNodeByIndex(dwIndex);
    if (pGet==NULL)
    {
        return false;
    }
    tTypeOut = pGet->m_data;
    return true;
}

template<typename T>
inline bool AL_ListCircuarDouble<T>::Set(T & tTypeOut, DWORD dwIndex, const T & tTemplate)
{
    if (IsEmpty()==true)
    {
        return false;
    }

    if (dwIndex>Length()-1)
    {
        return false;
    }
    AL_Node<T> *pSet = GetNodeByIndex(dwIndex);
    if (pSet==NULL)
    {
        return false;
    }
    tTypeOut = pSet->m_data;
    pSet->m_data = tTemplate;
    return true;
}

template<typename T>
inline void AL_ListCircuarDouble<T>::Clear()
{
    if (IsEmpty()==true)
    {
        return;
    }

    AL_Node<T> *pDelete = NULL;
    while (m_pHeader->m_pNext!=m_pHeader)
    {
        pDelete = m_pHeader->m_pNext;
        m_pHeader->m_pNext = pDelete->m_pNext;
        delete pDelete;
        pDelete = NULL;
    }
    m_dwSize = 0x00;
}

template<typename T>
inline AL_Node<T>* AL_ListCircuarDouble<T>::GetNodeByIndex(DWORD dwIndex) const
{
    if (dwIndex>Length()-1)
    {
        return NULL;
    }

    AL_Node<T> * pMove = NULL;
    DWORD dwCount = 1;
    pMove = m_pHeader->m_pNext;
    while (pMove->m_pNext!=m_pHeader)
    {
         if (dwCount-1==dwIndex)
         {
             return pMove;
         }
         dwCount++;
         pMove = pMove->m_pNext;
    }
    return pMove;
}
 
测试代码：
 

void ListCircularDoubleTest()
{
    AL_ListCircuarDouble<DWORD> clistCircuarDouble;
    bool bEmpty = clistCircuarDouble.IsEmpty();
    std::cout << bEmpty << std::endl;

    int arrays[15] = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
    for (int  i = 0; i < 15; i++)
    {
     clistCircuarDouble.Insert(i, arrays[i]);
    }
    bEmpty = clistCircuarDouble.IsEmpty();
    DWORD blength = clistCircuarDouble.Length();
    std::cout << bEmpty << " " << blength << std::endl;

    bEmpty = clistCircuarDouble.Remove(6);
    blength = clistCircuarDouble.Length();
    std::cout << bEmpty << "  " << blength << std::endl;

    DWORD  sget, sset;
    clistCircuarDouble.Set(sset, 5, 123);
    clistCircuarDouble.Get(sget, 5);
    std::cout << sset << " " << sget << std::endl;

    DWORD  sfind = clistCircuarDouble.Find(5);
    DWORD sfind1 = clistCircuarDouble.Find(123);
    std::cout << sfind1 << " " << sfind << std::endl;
}

int main(int argc, char *argv[])
{
    ListCircularDoubleTest();
    getchar();
    return 0;
}
 
运行结果：