数据结构之带头双向循环链表_双循环链表删除尾结点

结构

1. 带头双向循环链表：结构最复杂，一般用在单独存储数据(头尾中间插入删除时间复杂度都为0(1))。
   实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，并且它的实现比单链表还简单。

---

实现

1. 头文件->list.h

#ifndef LIST_H_
#define LIST_H_

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;
typedef struct List
{
    LTDataType val;    //数据域
    struct List *next; //后驱指针域
    struct List *prev; //前驱指针域
} ListNode;

ListNode *BuyListNode(LTDataType x);               //创建新节点
ListNode *ListInit();                              //创建哨兵位头节点
void ListPrint(ListNode *phead);                   //显示链表数据
void ListPushBack(ListNode *phead, LTDataType x);  //尾插
void ListPopBack(ListNode *phead);                 //尾删
void ListPushFront(ListNode *phead, LTDataType x); //头插
void ListPopFront(ListNode *phead);                //头删
ListNode *ListFind(ListNode *phead, LTDataType X); //查找值为x的节点
void ListInsert(ListNode *pos, LTDataType x);      //在pos节点前插入新的节点
void ListErase(ListNode *pos);                     //删除pos位置的节点

#endif
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

2. 实现头文件的函数接口->list.c
   ps:记得包含头文件->#include “list.h”

BuyListNode接口->基本的动态开辟节点接口，不做多解释

