DataStructure

【Data Structure】链表 - 双向链表(Doubly Linked List)

Posted by 西维蜀黍 on 2019-05-16, Last Modified on 2023-03-23

双向链表（Doubly Linked List）

从名字上理解双向链表（Doubly Linked List），即链表是 “双向” 的，如下图所示：

双向，指的是各节点之间的逻辑关系是双向的，但通常头指针只设置一个，除非实际情况需要。

双向链表中各节点包含以下 3 部分信息（如下图所示）：

  • 指针域：用于指向当前节点的直接前驱节点；
  • 数据域：用于存储数据元素。
  • 指针域：用于指向当前节点的直接后继节点；

因此，双链表的节点结构用 C 语言实现为：

typedef struct line{
    struct line * prior; //指向直接前趋
    int data;
    struct line * next; //指向直接后继
}line;

双向链表的创建

同单链表相比，双链表仅是各节点多了一个用于指向直接前驱的指针域。因此，我们可以在单链表的基础轻松实现对双链表的创建。

需要注意的是，与单链表不同，双链表创建过程中，每创建一个新节点，都要与其前驱节点建立两次联系，分别是：

  • 将新节点的 prior 指针指向直接前驱节点；
  • 将直接前驱节点的 next 指针指向新节点；

这里给出创建双向链表的 C 语言实现代码：

line* initLine(line * head){
    head=(line*)malloc(sizeof(line));//创建链表第一个结点（首元结点）
    head->prior=NULL;
    head->next=NULL;
    head->data=1;
    line * list=head;
    for (int i=2; i<=3; i++) {
        //创建并初始化一个新结点
        line * body=(line*)malloc(sizeof(line));
        body->prior=NULL;
        body->next=NULL;
        body->data=i;
      
        list->next=body;//直接前趋结点的next指针指向新结点
        body->prior=list;//新结点指向直接前趋结点
        list=list->next;
    }
    return head;
}

Reference

FEATURED TAGS
algorithm algorithmproblem architecturalpattern architecture aws c# cachesystem codis concurrentcontrol database dataformat datastructure debug design designpattern distributedsystem django docker domain engineering freebsd git golang grafana hackintosh hadoop hardware hexo http hugo ios iot java javaee javascript kafka kubernetes linux linuxcommand linuxio lock macos markdown microservices mysql nas network networkprogramming nginx node.js npm oop openwrt operatingsystem padavan performance programming prometheus protobuf python redis router security shell software-testing spring sql systemdesign truenas ubuntu vmware vpn windows wmware wordpress zookeeper
FRIENDS

TOC