1. 双向链表的简介&概念文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
单链表在很多时候已经可以胜任很多优秀的操作了，但是，单链表任然存在不足，所谓‘单链表’，是指结点中只有一个指向其后继的指针，具有单向性，有时需要搜索大量数据的时候，就必须要多次进行从头开始的遍历，这样的搜索不是很便利。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
图：单链表示意图文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
对此在单链表的基础上，产生了双向链表的概念，即： 在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
双向链表可以简称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
图：双向链表示意图文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
一个完整的双向链表应该是头结点的pre指针指为空，尾结点的next指针指向空，其余结点前后相链。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
2. 双向链表的结点设计文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
对于每一个结点而言，有：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
其中，DATA表示数据，其可以是简单的类型（如int,double等等），也可以是复杂的结构体（struct类型）；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
pre代表的是前驱指针，它永远指向当前结点的前一个结点，注意，如果当前结点是头结点，则pre指针为空；文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
next代表的是后继指针，它永远指向当前结点的下一个结点，注意，如果当前结点是尾结点，则next指针为空文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
其代码设计可以为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
typedef struct line{ int data; //data struct line *pre; //pre node struct line *next; //next node}line,*a;//分别表示该结点的前驱(pre)，后继(next)，以及当前数据(data) |
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
3. 双链表的创建文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
对于创建双向链表，我们需要先创建头结点再逐步的进行添加，请注意，双向链表的头结点是有数据元素的，也就是头结点的data域中是存有数据的，这与一般的单链表是不同的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
对于逐步添加数据，我们采取的做法是，开辟一段新的内存空间作为新的结点，为这个结点进行的data进行赋值，然后将已成链表的上一个结点的next指针指向自身，自身的pre指针指向上一个结点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
其代码可以设计为：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html
//创建双链表line* initLine(line * head){ int number,pos=1,input_data; //三个变量分别代表结点数量，当前位置，输入的数据 printf("请输入创建结点的大小\n"); scanf("%d",&number); if(number<1){return NULL;} //输入非法直接结束 //////头结点创建/////// head=(line*)malloc(sizeof(line)); head->pre=NULL; head->next=NULL; printf("输入第%d个数据\n",pos++); scanf("%d",&input_data); head->data=input_data; line * list=head; while (pos<=number) { line * body=(line*)malloc(sizeof(line)); body->pre=NULL; body->next=NULL; printf("输入第%d个数据\n",pos++); scanf("%d",&input_data); body->data=input_data; list->next=body; body->pre=list; list=list->next; } return head;} |
初步看起来双向链表似乎比单链表的两种创建方法要复杂，其实将过程逐步拆解为 创建头结点----创建一个新的结点----将头结点和新结点相互链接----再度创建新结点……这样的过程去思考，再反过头多看几遍代码会有助于理解。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/wangluo/25067.html