【数据结构--双链表】

作者：凡人多烦事01 | 2024-04-15 10:38:42

踩

双链表

文章目录

双向链表

双向链表的定义

什么是双向链表？

双向链表顾名思义，就是链表由单向的链变成了双向链。双向链表(double linked list)是在单链表的每个结点中再设置一个指向其前驱结点的指针域。

非空带头结点的双向链表

在这里插入图片描述

双向链表的存储结构

//双链表节点结构体
typedef struct DoubleLinkNode
{
    char data;
    struct DoubleLinkNode* prior;
    struct DoubleLinkNode* next;
} Node,*NodePtr;
1
2
3
4
5
6
7

双向链表的初始化

//初始化
NodePtr initLinkList()
{
    NodePtr LinkHeader = (NodePtr)malloc(sizeof(Node));
    LinkHeader->data = '\0';
    LinkHeader->next = NULL;
    LinkHeader->prior = NULL;
    Linklength = 0;
    return LinkHeader;
}
1
2
3
4
5
6
7
8
9
10

双向链表的插入

双向链表的插入其实并不复杂，不过顺序很重要，千万不能写反了。

我们假设存储e的节点为q，要实现将结点q插入到结点p和p -> next之间需要下面几步，如下图所示。

在这里插入图片描述
顺序是先搞定q的前驱和后继，再搞定后结点的前驱，最后解决前结点的后继

代码如下：

//在某位置插入
void ListInsert(NodePtr LinkHeader, int InsertPosition, char InsertChar)
{
    if(InsertPosition < 0 || InsertPosition > Linklength)
    {
        printf("The position %d out of range of linked list!\n",InsertPosition);
        return ;
    }
    NodePtr p,q,r,tail;
    p = LinkHeader;
    for(int i = 0; i < InsertPosition; ++i)
    {
        p = p->next;
        if(!p)
        {
            printf("The position %d out of range of linked list!\n",InsertPosition);
            return ;
        }
    }
    q = (NodePtr)malloc(sizeof(Node));
    q->data = InsertChar;
    r = p->next;
    q->prior = p;
    q->next = r;
    p->next = q;
    if(r)
    {
        r->prior = q;
    }
    Linklength++;
}
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

双向链表的删除

如果插入操作理解了，那么删除操作就比较简单了。

若要删除节点q，只需要下面两个步骤，如下图所示。
在这里插入图片描述

代码如下：

//删除第Position个节点
void ListDeleteByPosition(NodePtr LinkHeader, int Position)
{
    NodePtr p,q,r,tail;
    int j = 0;
    tail = tailNodeSearch(LinkHeader);
    p = LinkHeader;
    while(p->next && j < Position)
    {
        p = p->next;
        ++j;
    }
    if(!(p->next) || j > Position)
    {
        printf("Can't delete it!\n");
        return ;
    }
    q = p->next;
    r = q->next;
    p->next = r;
    if(r)
    {
        r->prior = p;
    }
    free(q);
    Linklength--;
}
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

