【数据结构】第五站：带头双向循环链表

目录

一、链表的八种结构

二、带头双向循环链表的实现

1.链表的定义

2.链表的接口定义

3.接口的具体实现

三、带头双向循环链表的完整代码

四、顺序表和链表的区别

---

一、链表的八种结构

我们已经知道链表可以有以下三种分法

 

 

而这三种结构又可以排列组合，形成八种结构

其中我们最常见的就是无头单向非循环链表和带头双向循环链表

1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了

二、带头双向循环链表的实现

1.链表的定义

对于这个链表，我们需要使用两个指针来控制，一个是前驱指针，一个是后继指针

typedef int LTDateType;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDateType data;
}ListNode;

2.链表的接口定义

如下代码所示，是我们需要实现的接口

//链表的初始化
ListNode* ListCreat();
//链表的打印
void ListPrint(ListNode* phead);
//链表的尾插
void ListPushBack(ListNode* phead, LTDateType x);
//链表的头插
void ListPushFront(ListNode* phead, LTDateType x);
//链表是否为空
bool ListEmpty(ListNode* phead);
//链表的尾删
void ListPopBack(ListNode* phead);
//链表的头删
void ListPopFront(ListNode* phead);
//链表的查找
ListNode* ListFind(ListNode* phead, LTDateType x);
//链表在pos前面的插入
void ListInsert(ListNode* pos, LTDateType x);
//链表在pos位置处的删除
void ListErase(ListNode* pos);
//链表的销毁
void ListDestroy(ListNode* phead);

3.接口的具体实现

1.链表的初始化

