双链表的理解
·一般学习双链表都是在学习单链表之后（本文需要一定单链表基础），但单链表有一个缺点，就是无法访问前驱节点，需要查找某个已知节点的前一个节点时能再次从头遍历，就比较麻烦，那么，在节点中再加一个指针指向前驱节点的链表就称为双链表，再综合单链表的节点写法，那么双链表的写法就很简单了。数据节点包含一个数据域，两个指针（一个指向前驱节点，一个指向后驱节点）。大致图解如下：
而因为多了一个前指针，所以数据节点的插入，删除等操作相对于单链表来说更难一点，但理解透了其实差不多，这里都不给出具体图解了，我们直接进入正文。
双链表数据节点和头结点的定义
双链表的数据节点定义只需要在定义单链表数据节点的基础上加一个前驱指针，这里我们还是定义一个头结点结构体来保存双链表的信息，另一个结构体充当数据节点
typedef struct header//头结点保存双链表信息 { int length;//记录双链表当前大小 struct node* next;//指向第一个数据节点 }head; typedef struct node//数据节点 { int val;//数据域 struct node* pre;//指向前一个数据节点（与单链表最大的区别） struct node* next;//指向下一个数据节点 }node;
如上，一个最基础的双链表头结点和数据节点就定义好了，下面就可以对双链表进行操作啦。
双链表的创建
和单链表的创建一样，双链表的创建同样只需要创建好头结点就可以了，链表每储存一个元素就分配一个内存单元构建数据节点 ，所以双链表的创建也相对简单，具体代码如下：
head* listcreat()//创建双链表 { head* p; p=(head*)malloc(sizeof(head));//给头结点分配空间 p->length=0;//初始化双链表 p->next=NULL;//双链表的最后指向NULL即可 return p;//返回创建好的头结点地址 }
双链表数据节点的插入
学习双链表在我看来比较难的便是双链表数据节点的插入，主要是不好想， 所以建议大家可以在本子上画一下，具体代码如下（本文都是用封装函数的形式写的，文章末尾有完整代码）：
void listinsert(head* p,int pos,int x)//头结点地址，要插入的位置，要插入的元素 { node* temp;//temp即我们要插入的数据节点 temp=(node*)malloc(sizeof(node));//为其分配空间 temp->val=x;//填充数据域 if(p==NULL||pos<0||pos>p->length)//判断插入失败的情况 { printf("listinsert():error\n"); return; } if(p->length==0)//判断双链表为空的情况 { p->next=temp;//头结点的的next指针指向temp temp->next=NULL;//temp的next指针指向NULL（保证最后一个数据节点的next指向空） temp->pre=NULL;temp的pre指针指向NULL（保证第一个数据节点的pre指向空） p->length++;//不要忘记记录双链表的大小 return;//完成插入 } node* pcur=p->next;//定义一个指向第一个数据节点的指针； if(pos==0)//插在头结点和第一个数据节点之间（即头插）的情况 { p->next=temp;//头结点的next指针指向temp temp->pre=NULL;//temp此时为第一个数据节点所以前指针pre指向空 temp->next=pcur;//pcur为上文记录的插入前的第一个数据节点 pcur->pre=temp;//作为第二个数据节点的前指针pre指向第一个数据节点temp p->length++; return; } for(int i=1;i<pos;i++) { pcur=pcur->next; } //此时pcur指向要插入的位置的前一个数据节点，例如将2插入到1，3中间，那pcur就指向1. if(pos==p->length)//尾插的情况 { pcur->next=temp; temp->next=NULL; temp->pre=pcur; } else//既不是头插，也不是尾插（可能比较难理解，建议画个草图） { temp->next=pcur->next; pcur->next->pre=temp; temp->pre=pcur; pcur->next=temp; } p->length++; return; }
双链表数据节点的删除
双链表的数据节点插入弄明白之后数据节点的删除就简单的多啦，直接附上代码：
void listdelete(head* p,int x)//头结点地址，要删除的元素 { node* temp=p->next;//定义一个指向第一个数据节点的指针 while(temp->val!=x&&temp!=NULL)//遍历链表寻找要删除的数据节点 { temp=temp->next; } if(temp->val!=x)//链表中没有找到要删除的数据节点 { printf("listdelete():error"); return;//退出程序 } node* pRe=temp->pre;//指向要删除的元素的前一个数据节点 node* pnext=temp->next;//指向要删除的元素的后一个节点 if(pRe==NULL)//即要删除的数据节点是第一个数据节点的情况 { p->next=pnext;//头结点的next指针直接指向第二个数据节点 pnext->pre=NULL;//第二个数据节点变成第一个数据节点 } else if(pnext==NULL)//要删除的数据节点是最后一个的情况 { pRe->next=NULL; } else//要删除的数据节点不是第一个也不是最后一个 { pRe->next=pnext; pnext->pre=pRe; } free(temp); p->length--; return; }
双链表的数据节点插入我们也完成了，为了方便使用，我们也可以写一个遍历打印（即输出）双链表的函数，具体代码如下：
void print(head* p) { if(p==NULL) { printf("listprint():error\n"); return; } node* temp=p->next; while(temp!=NULL) { printf("%d ",temp->val); temp=temp->next; } printf("\n"); return; }
好了，双链表的各个操作差不多就弄明白了，完整的代码如下：
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct header { int length; struct node* next; }head; typedef struct node { int val; struct node* pre; struct node* next; }node; head* listcreat()//创建双链表 { head* p; p=(head*)malloc(sizeof(head)); p->length=0; p->next=NULL; return p; } void listinsert(head* p,int pos,int x)//单链表数据节点的插入 { node* temp; temp=(node*)malloc(sizeof(node)); node* pcur=p->next;//定义一个指向第一个数据节点的指针； temp->val=x; if(p==NULL||pos<0||pos>p->length) { printf("listinsert():error\n"); return; } if(p->length==0) { p->next=temp; temp->next=NULL; temp->pre=NULL; p->length++; return; } if(pos==0) { p->next=temp; temp->pre=NULL; temp->next=pcur; pcur->pre=temp; p->length++; return; } for(int i=1;i<pos;i++)//使pcur指向要插入的位置 { pcur=pcur->next; } if(pos==p->length) { pcur->next=temp; temp->next=NULL; temp->pre=pcur; } else { temp->next=pcur->next; pcur->next->pre=temp; temp->pre=pcur; pcur->next=temp; } p->length++; return; } void listdelete(head* p,int x) { node* temp=p->next; while(temp->val!=x&&temp!=NULL) { temp=temp->next; } if(temp->val!=x) { printf("listdelete():error"); return; } node* pRe=temp->pre; node* pnext=temp->next; if(pRe==NULL) { p->next=pnext; pnext->pre=NULL; } else if(pnext==NULL) { pRe->next=NULL; } else { pRe->next=pnext; pnext->pre=pRe; } free(temp); p->length--; return; } void print(head* p) { if(p==NULL) { printf("listprint():error\n"); return; } node* temp=p->next; while(temp!=NULL) { printf("%d ",temp->val); temp=temp->next; } printf("\n"); return; } int main() { int number; head* p=listcreat(); printf("请输入双链表数据节点初始个数\n"); scanf("%d",&number); printf("请依次输入初始数据\n"); int a[number]; for(int i=0;i<number;i++) { scanf("%d",&a[i]); } for(int i=number-1;i>=0;i--) { listinsert(p,0,a[i]); } printf("输出初始链表\n"); print(p); printf("请输入插入的位置和元素\n"); int m,n; scanf("%d%d",&m,&n); listinsert(p,m,n); printf("输出插入后的链表\n"); print(p); printf("请输入要删除的元素\n"); int del; scanf("%d",&del); listdelete(p,del); printf("输出删除后的元素\n"); print(p); return 0; }
随便写点代码运行一下就是下面这个效果啦 （因为双链表和单链表的差别其实不大，而我也写过一篇单链表的博客，所以感觉没什么写的了，有什么遗漏的希望大家见谅）
请输入双链表数据节点初始个数
6
请依次输入初始数据
1 2 3 4 5 6
输出初始链表
1 2 3 4 5 6
请输入插入的位置和元素
6 7
输出插入后的链表
1 2 3 4 5 6 7
请输入要删除的元素
7
输出删除后的元素
1 2 3 4 5 6
