前面总结了单链表的定义的基础上，现在开始着手实践实践双向链表。结构换个角度而言，双向链表是单向链表的扩展，如果从数据结构代码的定义上来看，双向链表需要维护三个数据内容：数据(data)、前指针(prev)和后指针(next)。与单向链表结构相比较，在程序代码中需要多维护一个prev指针域，双向链表如下图所示：
链表的插入与删除示意图：
双向链表带来的好处在于：
1.对链表数据的遍历操作不仅仅能向后遍历(如单链表），而且还能够向前遍历寻找元素，对链表数据的操作更加灵活。
2.可以直接删除某一个数据元素，我认为这是比较重要的一方面，因为对单链表而言，如果要删除某一个数据元素，需要遍历至此元素之前的一个结点才能删除，而双向链表可以遍历到某一元素，然后可以直接对它进行删除操作。
源代码
#include <stdio.h> #include <malloc.h> #include <stdlib.h> typedef struct Node{ int data; struct Node* pNext; struct Node* prior; }NODE,*PNODE; PNODE create_list(void); void traverse_list(PNODE pHead); int length_list(PNODE pHead); void sort_list(PNODE pHead); void insert_list(PNODE pHead,int pos,int val); void delete_list(PNODE pHead,int pos); int main(int argc, char const *argv[]) { PNODE pHead=create_list(); traverse_list(pHead); insert_list(pHead,2,10); traverse_list(pHead); delete_list(pHead,2); traverse_list(pHead); sort_list(pHead); traverse_list(pHead); return 0; } PNODE create_list(void) { int len,i,val; PNODE pHead = (PNODE)malloc(sizeof(NODE)); if(NULL==pHead) { printf("内存分配失败，程序终止!\n"); exit(-1); } PNODE pTail=pHead; pTail->pNext = NULL; pTail->prior = NULL; printf("请输入您要创建链表的长度：\n"); scanf("%d",&len); for(i=0;i<len;i++) { printf("请输入第%d个节点的值：",i+1); scanf("%d",&val); PNODE pNew=(PNODE)malloc(sizeof(NODE)); if(NULL == pNew) { printf("内存分配失败!"); exit(-1); } pNew->data=val; pTail->pNext=pNew; pTail=pNew->prior; pNew->pNext=NULL; pTail=pNew; } return pHead; } void traverse_list(PNODE pHead) { PNODE p=pHead->pNext; while(p) { printf("%d ",p->data); p=p->pNext; } printf("\n"); } int length_list(PNODE pHead) { PNODE p=pHead->pNext; int len=0; while(p){ len++; p = p->pNext; } return len; } void sort_list(PNODE pHead) { int len,i,j,t; PNODE p,q; len=length_list(pHead); for(i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext) { for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext) { if(p->data > q->data) { t=p->data; p->data=q->data; q->data=t; } } } } //pos从1开始 void insert_list(PNODE pHead,int pos,int val) { int i=0; PNODE p=pHead; PNODE pNew=(PNODE)malloc(sizeof(NODE)); if(pNew==NULL) { printf("内存分配失败\n"); exit(-1); } //找到插入位置的前一个位置 while(p!=NULL && i<pos-1) { p=p->pNext; ++i; } pNew->data=val; pNew->pNext=p->pNext; pNew->prior=p; p->pNext->prior=pNew; p->pNext=pNew; } void delete_list(PNODE pHead,int pos){ int i=0; PNODE p=pHead->pNext; while(p!=NULL && i<pos-2){ p=p->pNext; ++i; } PNODE pNew=p->pNext; pNew->prior->pNext=pNew->pNext; pNew->prior=NULL; pNew->pNext->prior=pNew->prior; pNew->pNext=NULL; pNew=NULL; } 运行结果为：
可以根据输入节点个数进行删除，插入，排序等功能。