ListNode* BuyListNode(LTDateType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");return NULL;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}
//链表的初始化
ListNode* ListCreat()
{ListNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}

如上代码所示，对于这个初始化，他与单链表不同，单链表其实是没有必要去专门做一个初始化函数的。但同时我们需要传二级指针来解决一些问题

对于双向带头循环链表，我们就有必要设置一个初始化函数了。

我们有两种思路去构建这个函数

一种是在主函数中直接定义一个指针，然后通过传这个指针的地址去构建。但是这样我们就需要传二级指针了。

另外一种是我们可以利用返回值，这样我们就直接避免了传参数了。

2.链表的打印

//链表的打印
void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;printf("<=head=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}

如上代码所示，链表的打印与单链表的打印是一样的，没有什么太大的区别，我们可以利用printf来更加形象的表达双向循环的意思

3.链表的尾插

//链表的尾插
void ListPushBack(ListNode* phead, LTDateType x)
{assert(phead);ListNode* newnode = BuyListNode(x);ListNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

对于尾插就比单链表简单多了，因为有了头节点，我们就不需要处理是否为空的状态了

4.链表的头插

//链表的头插
void ListPushFront(ListNode* phead, LTDateType x)
{assert(phead);ListNode* newnode = BuyListNode(x);ListNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}

头插和尾插基本上是非常类似的，这也得益于这种链表结构基本是无死角的

5.链表的头删尾删以及是否为空

//链表是否为空
bool ListEmpty(ListNode* phead)
{assert(phead);return phead->next == phead;
}
//链表的尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(!ListEmpty(phead));ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;phead->prev = tailPrev;tailPrev->next = phead;free(tail);tail = NULL;
}
//链表的头删
void ListPopFront(ListNode* phead)
{assert(phead);assert(!ListEmpty(phead));ListNode* first = phead->next;ListNode* firstNext = first->next;phead->next = firstNext;firstNext->prev = phead;free(first);first = NULL;
}

对于头删和尾删其实也是一致的思路，我们只需要改变结点即可，值得注意的是，我们需要判断链表是否为空， 如果为空肯定不可以删除

6.链表的查找

//链表的查找
ListNode* ListFind(ListNode* phead,LTDateType x)
{assert(phead);assert(!ListEmpty(phead));ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

这个也是比较简单的，他的思路与单链表的是一样的

7.链表在pos位置之前插入

//链表在pos前面的插入
void ListInsert(ListNode* pos, LTDateType x)
{assert(pos);ListNode* newnode = BuyListNode(x);ListNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}

这个的话，我们更能体会到他相对于单链表的优势了。我们只需要pos位置即可。然后思路和头插尾插是一致的

8.链表在pos位置的删除

//链表在pos位置处的删除
void ListErase(ListNode* pos)
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);pos = NULL;
}

对于删除，也是与头删尾删思路一致的

9.链表的销毁

//链表的销毁
void ListDestroy(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}

对于链表的销毁思路与单链表也是一致的，只需要循环遍历即可

三、带头双向循环链表的完整代码

List.h

#pragma once
#include<stdio.h>
#include<malloc.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDateType;
typedef struct ListNode
{struct ListNode* prev;struct ListNode* next;LTDateType data;
}ListNode;//链表的初始化
ListNode* ListCreat();
//链表的打印
void ListPrint(ListNode* phead);
//链表的尾插
void ListPushBack(ListNode* phead, LTDateType x);
//链表的头插
void ListPushFront(ListNode* phead, LTDateType x);
//链表是否为空
bool ListEmpty(ListNode* phead);
//链表的尾删
void ListPopBack(ListNode* phead);
//链表的头删
void ListPopFront(ListNode* phead);
//链表的查找
ListNode* ListFind(ListNode* phead, LTDateType x);
//链表在pos前面的插入
void ListInsert(ListNode* pos, LTDateType x);
//链表在pos位置处的删除
void ListErase(ListNode* pos);
//链表的销毁
void ListDestroy(ListNode* phead);

List.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
ListNode* BuyListNode(LTDateType x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc");return NULL;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;
}
//链表的初始化
ListNode* ListCreat()
{ListNode* phead = BuyListNode(-1);phead->next = phead;phead->prev = phead;return phead;
}
//链表的打印
void ListPrint(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;printf("<=head=>");while (cur != phead){printf("%d<=>", cur->data);cur = cur->next;}printf("\n");
}
//链表的尾插
void ListPushBack(ListNode* phead, LTDateType x)
{assert(phead);ListNode* newnode = BuyListNode(x);ListNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}
//链表的头插
void ListPushFront(ListNode* phead, LTDateType x)
{assert(phead);ListNode* newnode = BuyListNode(x);ListNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}
//链表是否为空
bool ListEmpty(ListNode* phead)
{assert(phead);return phead->next == phead;
}
//链表的尾删
void ListPopBack(ListNode* phead)
{assert(phead);assert(!ListEmpty(phead));ListNode* tail = phead->prev;ListNode* tailPrev = tail->prev;phead->prev = tailPrev;tailPrev->next = phead;free(tail);tail = NULL;
}
//链表的头删
void ListPopFront(ListNode* phead)
{assert(phead);assert(!ListEmpty(phead));ListNode* first = phead->next;ListNode* firstNext = first->next;phead->next = firstNext;firstNext->prev = phead;free(first);first = NULL;
}
//链表的查找
ListNode* ListFind(ListNode* phead,LTDateType x)
{assert(phead);assert(!ListEmpty(phead));ListNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
//链表在pos前面的插入
void ListInsert(ListNode* pos, LTDateType x)
{assert(pos);ListNode* newnode = BuyListNode(x);ListNode* prev = pos->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos;pos->prev = newnode;
}
//链表在pos位置处的删除
void ListErase(ListNode* pos)
{assert(pos);ListNode* prev = pos->prev;ListNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);pos = NULL;
}
//链表的销毁
void ListDestroy(ListNode* phead)
{assert(phead);ListNode* cur = phead->next;while (cur != phead){ListNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1#include"List.h"void TestList1()
{ListNode* plist = ListCreat();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);ListPrint(plist);ListPushFront(plist, 6);ListPushFront(plist, 7);ListPushFront(plist, 8);ListPushFront(plist, 9);ListPushFront(plist, 10);ListPrint(plist);ListPopBack(plist);ListPopBack(plist);ListPopBack(plist);ListPopBack(plist);ListPrint(plist);ListPopFront(plist);ListPopFront(plist);ListPopFront(plist);ListPopFront(plist);ListPrint(plist);}
void TestList2()
{ListNode* plist = ListCreat();ListPushBack(plist, 1);ListPushBack(plist, 2);ListPushBack(plist, 3);ListPushBack(plist, 4);ListPushBack(plist, 5);ListPrint(plist);ListNode* pos = ListFind(plist, 3);(pos->data) *= 10;ListPrint(plist);ListInsert(pos, 20);ListPrint(plist);ListErase(pos);ListPrint(plist);}
int main()
{//TestList1();TestList2();return 0;
}

四、顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持，O(1)	不支持，O(N)
任意位置插入或删除元素	可能需要搬移元素，效率低，O(N)	只需要改变指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

如上表所示，是顺序表和链表的区别

在这里我们需要注意缓存利用率这个东西。

对于我们的顺序表/链表，想要实现他的数据访问、遍历、修改等

这些数据是由cpu来进行访问的。

也就是这些访问的指令都是cpu执行的。从而访问打印等操作。这时候cpu就需要去访问内存

而cpu其实是不能直接访问内存的，这是因为cpu太快了，内存太慢了

为了解决这个问题，就有了三级缓存，即cpu高速缓存这个东西。

也就是说cpu会先访问缓存，最高级的缓存再次缓存其实就是命中。

在计算机中有一个局部性原理，在访问某个位置的数据的时候，大概率要访问后面的数据。因此他就会将这个数据后面的数据也顺便加载进去。

这时候由于顺序表是连续的，后面的都直接被命中了。所以他的缓存利用率高

而链表他访问某个数据的时候也会加载一长段，但是后面的不一定会用。所以就会浪费，也会导致缓存污染。所以缓存利用率低。也就是他不仅没有起到正向作用，反而起到了反向作用。

---

本节内容到此位置

如果对你有帮助的话，不要忘记点赞加收藏哦！！！