双向链表的数据结构图解VS C语言代码实现

网络运维 2023-07-10 法医 手机阅读

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

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

图：单链表示意图

双向链表的数据结构图解VS C语言代码实现

 

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

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

图：双向链表示意图

双向链表的数据结构图解VS C语言代码实现

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

 

2. 双向链表的结点设计

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

双向链表的数据结构图解VS C语言代码实现

其中，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 (numberpre=NULL;      head->next=NULL;      printf ( "输入第%d个数据n" ,pos++);      scanf ( "%d" ,&input_data);      head->data=input_data;        line * list=head;      while (pospre=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; }

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