大家好我是沐曦希💕
1.前言
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了,可以通过对比无头单向链表实现代码进行对比。
2.带头双向循环链表的实现
2.1 List.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
LTDataType val;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//初始化带头双向循环链表
LTNode* ListInit(LTNode* phead);
//销毁链表
void ListDestory(LTNode* phead);
//尾插数据
void ListPushBack(LTNode* phead, LTDataType x);
//打印链表中的数据
void ListPrint(LTNode* phead);
//头插数据
void ListPushFront(LTNode* phead, LTDataType x);
//尾删数据
void ListPopBack(LTNode* phead);
//头删数据
void ListPopFront(LTNode* phead);
//检测链表是否为空
bool ListEmpty(LTNode* phead);
//计录链表有多少的数据
size_t ListSize(LTNode* phead);
//查找链表中数据
LTNode* ListFind(LTNode* phead, LTDataType x);
//在pos位置之前插入数据
void ListInsert(LTNode* pos, LTDataType x);
//删除pos位置
void ListErase(LTNode* pos);
2.2 test.c
#include"List.h"
void test1()
{
LTNode* plist = NULL;
plist = ListInit(plist);
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPrint(plist);
ListPushFront(plist, 40);
ListPushFront(plist, 30);
ListPushFront(plist, 20);
ListPushFront(plist, 10);
ListPrint(plist);
ListPopBack(plist);
ListPopBack(plist);
ListPopBack(plist);
ListPopBack(plist);
ListPrint(plist);
ListPopFront(plist);
ListPrint(plist);
ListPopFront(plist);
ListPopFront(plist);
ListPrint(plist);
ListDestory(plist);
plist = NULL;
}
void test2()
{
LTNode* plist = NULL;
plist = ListInit(plist);
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPrint(plist);
ListPushFront(plist, 40);
ListPushFront(plist, 30);
ListPushFront(plist, 20);
ListPushFront(plist, 10);
ListPrint(plist);
LTNode* cur = ListFind(plist, 30);
printf("%d\n", cur->val);
ListInsert(cur, 100);
ListPrint(plist);
cur = ListFind(plist, 10);
printf("%d\n", cur->val);
ListErase(cur);
ListPrint(plist);
ListDestory(plist);
plist = NULL;
}
int main()
{
test1();
test2();
return 0;
}
2.3 List.c
#include"List.h"
LTNode* ListInit(LTNode* phead)
{
//创建哨兵位
phead = (LTNode*)malloc(sizeof(LTNode));
if (phead == NULL)
{
perror("malloc fail");
exit(-1);
}
//实现双向循环的功能
phead->next = phead;
phead->prev = phead;
return phead;
}
//用一级指针，让调用ListDestory的人置空
//保持接口一致性
void ListDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
//从哨兵位的下一个节点遍历一遍并释放，直到cur回到phead停止
LTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}
LTNode* BuyListNode(LTDataType x)
{
//该函数实现了创建一个新节点
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(-1);
}
newnode->val = x;
newnode->next = NULL;
newnode->prev = NULL;
}
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
/*LTNode* tail = phead->prev;
LTNode* newnode = BuyListNode(x);
tail->next = newnode;
newnode->next = phead;
newnode->prev = tail;
phead->prev = newnode;*/
ListInsert(phead, x);
//尾插可以看成在pos=phead之前插入一个新节点
}
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
printf("phead<=>");
while (cur != phead)
{
//从哨兵位的下一个节点遍历一遍并打印数据，直到cur回到phead停止
LTNode* next = cur->next;
printf("%d<=>", cur->val);
cur = next;
}
printf("\n");
}
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
/*LTNode* next = phead->next;
LTNode* newnode = BuyListNode(x);
newnode->next = next;
next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;*/
ListInsert(phead->next, x);
//头插可以看成在pos=phead->next之前插入一个新节点
}
void ListPopBack(LTNode* phead)
{
/*assert(phead);
assert(!ListEmpty(phead));
//检测链表是否还有数据可以删除
LTNode* tail = phead->prev;
LTNode* prev = tail->prev;
phead->prev = prev;
prev->next = phead;
free(tail);
tail = NULL;*/
ListErase(phead->prev);
//尾删可以看成是删除pos=phead->prev的节点
}
void ListPopFront(LTNode* phead)
{
/*assert(phead);
assert(!ListEmpty(phead));
//检测链表是否还有数据可以删除
LTNode* cur = phead->next;
phead->next = cur->next;
cur->next->prev = phead;
free(cur);
cur = NULL;*/
ListErase(phead->next);
//头删可以看成是删除pos=phead->next的节点
}
bool ListEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
//如果phead->next等于phead，表明没有数据。
//不等于，表明链表还有数据。
}
size_t ListSize(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
size_t count = 0;
while (cur != phead)
{
count++;
cur = cur->next;
}
return count;
}
LTNode* ListFind(LTNode* phead, LTDataType x)
{
//查找经常用来进行删除和插入等操作，而不是单单进行查找操作
assert(phead);
LTNode* cur = phead->next;
while (cur->next != phead)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
newnode->prev = pos->prev;
pos->prev->next = newnode;
pos->prev = newnode;
newnode->next = pos;
}
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
3.顺序表和链表的区别
| 不同点 | 顺序表 | 链表（带头双向循环） |
|---|---|---|
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
顺序表的优点（存储数据用顺序表多）：
1.尾插尾删效率高。
2.随机访问（用下标访问）
3.相比链表结构——顺序表CPU高速缓存命中率更高。
备注：缓存利用率参考存储体系结构 以及 局部原理性。
CPU执行指令，不会直接访问内存。先看数据在不在三级缓存：在（命中），直接访问；不在（不命中），先加载带缓存，再访问。
加载缓存时会从一个位置开始加载一段进入缓存（加载多少取决于硬件）。
顺序表是连续存储，加载进缓存的是有效数据，CPU高速缓存命中率效率更高。而链表不是连续存储的，各个地址之间没有关联的，所以加载进缓存的可能就一个有效数据，那么命中率低还污染。
顺序表的缺点：
1.头部和中部插入删除效率低——O(N)
2.扩容——性能消耗+空间浪费
链表的优点：
1.任意位置插入删除效率很高。——O(N)
2.按需申请释放+不存在空间浪费。
链表的缺点：
1.不支持随机访问。
4.写在最后
那么带头双向循环链表就到这里了。
