title: 数据结构与算法（三）双向链表(C语言)date: 2021-06-25 15:52:57.609

updated: 2021-06-25 20:41:18.577
url: /?p=260
categories: 数据结构与算法
tags: 数据结构与算法

双向链表

表中各节点中都只包含一个指针（游标），且都统一指向直接后继节点，通常称这类链表为单向链表（或单链表）。

单链表能 100% 解决逻辑关系为 “一对一” 数据的存储问题，但在解决某些特殊问题时，单链表并不是效率最优的存储结构。比如说，如果算法中需要大量地找某指定结点的前趋结点，使用单链表无疑是灾难性的，因为单链表更适合 “从前往后” 找，而 “从后往前” 找并不是它的强项。

因此，引入双向链表。

双向链表。顾名思义，链表是 “双向” 的。

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

双向链表各个结点的包含3部分的信息：

  1. 指针域：用于指向当前节点的直接前驱节点；
  2. 数据域：用于存储数据；
  3. 指针域：用于指向当前节点的直接后继节点；

双向链表的结点的结构体：

1
2
3
4
5
6
typedef struct dNode
{
    struct dNode *prior; //指向前驱结点的指针
    int data;            //数据域
    struct dNode *next;  //指向后继结点的指针
} dnode;

双向链表的创建

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
#include <stdio.h>
#include <stdlib.h>

// 双向链表结构体
typedef struct dNode
{
    struct dNode *prior; //指向前驱结点的指针
    int data;            //数据域
    struct dNode *next;  //指向后继结点的指针
} dnode;

dnode *initDLink();
void initData(dnode *);
void displayDLink(dnode *);

int main()
{
    dnode *dlink = initDLink();
    initData(dlink);
    displayDLink(dlink);
    return 0;
}

// 初始化双向链表
dnode *initDLink()
{
    dnode *head = (dnode *)malloc(sizeof(dnode));

    head->data = 0;
    head->next = NULL;
    head->prior = NULL;

    return head;
}

// 给双向链表初始化数据
void initData(dnode *d)
{
    dnode *temp = d;
    for (size_t i = 0; i < 10; i++)
    {
        //创建新的节点并初始化
        dnode *newNode = (dnode *)malloc(sizeof(dnode));
        newNode->prior = NULL;
        newNode->data = i * 10;
        newNode->next = NULL;
        //新节点与链表最后一个节点建立关系
        temp->next = newNode;
        newNode->prior = temp;
        //temp永远指向链表中最后一个节点
        temp = temp->next;
    }
}

void displayDLink(dnode *d)
{
    printf("输出双向链表：");
    dnode *temp = d;
    while (temp->next != NULL)
    {
        temp = temp->next;
        printf("%d ", temp->data);
    }
}
1
输出双向链表：0 10 20 30 40 50 60 70 80 90

双向链表添加节点

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

1.
添加至表头

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

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

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


2.
添加至表的中间位置

同单链表添加数据类似，双向链表中间位置添加数据需要经过以下 2 个步骤：

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


3.
添加至表尾

与添加到表头是一个道理，实现过程如下：

  1. 找到双链表中最后一个节点；
  2. 让新节点与最后一个节点进行双层逻辑关系；

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
void insertElem(dnode *d, int elem, int index)
{
    printf("在下标%d处插入元素%d", index, elem);
    dnode *newNode = (dnode *)malloc(sizeof(dnode));
    newNode->next = NULL;
    newNode->data = elem;
    newNode->prior = NULL;

    if (index == 0)
    {
        // newNode->next = d->next;
        // d->prior = newNode;
        // d->next = newNode;
        newNode->next = d->next;
        d->next->prior = newNode;
        d->next = newNode;
        newNode->prior = d;
    }
    else
    {
        dnode *temp = d;
        for (size_t i = 0; i < index; i++)
        {
            temp = temp->next;
        }

        if (temp->next == NULL)
        {
            newNode->next = NULL;
            temp->next = newNode;
            newNode->prior = temp;
        }
        else
        {
            newNode->next = temp->next;
            temp->next->prior = newNode;
            //
            temp->next = newNode;
            newNode->prior = temp;
        }
    }
    //输出
    displayDLink(d);
}

双向链表删除节点

双链表删除结点时，只需遍历链表找到要删除的结点，然后将该节点从表中摘除即可。

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
void delElem(dnode *d, int data)
{
    printf("删除数据为%d元素", data);
    //
    dnode *temp = d;
    while (temp->next != NULL)
    {
        temp = temp->next;
        if (temp->data == data)
        {
            if (temp->prior != NULL && temp->next != NULL)
            {
                temp->prior->next = temp->next;
                temp->next->prior = temp->prior;
            }
            else
            {
                temp->prior->next = NULL;
            }
            free(temp);
            //输出
            displayDLink(d);
            return;
        }
    }
    printf(" 链表中无该数据元素\n");
}
1
2
3
4
// 在下标6处插入元素1000输出双向链表：1000 0 10 20 1000 30 1000 40 50 60 70 80 90 
删除数据为1000元素输出双向链表：0 10 20 1000 30 1000 40 50 60 70 80 90 
删除数据为10元素输出双向链表：0 20 1000 30 1000 40 50 60 70 80 90 
删除数据为90元素输出双向链表：0 20 1000 30 1000 40 50 60 70 8

双向链表查找节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int selectElem(dnode *d, int elem)
{
    printf("查找元素%d的索引：", elem);

    int index = 0;
    dnode *temp = d;
    while (temp->next != NULL)
    {
        temp = temp->next;
        if (temp->data == elem)
        {
            return index;
        }
        index++;
    }

    return -1;
}

