C语言中的双向链表

最近在看BIOS 中boot option相关的代码,看到一个地方突然蒙了,如下:

///
/// LIST_ENTRY structure definition.
///
typedef struct _LIST_ENTRY LIST_ENTRY;

///
/// _LIST_ENTRY structure definition.
///
struct _LIST_ENTRY {
  LIST_ENTRY  *ForwardLink;
  LIST_ENTRY  *BackLink;
};

网上查了一下,原来是一个双向链表, 这个还没有学过,脑中没什么概念, 那就学学吧!

有了单向链表,为什么还有双向链表? 区别是什么?  单向链表顾名思义, 就是只有一个方向, 我们在查询的时候只能从前到后查找, 要是想往前查找呢?单向是做不到的, 所以双向链表就出现了.

首先看下单向链表的定义:

struct list{
    int data;
    struct list *next;
};

示意图:

2019-12-26 17-20-49 的屏幕截图.png

可以看到,单向链表是用一个next指针指向下一个节点的, 双向链表就是在此基础上加一个指向上一个节点的指针, 修改后如下:

struct list{
    struct list *previous;
    int data;
    struct list *next;
};

2019-12-26 17-23-37 的屏幕截图.png

参考程序:

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;
}

版权声明:
作者:bin
链接:https://ay123.net/mystudy/clan/692/
来源:爱影博客
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>