//删除第一个数据域为x的节点
void ListDeleteByData(NodePtr LinkHeader, char DeleteChar)
{
    NodePtr p,q,r;
    p = LinkHeader;
    while(p->next && p->next->data != DeleteChar)
    {
        p = p->next;
    }
    if(!(p->next))
    {
        printf("The char '%c' does't exist.\n",DeleteChar);
        return ;
    }
    q = p->next;
    r = q->next;
    p->next = r;
    if(r)
    {
        r->prior = p;
    }
    free(q);
    Linklength--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

寻找尾结点

双向链表与单链表不同的是单链表只能单向读取，双向链表可以双向读取，因此在反向打印时，需要先找到尾结点

//寻找尾节点
NodePtr tailNodeSearch(NodePtr LinkHeader)
{
    NodePtr p = LinkHeader;
    while(p->next)
    {
        p = p->next;
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10

正向打印

//正向打印
void printListByHead(NodePtr LinkHeader)
{
    NodePtr p = LinkHeader->next;
    while (p)
    {
        printf("%c",p->data);
        p = p->next;
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11

反向打印

//反向打印
void printListByTail(NodePtr LinkHeader)
{
    NodePtr tail = tailNodeSearch(LinkHeader);
    NodePtr p = tail;
    while (p)
    {
        printf("%c",p->data);
        p = p->prior;
    }
    printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

链表节点的读取

双链表除了有一个指向下一结点的指针外，还有一个指向前一结点的指针，可以双向遍历，故双链表的在查找时可利用二分法的思想去实现，那么这样效率就会大大提高。

//链表节点的读取（打印链表中第position个数据元素的值）
void GetElement(NodePtr LinkHeader, int position)
{
    NodePtr p,q,r;
    if(position <= Linklength/2)
    {
        p = LinkHeader->next;
        int j = 0;
        while(p && j < position)
        {
            p = p->next;
            ++j;
        }
        if(!p || j > position)
        {
            printf("Can't get it !\n");
            return ;
        }
        printf("The element at its %d-th position is %c\n",position,p->data);
    }else
    {
        p = tailNodeSearch(LinkHeader);
        int j = 0;
        while(p->prior && j < Linklength-position-1)
        {
            p = p->prior;
            ++j;
        }
        if(!p || j > Linklength-position-1)
        {
            printf("Can't get it !\n");
            return ;
        }
        printf("The element at its %d-th position is %c\n",position,p->data);
    }
}
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

测试运行截图

在这里插入图片描述

完整代码

#include <stdio.h>
#include <stdlib.h>
int Linklength;

//双链表节点结构体
typedef struct DoubleLinkNode
{
    char data;
    struct DoubleLinkNode* prior;
    struct DoubleLinkNode* next;
} Node,*NodePtr;

//初始化
NodePtr initLinkList()
{
    NodePtr LinkHeader = (NodePtr)malloc(sizeof(Node));
    LinkHeader->data = '\0';
    LinkHeader->next = NULL;
    LinkHeader->prior = NULL;
    Linklength = 0;
    return LinkHeader;
}

//寻找尾节点
NodePtr tailNodeSearch(NodePtr LinkHeader)
{
    NodePtr p = LinkHeader;
    while(p->next)
    {
        p = p->next;
    }
    return p;
}

//正向打印
void printListByHead(NodePtr LinkHeader)
{
    NodePtr p = LinkHeader->next;
    while (p)
    {
        printf("%c",p->data);
        p = p->next;
    }
    printf("\n");
}

//反向打印
void printListByTail(NodePtr LinkHeader)
{
    NodePtr tail = tailNodeSearch(LinkHeader);
    NodePtr p = tail;
    while (p)
    {
        printf("%c",p->data);
        p = p->prior;
    }
    printf("\n");
}

//在某位置插入
void ListInsert(NodePtr LinkHeader, int InsertPosition, char InsertChar)
{
    if(InsertPosition < 0 || InsertPosition > Linklength)
    {
        printf("The position %d out of range of linked list!\n",InsertPosition);
        return ;
    }
    NodePtr p,q,r,tail;
    p = LinkHeader;
    for(int i = 0; i < InsertPosition; ++i)
    {
        p = p->next;
        if(!p)
        {
            printf("The position %d out of range of linked list!\n",InsertPosition);
            return ;
        }
    }
    q = (NodePtr)malloc(sizeof(Node));
    q->data = InsertChar;
    r = p->next;
    q->prior = p;
    q->next = r;
    p->next = q;
    if(r)
    {
        r->prior = q;
    }
    Linklength++;
}

//删除第一个数据域为x的节点
void ListDeleteByData(NodePtr LinkHeader, char DeleteChar)
{
    NodePtr p,q,r;
    p = LinkHeader;
    while(p->next && p->next->data != DeleteChar)
    {
        p = p->next;
    }
    if(!(p->next))
    {
        printf("The char '%c' does't exist.\n",DeleteChar);
        return ;
    }
    q = p->next;
    r = q->next;
    p->next = r;
    if(r)
    {
        r->prior = p;
    }
    free(q);
    Linklength--;
}

//删除第Position个节点
void ListDeleteByPosition(NodePtr LinkHeader, int Position)
{
    NodePtr p,q,r,tail;
    int j = 0;
    tail = tailNodeSearch(LinkHeader);
    p = LinkHeader;
    while(p->next && j < Position)
    {
        p = p->next;
        ++j;
    }
    if(!(p->next) || j > Position)
    {
        printf("Can't delete it!\n");
        return ;
    }
    q = p->next;
    r = q->next;
    p->next = r;
    if(r)
    {
        r->prior = p;
    }
    free(q);
    Linklength--;
}

//链表节点的读取（打印链表中第position个数据元素的值）
void GetElement(NodePtr LinkHeader, int position)
{
    NodePtr p,q,r;
    if(position <= Linklength/2)
    {
        p = LinkHeader->next;
        int j = 0;
        while(p && j < position)
        {
            p = p->next;
            ++j;
        }
        if(!p || j > position)
        {
            printf("Can't get it !\n");
            return ;
        }
        printf("The element at its %d-th position is %c\n",position,p->data);
    }else
    {
        p = tailNodeSearch(LinkHeader);
        int j = 0;
        while(p->prior && j < Linklength-position-1)
        {
            p = p->prior;
            ++j;
        }
        if(!p || j > Linklength-position-1)
        {
            printf("Can't get it !\n");
            return ;
        }
        printf("The element at its %d-th position is %c\n",position,p->data);
    }
}

//测试
void insertDeleteTest()
{
    printf("---------------Initialize bidirectional linked list--------------\n");
    NodePtr tempList = initLinkList();
    printListByHead(tempList);
    printListByTail(tempList);

    printf("---------------Inserts a node at the specified location--------------\n");
    ListInsert(tempList,0,'H');
    ListInsert(tempList,1,'e');
    ListInsert(tempList,2,'l');
    ListInsert(tempList,3,'l');
    ListInsert(tempList,4,'o');
    
    printListByHead(tempList);
    printListByTail(tempList);

    printf("---------------Gets the node data field at the specified location--------------\n");
    GetElement(tempList,0);
    GetElement(tempList,4);
    GetElement(tempList,5);

    printf("---------------Delete the first node whose data field is X--------------\n");
    ListDeleteByData(tempList,'e');
    printListByHead(tempList);
    printListByTail(tempList);

    printf("---------------Delete the position node--------------\n");
    ListDeleteByPosition(tempList,3);
    printListByHead(tempList);
    printListByTail(tempList);
}

int main()
{
    insertDeleteTest();
}
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
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219

总结

双向链表相当于单链表来说，要复杂一些，对于插入和删除要格外小心。另外它由于每个结点都需要记录两份指针，所以在空间上的占用要略微多一些，说白了就是用空间换取时间。

双链表在查找时，我们可以借用二分法的思路，从head（首节点）向后查找操作和last（尾节点）向前查找操作同步进行，这样双链表的效率可以提高一倍。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/427402