1.双链表的初始化
初始化双链表：首先通过malloc函数分配一个头结点空间，通过判断链表L是否为空来确定是否分配成功。将头结点的prior永远指向NULL，头结点的下一个结点暂时没有所以也指向NULL
bool InitDLinkList(DLinkList &L){ L=(DNode *) malloc(sizeof(DNode)); if(L==NULL) return false; L->prior=NULL; L->next=NULL; retrun true; }
1.1 判断双链表是否为空
要想判断双链表是否为空，即判断头结点的next的指针是否为空
bool Empty(DLinkList L){ if(L->next==NULL) return false; else return true; }
2.双链表的插入
实现需求：在p结点之后插入s结点
2.1 p结点不是最后一个结点
网络异常，图片无法展示
|
- 首先会把s结点指向p->next结点
- p的后继结点的前向指针指向s
- s结点的前向指针指向p结点
- p的后向指针指向s结点
网络异常，图片无法展示
|
代码实现：
bool InsertNextDNode(DNode *p, DNode *s){ s->nest=p->next; p->next->prior=s; s->prior=p; p->next=s; }
2.2 p结点是最后一个结点
网络异常，图片无法展示
|
p->next->prior=s改良，判断p结点是否有后续结点，从而判断是不是需要修改p下一个结点的前向指针
if(p==NULL || S==NULL) return false; s->next=p->next; if(p->next!=NULL) p->next->prior=s;
3.双链表的删除
3.1 删除p的后继节点
分析：和插入的思考方式一样，同样我们需要考虑p的后继结点是否为NULL。
- 找到p的后继结点
- 判断p的后继结点是否为NULL，为NULL即p没有后继
- 将p的下一个结点指向q的下一个结点
- 判断q结点是否为最后一个结点
- free(q)
代码实现：
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=q; free(q); return true; }
3.2 销毁链表
实现步骤：
- 循环释放各个数据结点
- 同时释放头结点
- 头指针指向空
void DestoryList(DLinkList &L){ while(L->nex!=NULL) DeleteNextDNode(L); free(L); L=NULL; }
4.双链表的遍历
对结点p做相应的处理，如打印
4.1 后向遍历
while(p!=NULL){ p=p->next; }
4.2 前向遍历
while(p!=NULL){ p=p->prior; }
4.3 前向遍历（跳过头结点）
while(p->prior=NULL){ p=p->prior; }
5.总结
- 修改指针的时候需要注意顺序
- 双链表可以很方便的找到给定结点的前驱节点，对前驱节点执行后插操作，这样就可以实现按位序插入的前插操作。
- 双链表不具备随机存取特性，查找操作只能通过顺序遍历实现
