双向链表的基本设计（C语言代码实现）-数据结构与算法教程

1.  双向链表的简介&概念

单链表在很多时候已经可以胜任很多优秀的操作了，但是，单链表任然存在不足，所谓‘单链表’，是指结点中只有一个指向其后继的指针，具有单向性，有时需要搜索大量数据的时候，就必须要多次进行从头开始的遍历，这样的搜索不是很便利。

图：单链表示意图

对此在单链表的基础上，产生了双向链表的概念，即： 在单链表的基础上，对于每一个结点设计一个前驱结点，前驱结点与前一个结点相互连接，构成一个链表。

双向链表可以简称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

图：双向链表示意图

一个完整的双向链表应该是头结点的pre指针指为空，尾结点的next指针指向空，其余结点前后相链。

2. 双向链表的结点设计

对于每一个结点而言，有：

其中，DATA表示数据，其可以是简单的类型（如int,double等等），也可以是复杂的结构体（struct类型）；

pre代表的是前驱指针，它永远指向当前结点的前一个结点，注意，如果当前结点是头结点，则pre指针为空；

next代表的是后继指针，它永远指向当前结点的下一个结点，注意，如果当前结点是尾结点，则next指针为空

其代码设计可以为：

typedef struct line{
    int data;           //data
    struct line *pre;   //pre node
    struct line *next;  //next node
}line,*a;
//分别表示该结点的前驱(pre)，后继(next)，以及当前数据(data)

3. 双链表的创建

对于创建双向链表，我们需要先创建头结点再逐步的进行添加，请注意，双向链表的头结点是有数据元素的，也就是头结点的data域中是存有数据的，这与一般的单链表是不同的。

对于逐步添加数据，我们采取的做法是，开辟一段新的内存空间作为新的结点，为这个结点进行的data进行赋值，然后将已成链表的上一个结点的next指针指向自身，自身的pre指针指向上一个结点。

其代码可以设计为：

//创建双链表
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;
}

初步看起来双向链表似乎比单链表的两种创建方法要复杂，其实将过程逐步拆解为 创建头结点----创建一个新的结点----将头结点和新结点相互链接----再度创建新结点……这样的过程去思考，再反过头多看几遍代码会有助于理解。