双向链表更改节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void updateElem(dnode *d, int index, int elem)
{
    int i = 0;
    dnode *temp = d;
    while (temp->next != NULL)
    {
        temp = temp->next;
        if (i == index)
        {
            temp->data = elem;
            displayDLink(d);
            return;
        }
        i++;
    }
}

以上完整代码

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include <stdio.h>
#include <stdlib.h>

// 双向链表结构体
typedef struct dNode
{
    struct dNode *prior; //指向前驱结点的指针
    int data;            //数据域
    struct dNode *next;  //指向后继结点的指针
} dnode;

dnode *initDLink();
void initData(dnode *);
void displayDLink(dnode *);
void insertElem(dnode *, int, int);
void delElem(dnode *, int);
int selectElem(dnode *, int);
void updateElem(dnode *, int, int);

int main()
{
    dnode *dlink = initDLink();
    initData(dlink);
    displayDLink(dlink);
    insertElem(dlink, 1000, 0);
    insertElem(dlink, 1000, 4);
    insertElem(dlink, 1000, 6);
    delElem(dlink, 1000);
    delElem(dlink, 10);
    delElem(dlink, 90);
    printf("index = %d\n", selectElem(dlink, 1000));
    printf("index = %d\n", selectElem(dlink, 40));
    displayDLink(dlink);
    updateElem(dlink, 3, 999);
    return 0;
}

// 初始化双向链表
dnode *initDLink()
{
    dnode *head = (dnode *)malloc(sizeof(dnode));

    head->data = 0;
    head->next = NULL;
    head->prior = NULL;

    return head;
}

// 给双向链表初始化数据
void initData(dnode *d)
{
    dnode *temp = d;
    for (size_t i = 0; i < 10; i++)
    {
        //创建新的节点并初始化
        dnode *newNode = (dnode *)malloc(sizeof(dnode));
        newNode->prior = NULL;
        newNode->data = i * 10;
        newNode->next = NULL;
        //新节点与链表最后一个节点建立关系
        temp->next = newNode;
        newNode->prior = temp;
        //temp永远指向链表中最后一个节点
        temp = temp->next;
    }
}

void displayDLink(dnode *d)
{
    printf("输出双向链表：");
    dnode *temp = d;
    while (temp->next != NULL)
    {
        temp = temp->next;
        printf("%d ", temp->data);
    }
    printf("\n");
}

void insertElem(dnode *d, int elem, int index)
{
    printf("在下标%d处插入元素%d", index, elem);
    dnode *newNode = (dnode *)malloc(sizeof(dnode));
    newNode->next = NULL;
    newNode->data = elem;
    newNode->prior = NULL;

    if (index == 0)
    {
        // newNode->next = d->next;
        // d->prior = newNode;
        // d->next = newNode;
        newNode->next = d->next;
        d->next->prior = newNode;
        d->next = newNode;
        newNode->prior = d;
    }
    else
    {
        dnode *temp = d;
        for (size_t i = 0; i < index; i++)
        {
            temp = temp->next;
        }

        if (temp->next == NULL)
        {
            newNode->next = NULL;
            temp->next = newNode;
            newNode->prior = temp;
        }
        else
        {
            newNode->next = temp->next;
            temp->next->prior = newNode;
            //
            temp->next = newNode;
            newNode->prior = temp;
        }
    }
    //输出
    displayDLink(d);
}

void delElem(dnode *d, int data)
{
    printf("删除数据为%d元素", data);
    //
    dnode *temp = d;
    while (temp->next != NULL)
    {
        temp = temp->next;
        if (temp->data == data)
        {
            if (temp->prior != NULL && temp->next != NULL)
            {
                temp->prior->next = temp->next;
                temp->next->prior = temp->prior;
            }
            else
            {
                temp->prior->next = NULL;
            }
            free(temp);
            //输出
            displayDLink(d);
            return;
        }
    }
    printf(" 链表中无该数据元素\n");
}

int selectElem(dnode *d, int elem)
{
    printf("查找元素%d的索引：", elem);

    int index = 0;
    dnode *temp = d;
    while (temp->next != NULL)
    {
        temp = temp->next;
        if (temp->data == elem)
        {
            return index;
        }
        index++;
    }

    return -1;
}

void updateElem(dnode *d, int index, int elem)
{
    int i = 0;
    dnode *temp = d;
    while (temp->next != NULL)
    {
        temp = temp->next;
        if (i == index)
        {
            temp->data = elem;
            displayDLink(d);
            return;
        }
        i++;
    }
}
1
2
3
4
5
6
7
8
9
10
11
输出双向链表：0 10 20 30 40 50 60 70 80 90
在下标0处插入元素1000输出双向链表：1000 0 10 20 30 40 50 60 70 80 90
在下标4处插入元素1000输出双向链表：1000 0 10 20 1000 30 40 50 60 70 80 90
在下标6处插入元素1000输出双向链表：1000 0 10 20 1000 30 1000 40 50 60 70 80 90
删除数据为1000元素输出双向链表：0 10 20 1000 30 1000 40 50 60 70 80 90
删除数据为10元素输出双向链表：0 20 1000 30 1000 40 50 60 70 80 90
删除数据为90元素输出双向链表：0 20 1000 30 1000 40 50 60 70 80
查找元素1000的索引：index = 2
查找元素40的索引：index = 5
输出双向链表：0 20 1000 30 1000 40 50 60 70 80
输出双向链表：1000 40 50 60 70 80