双向链表一

点击打开在线编译器,边学边练

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

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

图:单链表示意图

31.png


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

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

图:双向链表示意图

32.png

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


2. 双向链表的结点设计

对于每一个结点而言,有:

33.png

其中,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;
}

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



本文固定URL:https://www.dotcpp.com/course/98

上一课:单链表二 下一课:双向链表二
第一章 数据结构入门
第二章 链表
第三章 栈
第四章 队列
第五章 从C语言到C++
第六章 串,数组,矩阵,广义表
第七章 树
第八章 图
第九章 算法—查找
第十章 算法—排序
第十一章 算法&竞赛,思维培养
第十二章 后记
Dotcpp在线编译      (登录可减少运行等待时间)