双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
线性表的双向链表存储结构：
typedef struct DuLNode{ElemType data;struct DuLNode *prior,*next;}DuLNode,*DulinkList;带头结点的双向循环链表的基本操作：
void InitList(DulinkList L){ L=(DulinkList)malloc(sizeof(DuLNode));if(L)L->next=L->prior=L;elseexit(OVERFLOW);}销毁双向循环链表L：
void DestroyList(DulinkList L){DulinkList q,p=L->next; while(p!=L) {q=p->next;free(p);p=q;}free(L);L=NULL;}重置链表为空表：
void ClearList(DulinkList L) { DulinkList q,p=L->next; while(p!=L) {q=p->next;free(p);p=q;}L->next=L->prior=L; }验证是否为空表：
Status ListEmpty(DulinkList L){ int i=0;DulinkList p=L->next; while(p!=L) {i++;p=p->next;}return i;}赋值：
Status GetElem(DulinkList L,int i,ElemType *e){ int j=1; DulinkList p=L->next; while(p!=L&&j<i){p=p->next;j++;}if(p==L||j>i) return ERROR;*e=p->data; return OK;}查找元素：
int LocateElem(DulinkList L,ElemType e,Status(*compare)(ElemType,ElemType)){ int i=0;DulinkList p=L->next; while(p!=L){i++;if(compare(p->data,e)) return i;p=p->next;}return 0;}查找元素前驱：
Status PriorElem(DulinkList L,ElemType cur_e,ElemType *pre_e){ DulinkList p=L->next->next; while(p!=L) {if(p->data==cur_e){*pre_e=p->prior->data;return TRUE;}p=p->next;}return FALSE;}查找元素后继：
Status NextElem(DulinkList L,ElemType cur_e,ElemType *next_e){ DulinkList p=L->next->next; while(p!=L) {if(p->prior->data==cur_e){*next_e=p->data;return TRUE;}p=p->next;}return FALSE;}查找元素地址：
DulinkList GetElemP(DulinkList L,int i) { int j;DulinkList p=L; if(i<0||i>ListLength(L)) return NULL;for(j=1;j<=i;j++)p=p->next;return p;}元素的插入：
Status ListInsert(DulinkList L,int i,ElemType e){ DulinkList p,s;if(i<1||i>ListLength(L)+1) return ERROR;p=GetElemP(L,i-1); if(!p) return ERROR;s=(DulinkList)malloc(sizeof(DuLNode));if(!s)return OVERFLOW;s->data=e;s->prior=p; s->next=p->next;p->next->prior=s;p->next=s;return OK;}元素的删除：
Status ListDelete(DulinkList L,int i,ElemType *e){ DulinkList p;if(i<1) return ERROR;p=GetElemP(L,i); if(!p) return ERROR;*e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);return OK;}正序查找：
void ListTraverse(DulinkList L,void(*visit)(ElemType)){ DulinkList p=L->next; while(p!=L){visit(p->data);p=p->next;}printf("n");}逆序查找：
void ListTraverseBack(DulinkList L,void(*visit)(ElemType)){ DulinkList p=L->prior; while(p!=L){visit(p->data);p=p->prior;}printf("n");}#pragma once#include <assert.h>template<class T>class linkedList{private:class Node{public:T data; //数据域,不要求泛型T的实例类有无参构造函数Node* prior; //指向前一个结点Node* next; //指向下一个结点Node(const T& element,Node*& pri,Node*& nt):data(element),next(nt),prior(pri){}Node():data(data){}//泛型T的实例类的复制构造函数将被调用.在Vc2010测试可行};Node* head; //指向第一个结点public://初始化：构造一个空结点，搭建空链linkedList():head(new Node()){head->prior=head->next=head;}//获取元素总数int elementToatal()const;//判断是否为空链bool isEmpty()const{return head==head->next?true:false;}//将元素添加至最后，注意node的指针设置void addToLast(const T& element){Node* ne=new Node(element,head->prior,head);head->prior=head->prior->next=ne;}//获取最后一个元素T getLastElement()const{assert(!isEmpty());return head->prior->data;}//删除最后一个元素，注意node的指针设置void delLastElement(){assert(!isEmpty());Node* p=head->prior->prior;delete head->prior;head->prior=p;p->next=head;}//修改最后一个元素void alterLastEmlent(const T& newElement){assert(!isEmpty());head->prior->data=newElement;}//插入元素void insertElement(const T& element,int position);//获取元素T getElement(int index)const;//删除元素T delElement(int index);//修改元素void alterElement(const T & Newelement,int index);//查找元素int findElement(const T& element) const;//正序遍历void Traverse(void (*visit)(T&element));//逆序遍历void TraverseBack(void (*visit)(T&element));//重载函数T& operator (int index);//清空链表void clearAllElement();//销毁链表~linkedList();};template<class T>int linkedList<T>::elementToatal()const{int Total=0;for(Node* p=head->next;p!=head;p=p->next) ++Total;return Total;}template<class T>void linkedList<T>::insertElement(const T& element,int position){assert(position>0 && position<=elementToatal()+1);Node* p=head;while(position){p=p->next;position--;}//此时p指向要插入的结点Node* pNew=new Node(element,p->prior,p);p->prior=p->prior->next=pNew;}template<class T>T linkedList<T>::getElement(int index)const{assert(index>0 && index<=elementToatal() && !isEmpty());//位置索引是否合法,链表是否空Node* p=head->next;while(--index) p=p->next;return p->data;}template<class T>T linkedList<T>::delElement(int index){assert(index>0 && index<=elementToatal() && !isEmpty());//位置索引是否合法,链表是否空Node* del=head->next;while(--index) del=del->next;//此时p指向要删除元素del->prior->next=del->next;del->next->prior=del->prior;T delData=del->data;delete del;return delData;}template<class T>void linkedList<T>::alterElement(const T & Newelement,int index){assert(index>0 && index<=elementToatal() && !isEmpty());//位置索引是否合法,链表是否空Node* p=head->next;while(--index) p=p->next;p->data=Newelement;}template<class T>int linkedList<T>::findElement(const T& element) const{Node* p=head->next;int i=0;while(p!=head){i++;if(p->data==element) return i;p=p->next;}return 0;}template<class T>void linkedList<T>::Traverse(void (*visit)(T&element)){Node* p=head->next;while(p!=head){visit(p->data);//注意此时外部visit函数有权限修改linkedList<T>的私有数据p=p->next;}}template<class T>void linkedList<T>::TraverseBack(void (*visit)(T&element)){Node* p=head->prior;while(p!=head){visit(p->data);//注意此时外部visit函数有权限修改linkedList<T>的私有数据p=p->prior;}}template<class T>T& linkedList<T>::operator (int index){assert(index>0 && index<=elementToatal() && !isEmpty());//函数使用前提条件Node* p=head->next;while(--index) p=p->next;return p->data;}template<class T>void linkedList<T>::clearAllElement(){Node* p=head->next,*pTemp=0;while(p!=head){pTemp=p->next;delete p;p=pTemp;}head->prior=head->next=head;//收尾工作}template<class T>linkedList<T>::~linkedList(){if(head)//防止用户显式析构后，对象又刚好超出作用域再调用该函数{clearAllElement();delete head;head=0;}}循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。
温馨提示：