网络知识 娱乐 【数据结构初阶】带头双向循环链表

【数据结构初阶】带头双向循环链表

发布: 2023年2月14日 10:17:50

大家好我是沐曦希💕

文章目录

  • 1.前言
  • 2.带头双向循环链表的实现
    • 2.1 List.h
    • 2.2 test.c
    • 2.3 List.c
  • 3.顺序表和链表的区别
  • 4.写在最后

1.前言

在这里插入图片描述
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了,可以通过对比无头单向链表实现代码进行对比。

2.带头双向循环链表的实现

2.1 List.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include
#include
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("%dn", cur->val);
	ListInsert(cur, 100);
	ListPrint(plist);
	cur = ListFind(plist, 10);
	printf("%dn", 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.写在最后

那么带头双向循环链表就到这里了。

在这里插入图片描述

相关文章