双向链表

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

链表的操作线性表的双向链表存储结构：

typedef struct DuLNode{ElemType data;struct DuLNode *prior,*next;}DuLNode,*DuLinkList;带头结点的双向循环链表的基本操作：

void InitList(DuLinkList L){ /* 产生空的双向循环链表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; /* p指向第一个结点 */while(p!=L) /* p没到表头 */{q=p->next;free(p);p=q;}free(*L);*L=NULL;}重置链表为空表：

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; /*头结点的两个指针域均指向自身 */}验证是否为空表1：

Status ListEmpty(DuLinkList L){ /* 初始条件：线性表L已存在if(L->next==L&&L->prior==L)return TRUE;elsereturn FALSE;}元素的操作计算表内元素个数

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

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

int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType)){ /* 初始条件：L已存在，compare()是数据元素判定函数 *//* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 *//* 若这样的数据元素不存在，则返回值为0 */int i=0;DuLinkList p=L->next; /* p指向第1个元素 */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){ /* 操作结果：若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 TRUE;}p=p->next;}return FALSE;}查找元素后继：

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 TRUE;}p=p->next;}return FALSE;}查找元素地址：

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

Status ListInsert(DuLinkList L,int i,ElemType e){ /* 在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1 *//* 改进算法2.18，否则无法在第表长+1个结点之前插入元素 */DuLinkList p,s;if(iListLength(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)return OVERFLOW;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(idata;p->prior->next=p->next;p->next->prior=p->prior;free(p);return OK;}正序查找1：

void ListTraverse(DuLinkList L,void(*visit)(ElemType)){ /* 由双链循环线性表L的头结点出发，正序对每个数据元素调用函数visit() */DuLinkList p=L->next; /* p指向头结点 */while(p!=L){visit(p->data);p=p->next;}printf("\n");}void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))逆序查找：

{ /* 由双链循环线性表L的头结点出发，逆序对每个数据元素调用函数visit()。另加 */DuLinkList p=L->prior; /* p指向尾结点 */while(p!=L){visit(p->data);p=p->prior;}printf("\n");}双向链表模板/******************************************************文件名：LinkedList.h*功能：实现双向链表的基本功能*注意：为了使最终程序执行得更快，仅在Debug模式下检测操作合法性。*另外不对内存分配失败作处理,因为一般情况下应用程序有近2GB真正可用的空间*********************************************************/#pragma once#include templateclass 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();};/****************************************返回元素总数****************************************/templateint LinkedList::elementToatal()const{int Total=0;for(Node* p=head->next;p!=head;p=p->next) ++Total;return Total;}/***********************************************在position指定的位置插入元素。原来position及后面的元*素后移***********************************************/templatevoid LinkedList::insertElement(const T& element,int position){assert(position>0 && positionnext;position--;}//此时p指向要插入的结点Node* pNew=new Node(element,p->prior,p);p->prior=p->prior->next=pNew;}/****************************************返回找到的元素的副本***************************************/templateT LinkedList::getElement(int index)const{assert(index>0 && indexnext;while(--index) p=p->next;return p->data;}/***********************************删除指定元素，并返回它**********************************/templateT LinkedList::delElement(int index){assert(index>0 && indexnext;while(--index) del=del->next;//此时p指向要删除元素del->prior->next=del->next;del->next->prior=del->prior;T delData=del->data;delete del;return delData;}/*****************************************用Newelement代替索引为index的元素*****************************************/templatevoid LinkedList::alterElement(const T & Newelement,int index){assert(index>0 && indexnext;while(--index) p=p->next;p->data=Newelement;}/*********************************找到返回元素的索引，否则返回0********************************/templateint LinkedList::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;}/****************************************正向遍历，以链表中每个元素作为参数调用visit函数*****************************************/templatevoid LinkedList::Traverse(void (*visit)(T&element)){Node* p=head->next;while(p!=head){visit(p->data);//注意此时外部visit函数有权限修改LinkedList的私有数据p=p->next;}}/**************************************************反向遍历，以链表中每个元素作为参数调用visit函数*************************************************/templatevoid LinkedList::TraverseBack(void (*visit)(T&element)){Node* p=head->prior;while(p!=head){visit(p->data);//注意此时外部visit函数有权限修改LinkedList的私有数据p=p->prior;}}/***************************************************返回链表的元素引用，并可读写.实际上链表没有[]意义上的所有功能*因此[]函数是有限制的.重载它是为了客户端代码简洁，因为从链表读写*数据是最常用的***************************************************/templateT& LinkedList::operator [](int index){assert(index>0 && indexnext;while(--index) p=p->next;return p->data;}/****************************清空链表***************************/templatevoid LinkedList::clearAllElement(){Node* p=head->next,*pTemp=0;while(p!=head){pTemp=p->next;delete p;p=pTemp;}head->prior=head->next=head;//收尾工作}/*******************************析构函数，若内存足够没必要调用该函数*******************************/templateLinkedList::~LinkedList(){if(head)//防止用户显式析构后，对象又刚好超出作用域再调用该函数{clearAllElement();delete head;head=0;}}循环链表循环链表是一种链式存储结构，它的最后一个结点指向头结点，形成一个环。因此，从循环链表中的任何一个结点出发都能找到任何其他结点。循环链表的操作和单链表的操作基本一致，差别仅仅在于算法中的循环条件有所不同。1

本词条内容贡献者为:

何星 - 副教授 - 上海交通大学