双向链表(双向循环链表)的建立及C语言实现

曾经学习过的链表都仅有一个指向直接后继的指针；其中 链表 也只能单向地从首节点依次访问至末尾节点；这种特殊的链接存储结构统称为 “单向链接列表”或 “单链式结构”。

当算法需要频繁查找某个结点的直接前驱节点时，在单链表中通常采取完整扫描整个链表结构的方法来实现这一需求。这种方法虽然能够解决问题但会导致算法的时间复杂度显著提升从而影响整体运行效率。

采用迅速且便捷的方法来解决此类问题。基于单向链表，在每个节点上附加一个指针变量用于指向其直接前驱元素。这种数据结构通常被称为“ 双向链表 ”或简称为“双链表”。

双链表中的结点

在双向链表中每个节点都包含两个指针字段分别指向其直接前驱和直接后续这些字段使得数据元素之间不仅存在单向的关系还具有相互连接的能力这种数据结构特别适合那些需要频繁修改数据顺序以及实现复杂的逻辑操作的应用场景

结点的具体构成：

>     [纯文本](http://data.biancheng.net/view/8.html# "纯文本")[复制](http://data.biancheng.net/view/8.html# "复制")

使用关键字typedef定义了一个名为struct line的结构体类型。

变量prior为一个指针变量，其类型为struct line指针类型。

成员data为整型数据类型。

变量next为一个指针变量，指向另一个struct类型的实例。

该结构体包含成员data以及前驱与后续节点的关系。

创建双向链表并初始化

在创建双向链表的过程中，在每个节点上首先初始化数据域和两个指针域，并为该节点设置直接前驱节点的指针的同时，并为该节点设置直接后继节点的指针。

例如，创建一个双向链表line（1，2，3）：

实现代码：

1. 函数 initLine 用于初始化链表。
2. 创建并分配内存给变量 head，并将其转换为线型指针。
3. 设置 head 的前驱域和后继域均为 NULL 值。
4. 将数据字段赋值为整数值 1。
5. 初始化变量 list 为 head 的引用。
6. 在循环体中运行两次：
   a) 动态内存分配存储新的线型对象。
   b) 设置该对象的前驱域和后继域均为 NULL 值。
   c) 将新对象附加到当前列表尾部：
   i) 当前列 node 的下一个域设置为新对象。
   ii) 新对象的前驱域设置为当前列 node.
   iii) 更新 current node 至新的下一个 node.

双向链表中插入结点

比如在（1，2，3）中插入一个结点 4，变成（1，4，2，3）。

实现效果图：

当在双向链表中进行数据插入操作时，在访问相邻节点之前，请先完成图3中标注步骤1的两个步骤；接着应依次执行标注步骤2中的两个动作。相反地，在优先执行标注步骤2的情况下，则会导致无法仅凭头指针访问该节点，并需增设临时引用变量来指向它。

实现代码：

 line * insertLine(line * head,int data,int add){

    
     //新建数据域为data的结点
    
     line * temp=(line*)malloc(sizeof(line));
    
     temp->data=data;
    
     temp->prior=NULL;
    
     temp->next=NULL;
    
     //插入到链表头，要特殊考虑
    
     if (add==1) {
    
     temp->next=head;
    
     head->prior=temp;
    
     head=temp;
    
     }else{
    
     line * body=head;
    
     //找到要插入位置的前一个结点
    
     for (int i=1; i<add-1; i++) {
    
         body=body->next;
    
     }
    
     //判断条件为真，说明插入位置为链表尾
    
     if (body->next==NULL) {
    
         body->next=temp;
    
         temp->prior=body;
    
     }else{
    
         body->next->prior=temp;
    
         temp->next=body->next;
    
         body->next=temp;
    
         temp->prior=body;
    
     }
    
     }
    
     return head;
    
 }

双向链表中删除节点

在双链表中删除一个结点时（即对该节点进行删除操作），系统会直接访问该节点并获取其前后驱节点地址，并根据其前驱和后继的关系进行相应的链接操作以完成整个删除过程

例如，在（1，4，2，3）中删除结点 2：

 //删除结点的函数，data为要删除结点的数据域的值

    
 line * delLine(line * head,int data){
    
     line * temp=head;
    
     //遍历链表
    
     while (temp) {
    
     //判断当前结点中数据域和data是否相等，若相等，摘除该结点
    
     if (temp->data==data) {
    
         temp->prior->next=temp->next;
    
         temp->next->prior=temp->prior;
    
         free(temp);
    
         return head;
    
     }
    
     temp=temp->next;
    
     }
    
     printf("链表中无该数据元素");
    
     return head;

双向链表中的查找和更改操作

在查找操作上双向链表与单链表具有相同的实现方法；其遍历过程始于链表中的头节点或首元节点；此处省略具体细节。

基于查找过程进行的操作是修改链表中某结点的数据域。在遍历过程中找到存储有该数据元素的结点后，可以直接修改该节点的数据字段。

总结

在数据结构方面，双向链表与单链表的主要区别在于其增加了直接前驱节点的引用。尽管两者在其他基本组成元素上完全相同。当一个问题需要大量访问当前节点的前驱节点时，则建议选择采用双向链表的数据结构作为最优选择。

双向链表和循环链表的结合体

约瑟夫环问题也可尝试以下玩法：当顺时针依次报数后有人退出后，则应从退出者之下一个正方向的位置启动反向报数（即逆时针），继续依次报数直至有人退出；接着又应从最新退出者之下一个反方向的位置启动正向报数（即顺时针）。如此循环往复直至最终只剩下一个人为止。

按照以下顺序进行出列：
首先顺时针方向转动，在第4个位置处数2人后，则第4人退出。
接着在逆时针方向寻找下一位参与者，在第3个位置处数2人后，则第3人退出。
随后转向顺时针方向，在第5个位置处数2人后，则第5人退出。
最后仅剩一人未参与此轮游戏，则该参与者自动退出游戏流程。

针对新型的约瑟夫环问题，必须采用循环链表与双向链表的综合运用，并构建为一个双向循环链表。