在上一节我们讲解了单链表的头插法和尾插法

http://t.csdn.cn/RixAu

但是单链表无法反向检索，对于某些情景可能造成不便，所以我们今天学习双链表

目录

1.双链表的初始化

2.双链表的插入

3.双链表的删除

4.遍历双链表

---

1.双链表的初始化

typedef int ElemType;
typedef struct DLinkList{ElemType data;struct DNode *prior,*next;}DNode,*DLinkList;bool InitDLinkList(DLinkList &L)
{L=(DNode*)malloc(sizeof(DNode));if(L=NULL){return false;}L->prior=NULL;L->next=NULL;return true;}void testDLinkList()
{DLinkList L;InitLinkList(L);}//判断双链表是否为空
bool Empty(DLinkList L)
{if(L->next==NULL)return true;elsereturn false;}

2.双链表的插入

//在p结点之后插入s结点
bool InsertNextNode(DNode *p,DNode *s)
{if(p==NULL || s==NULL)return false;s->next=p->next;//将结点*s插入到结点*p之后if(p->next!=NULL)p->next->prior=s;s->prior=p;p->next=s;return true;
}

3.双链表的删除

bool DeleteNextDNode(DNode *p)
{if(p==NULL)return false;DNode *q=p->next;if(q==NULL)return false;p->next=q->next;if(q->next!=NULL)q->next->prior=p;free(q);return true;}void DestroyList(DLinkList &L)
{
//释放各数据结点while(L->next!=NULL)DeleteNextNode(L);free(L);//释放头结点L=NULL;//头指针指向NULL}

4.遍历双链表

//后向遍历
while(p!=NULL)
{p=p->next;}while(p!=NULL)
{p=p->prior;}
//前向遍历,跳过头结点
while(p->prior!=NULL)
{p=->prior;
}
时间复杂度O(n)