在使用链表来解决约瑟夫问题的时候，用到了循环链表。循环链表又分为单向循环链表与双向循环链表，约瑟夫问题采用单项循环链表可以得到很好的而解决了，但是单向链表的很大的缺陷仍然存在，那就是在删除的时候需要两个并排指针同步移动。双向链表就可以解决这个问题，因为在双向链表中的每一个结点都有两个指针域来分别指向其前驱和后继。这样子在遍历链表时不用两个指针，直接使用一个就好，当锁定位置后，取出其前驱然后再保存当前位置最后做删除操作就好了。
结点类型不变，存在两个指针：
[cpp]
#pragma once
#include<iostream>
using namespace std;
template<class T>
class LinkNode //节点类
{
public: //全为公共的方便操作
T data; //模板类型的一个数据
LinkNode<T> *next; //该结点的一个指针，用于指向后继
LinkNode<T> *prior;//用于指向前驱
public:
LinkNode(LinkNode<T> *ptr = NULL)//只初始化指针的构造函数,并使指针域为空
{ next = ptr; prior = ptr; }
LinkNode(const T& item,LinkNode<T> *ptr = NULL)//数据与指针一同初始化的构造函数，依旧指针域默认参数为空
{ data = item; next = ptr; prior = ptr; }
~LinkNode(){}
};
循环链表的关键是环的形成，而最好的方式就是在创建链表的时候就形成环状，笔者采用的是带有头结点的链表，所以在构造函数中就可以创建一个环出来：
[cpp]
template<class T>
List<T>::List()
{
first = new LinkNode<T>;//构造函数中开辟头结点
first->prior = first;//头结点的前后指针均指向其本身 逻辑循环
first->next = first;
}
在每一次的插入和删除之后需要把首尾连接起来，其余操作可看做是普通链表。
#pragma once
#include"LinkNode.h"
#include<iostream>
using namespace std;
template<class T>//继承的过程中，加上此句派生类依然为类模板
class List
{
protected:
LinkNode<T>* first;//封装
public:
List();
List(List<T>& L);
~List();
void makeEmpty();//依次销毁每个结点的空间
int Length() const;//搜索当前表节点数
LinkNode<T>* getHead() const;//返回头指针
LinkNode<T>* Search(T x) const;//搜索并返回指针
LinkNode<T>* Locate(int i) const;//定位并返回指针
bool GetData(int i,T& x) const;//返回第i个结点的元素值以引用的形式
bool SetData(int i,T& x);//修改第i个结点的元素值
bool Insert(int i,T& x);//在第i个节点后面插入新节点元素值
LinkNode<T>* Remove(int i,T& x);//删除第i个结点
bool isEmpty() const;//判表空
void Sort(); //排序
void input(T endTag);//建立表并输入
void output();//输出表
void operator = (List<T>& L);//复制重载
};
template<class T>
List<T>::List()
{
first = new LinkNode<T>;//构造函数中开辟头结点
first->prior = first;//头结点的前后指针均指向其本身 逻辑循环
first->next = first;
}
template<class T>
List<T>::List(List<T>& L)
{
LinkNode<T> *L_HEAD = L.getHead();
LinkNode<T> *srcptr = L_HEAD->next; //获取头指针 用于遍历
LinkNode<T> *destptr = first = new LinkNode<T>;//建立头结点 初始化
LinkNode<T> *newNode;
T value;
while(srcptr != L_HEAD)//直到循环到首指针w为结束
{
value = srcptr->data;
newNode = new LinkNode<T>(value);
newNode->prior = destptr;//往新链表的后面插入
destptr->next = newNode;
srcptr = srcptr->next;//后移
destptr = destptr->next;
}
destptr->next = first;//首尾相接 建立循环
first->prior = destptr;
}
template<class T>
List<T>::~List()
{
makeEmpty();
}
template<class T>
void List<T>::makeEmpty() //全部销毁指针资源
{
LinkNode<T> *current = first->next;
LinkNode<T> *del;
while(current != first)
{
del = current;
current = current->next;
delete del;
}
}
template<class T>
int List<T>::Length() const
{
int count = 0;
LinkNode<T> *current = first;//头指针副本用于遍历
while(current->next != first)//与单链表的遍历控制条件相同，当前结点后后继是否为空
{
current = current->next;
count++ ;
}
return count;
}
template<class T>
LinkNode<T>* List<T>::getHead() const
{
return first;
}
template<class T>
LinkNode<T>* List<T>::Search(T x) const
{
LinkNode<T> *current = first->next;
while(current != NULL)//此时的控制条件为某个结点的next知否为空
{
if(current->data == x)