ListNode *BuyListNode(LTDataType x)
{
    //创建新节点
    ListNode *newnode = (ListNode *)malloc(sizeof(ListNode));
    //判断新节点是否开辟成功
    if (newnode == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    else
    {
        newnode->val = x;
        newnode->next = NULL;
        newnode->prev = NULL;
    }
    return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

ListInit接口->基本的初始化头节点接口，不做多解释

istNode *ListInit()
{
    //开辟哨兵位头节点
    ListNode *phead = BuyListNode(0);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}
1
2
3
4
5
6
7
8

ListPrint接口->显示链表数据

void ListPrint(ListNode *phead)
{
    assert(phead);
    ListNode *cur = phead->next;
    //当cur为phead时，说明已走完一遍
    while (cur != phead)
    {
        printf("%d->", cur->val);
        cur = cur->next;
    }
    printf("phead\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

ListPushBack接口->尾插

void ListPushBack(ListNode *phead, LTDataType x)
{
    assert(phead);
    ListNode *newnode = BuyListNode(x);
    ListNode *tail = phead->prev;

    tail->next = newnode;
    newnode->prev = tail;

    newnode->next = phead;
    phead->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12

ListPopBack接口->头删

void ListPopBack(ListNode *phead)
{
    assert(phead);
    //当删到只有哨兵位时，哨兵位前驱后驱都指向自己，这时就不能再删了
    assert(phead->prev != phead);

    ListNode *tailPrev = phead->prev->prev;
    free(phead->prev);
    tailPrev->next = phead;
    phead->prev = tailPrev;
}
1
2
3
4
5
6
7
8
9
10
11

ListPushFront接口->头插

void ListPushFront(ListNode *phead, LTDataType x)
{
    assert(phead);
    ListNode *newnode = BuyListNode(x);
    ListNode *next = phead->next;

    newnode->next = next;
    next->prev = newnode;

    phead->next = newnode;
    newnode->prev = phead;
}
1
2
3
4
5
6
7
8
9
10
11
12

ListPopFront->头删

void ListPopFront(ListNode *phead)
{
    assert(phead);
    //当删到只有哨兵位时，哨兵位前驱后驱都指向自己，这时就不能再删了
    assert(phead->prev != phead);
    ListNode *head = phead->next;
    ListNode *next = phead->next->next;
    //如果只有一个节点时，要另外处理
    if (head->next == NULL)
    {
        free(head);
        phead->next = phead;
        phead->prev = phead;
    }
    else
    {
        free(phead->next);
        phead->next = next;
        next->prev = phead;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

ListFind接口->基本的查找数据接口，不做多解释

ListNode *ListFind(ListNode *phead, LTDataType x)
{
    ListNode *cur = phead->next;
    //当cur为phead时，说明已走完一遍
    while (cur != phead)
    {
        if (cur->val == x)
        {
            //找到返回这个值得节点地址
            return cur;
        }
        cur = cur->next;
    }
    //没找到返回空指针
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

ListInsert接口->在pos节点后面插入新节点

void ListInsert(ListNode *pos, LTDataType x)
{
    //不用判空
    ListNode *newnode = BuyListNode(x);
    ListNode *posPrev = pos->prev;
    //这里必须先链接newnode后面的节点,先链接前面的节点会找不到下一个节点
    newnode->next = pos;
    pos->prev = newnode;

    posPrev->next = newnode;
    newnode->prev = posPrev;
}
1
2
3
4
5
6
7
8
9
10
11
12

ListErase接口->删除pos位置节点

void ListErase(ListNode *pos)
{
    ListNode *posPrev = pos->prev;
    ListNode *posNext = pos->next;
    free(pos);
    posPrev->next = posNext;
    posNext->prev = posPrev;
}
1
2
3
4
5
6
7
8

最后一个接口->释放链表

void ListDestory(ListNode *head)
{
    assert(head);
    ListNode *cur = head->next;
    while (cur != head)
    {
        ListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    free(head);
}
1
2
3
4
5
6
7
8
9
10
11
12

---

完整代码

list.h
#ifndef LIST_H_
#define LIST_H_

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;
typedef struct List
{
    LTDataType val;    //数据域
    struct List *next; //后驱指针域
    struct List *prev; //前驱指针域
} ListNode;

ListNode *BuyListNode(LTDataType x);               //创建新节点
ListNode *ListInit();                              //创建哨兵位头节点
void ListPrint(ListNode *phead);                   //显示链表数据
void ListPushBack(ListNode *phead, LTDataType x);  //尾插
void ListPopBack(ListNode *phead);                 //尾删
void ListPushFront(ListNode *phead, LTDataType x); //头插
void ListPopFront(ListNode *phead);                //头删
ListNode *ListFind(ListNode *phead, LTDataType X); //查找值为x的节点
void ListInsert(ListNode *pos, LTDataType x);      //在pos节点前插入新的节点
void ListErase(ListNode *pos);                     //删除pos位置的节点
void ListDestory(ListNode *head);                  //释放链表

#endif

list.c
#include "list.h"

ListNode *BuyListNode(LTDataType x)
{
    //创建新节点
    ListNode *newnode = (ListNode *)malloc(sizeof(ListNode));
    if (newnode == NULL)
    {
        printf("malloc fail!!!\n");
        exit(EXIT_FAILURE);
    }
    else
    {
        newnode->val = x;
        newnode->next = NULL;
        newnode->prev = NULL;
    }
    return newnode;
}

ListNode *ListInit()
{
    //创建哨兵位头节点
    ListNode *phead = BuyListNode(0);
    phead->next = phead;
    phead->prev = phead;
    return phead;
}

void ListPrint(ListNode *phead)
{
    assert(phead);
    ListNode *cur = phead->next;
    //当cur为phead时，说明已走完一遍
    while (cur != phead)
    {
        printf("%d->", cur->val);
        cur = cur->next;
    }
    printf("phead\n");
}

void ListPushBack(ListNode *phead, LTDataType x)
{
    assert(phead);
    ListNode *newnode = BuyListNode(x);
    ListNode *tail = phead->prev;

    tail->next = newnode;
    newnode->prev = tail;

    newnode->next = phead;
    phead->prev = newnode;
}

void ListPopBack(ListNode *phead)
{
    assert(phead);
    //当删到只有哨兵位时，哨兵位前驱后驱都指向自己，这时就不能再删了
    assert(phead->prev != phead);

    ListNode *tailPrev = phead->prev->prev;
    free(phead->prev);
    tailPrev->next = phead;
    phead->prev = tailPrev;
}

void ListPushFront(ListNode *phead, LTDataType x)
{
    assert(phead);
    ListNode *newnode = BuyListNode(x);
    ListNode *next = phead->next;

    newnode->next = next;
    next->prev = newnode;

    phead->next = newnode;
    newnode->prev = phead;
}

void ListPopFront(ListNode *phead)
{
    assert(phead);
    //当删到只有哨兵位时，哨兵位前驱后驱都指向自己，这时就不能再删了
    assert(phead->prev != phead);
    ListNode *head = phead->next;
    ListNode *next = phead->next->next;
    if (head->next == NULL)
    {
        free(head);
        phead->next = phead;
        phead->prev = phead;
    }
    else
    {
        free(phead->next);
        phead->next = next;
        next->prev = phead;
    }
}

ListNode *ListFind(ListNode *phead, LTDataType x)
{
    ListNode *cur = phead->next;
    //当cur为phead时，说明已走完一遍
    while (cur != phead)
    {
        if (cur->val == x)
        {
            //找到返回这个值得节点地址
            return cur;
        }
        cur = cur->next;
    }
    //没找到返回空指针
    return NULL;
}

void ListInsert(ListNode *pos, LTDataType x)
{
    //这里不用判空
    ListNode *newnode = BuyListNode(x);
    ListNode *posPrev = pos->prev;
    //这里必须先链接newnode后面的节点,先链接前面的节点会找不到下一个节点
    newnode->next = pos;
    pos->prev = newnode;

    posPrev->next = newnode;
    newnode->prev = posPrev;
}

void ListErase(ListNode *pos)
{
    ListNode *posPrev = pos->prev;
    ListNode *posNext = pos->next;
    free(pos);
    posPrev->next = posNext;
    posNext->prev = posPrev;
}

void ListDestory(ListNode *head)
{
    assert(head);
    ListNode *cur = head->next;
    while (cur != head)
    {
        ListNode *next = cur->next;
        free(cur);
        cur = next;
    }
    free(head);
}

Test.c
#include "list.h"
int main()
{
    //测试

    //尾插
    ListNode *phead = ListInit();
    ListPushBack(phead, 1);
    ListPushBack(phead, 2);
    ListPushBack(phead, 3);
    ListPushBack(phead, 4);
    ListPushBack(phead, 5);
    ListPushBack(phead, 6);

    ListPrint(phead);

    //尾删
    ListPopBack(phead);
    ListPopBack(phead);
    ListPrint(phead);

    //头插
    ListPushFront(phead, 0);
    ListPushFront(phead, -1);
    ListPushFront(phead, -2);
    ListPrint(phead);

    //头删
    ListPopFront(phead);
    ListPopFront(phead);
    ListPopFront(phead);
    ListPrint(phead);

    //在pos后面插入新节点
    ListNode *pos = ListFind(phead, 2);
    if (pos)
        ListInsert(pos, 100);
    else
        printf("Don't find.....\n");
    ListPrint(phead);

    //删除pos位置的节点
    ListNode *pos2 = ListFind(phead, 2);
    if (pos)
        ListErase(pos2);
    else
        printf("Don't find.....\n");
    ListPrint(phead);
    
    ListDestory(phead);
    system("pause");
    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
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
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238

顺序表和链表的区别

1. 这个结构是相辅相成的
   顺序表的优点：
   1、物理空间是连续的，方便下标随机访问。
   2、CPU高速缓存命中率更高。
   缺点：
   1、由于需要物理空间连续，空间不够需要扩容。扩容本身有一定的效率消耗，其次扩容机制还存在一定的空间浪费。
   2、头部或者中间插入删除，需要挪动数据，效率低，时间复杂度为O(n)。

2.链表的优点：
1、任意位置插入删除数据效率高(带头双向循环链表)，时间复杂度为0(1)。
2、可以按需申请和释放空间。
缺点：不支持下标的随机访问。大多数算法不适合在他水面进行。(如：快排，二分查找等等…)

---

高速缓存命中率问题

1. 这里除了本地二级存储(本地磁盘)为不带电存储之外，其他都是带电存储，如果你的电脑还没有保存好数据就直接关机，会造成数据丢失

2. 一个程序在编译链接后，生成可执行程序，CPU执行这个程序，并且要去访问内存
3. CPU不会直接访问内存，因为内存的速度太慢了，会把数据加载到三级缓冲(大数据)或寄存器(4或8Byte小数据)中
4. CPU会看数据是否在缓存中，在就叫做"命中"，直接访问它，不在就叫"不命中"，CPU会先把数据从内存加载到缓存中，在进行访问。
5. 顺序表是一个连续的空间，CPU会将一块连续的空间加载到缓存中，所以说顺序表的高速缓存命中率高
6. 链表是随机开辟节点存储的，它不是一块连续的空间，所以高速缓存命中率低…

高速缓存相关知识

---

知识点已经讲完了，如有错误请指出，感谢！！！