双向链表的操作

什么是双向链表？

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

typedef struct line{
    struct line * prior; //指向直接前趋，结构体类型line的地址
    int data; //数据域
    struct line * next; //指向直接后继
}Line;
1
2
3
4
5

双向链表的创建

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

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

1. 将新节点的 prior 指针指向直接前驱节点；
2. 将直接前驱节点的 next 指针指向新节点；

Line* initLine(Line* head) {
    Line* list = NULL;
    head = (Line*)malloc(sizeof(Line));//创建链表第一个结点（首元结点）
    head->prior = NULL;
    head->next = NULL;
    head->data = 1;
    list = head;
    for (int i = 2; i <= 5; i++) {
        //创建并初始化一个新结点
        Line* body = (Line*)malloc(sizeof(Line));
        body->prior = NULL;
        body->next = NULL;
        body->data = i;
        //直接前趋结点的next指针指向新结点
        list->next = body;
        //新结点指向直接前趋结点
        body->prior = list;
        list = list->next;
    }
    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

Line* initLine(Line* head) {
    int i;
    Line* list = NULL;
    head = (Line*)malloc(sizeof(Line));//创建链表第一个结点（首元结点）
    head->prior = NULL;
    head->next = NULL;
    head->data = 1;
    list = head;
    for (i = 2; i <= 5; i++) {
        //创建并初始化一个新结点
        Line* body = (Line*)malloc(sizeof(Line));
        body->prior = NULL;
        body->next = NULL;
        body->data = i;
        //直接前趋结点的next指针指向新结点
        list->next = body;
        //新结点指向直接前趋结点
        body->prior = list;
        list = list->next;
    }
    return head;
}
//输出链表中的数据
void display(Line* head) {
    Line* temp = head;
    while (temp) {
        //如果该节点无后继节点，说明此节点是链表的最后一个节点
        if (temp->next == NULL) {
            printf("%d\n", temp->data);
        }
        else {
            printf("%d <-> ", temp->data);
        }
        temp = temp->next;
    }
}
//释放链表中结点占用的空间
void free_line(Line* head) {
    Line* temp = head;
    while (temp) {
        head = head->next;
        free(temp);
        temp = head;
    }
}

int main()
{
    //创建一个头指针
    Line* head = NULL;
    //调用链表创建函数
    head = initLine(head);
    //输出创建好的链表
    display(head);
    //显示双链表的优点
    printf("链表中第 4 个节点的直接前驱是：%d", head->next->next->next->prior->data);
    free_line(head);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

1. 双向链表添加节点

根据数据添加到双向链表中的位置不同，可细分为以下 3 种情况：

1. 添加至表头
   将新数据元素添加到表头，只需要将该元素与表头元素建立双层逻辑关系即可。

换句话说，假设新元素节点为 temp，表头节点为 head，则需要做以下 2 步操作即可：

1. temp->next=head; head->prior=temp;
2. 将 head 移至 temp，重新指向新的表头；

2. 添加至表的中间位置

1. 新节点先与其直接后继节点建立双层逻辑关系；
2. 新节点的直接前驱节点与之建立双层逻辑关系；

3. 添加至表尾

与添加到表头是一样，但是next指向NULL
找到双链表中最后一个节点；
让新节点与最后一个节点进行双层逻辑关系；

双向链表删除节点

和添加结点的思想类似，在双向链表中删除目标结点也分为 3 种情况。

1. 删除表头结点

删除表头结点的实现过程是：

1. 新建一个指针指向表头结点；
2. 断开表头结点和其直接后续结点之间的关联，更改 head 头指针的指向，同时将其直接后续结点的 prior 3指针指向 NULL；
3. 释放表头结点占用的内存空间。

2. 删除表中结点

删除表中结点的过程如下图所示：

删除表中结点的实现过程是：

1. 找到目标结点，新建一个指针指向改结点；
2. 将目标结点从链表上摘除；
3. 释放该结点占用的内存空间。

3. 删除表尾结点

删除表尾结点的实现过程是：

1. 找到表尾结点，新建一个指针指向该结点；
2. 断点表尾结点和其直接前驱结点的关联，并将其直接前驱结点的 next 指针指向 NULL；
3. 释放表尾结点占用的内存空间。