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

示意图:

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

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

参考程序:

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