带头双向循环链表的实现（C语言）

目录

一、关于带头双向循环链表的一些理解：

 二、具体实现

1.创建节点

2.打印链表

3.初始化链表

4.尾插

注意：这里不用二级指针是因为：

 5.在pos位置后插入

 6.尾删 

7.删除pos位置

8. 头删

9.头插

10.寻找节点

11.销毁

 三、顺序表与链表的区别（个人亲身经历的一道面试题）

1.链表与顺序表的区别总图

2. malloc开辟空间，内存碎片产生的原因？

3. 链表的优缺点

4. 怎么理解缓存利用率？

一、关于带头双向循环链表的一些理解：

原文链接：数据结构之带头结点的循环双向链表详细图片+文字讲解_小赵小赵福星高照～的博客-CSDN博客

不带哨兵位的头结点：
        不带哨兵位的头结点，在链表的系列操作函数中可能会修改到指向存储有效数据的第一个结点的指针plist，对在第一元素结点前插入结点和删除第一结点时，其操作与其他结点的操作不统一，我们需要在这系列操作中分别考虑不同情况。

带哨兵位的头结点：
        这个结点不存储有效数据，链表的系列操作函数永远不会修改到指向存储有效数据的第一个结点的指针plist，因为拥有这个带哨兵位的头节点，对在第一元素结点前插入结点和删除第一结点时，其操作与其他结点的操作就统一了。这个带哨兵位的头节点看起来简单一点，为什么我们的单链表不设计这个结构呢？这个头节点的结构在实际中很少出现，包括哈希桶、邻接表做子结构都是不带头，其次就是OJ中给的链表基本都是不带头的，都有先入为主思维，我们直接写带头，容易对后面的学习产生误导。
原文链接：https://blog.csdn.net/roseisbule/article/details/12371016
为什么要有哨兵位呢？

        1.对于一个已经创建和初始化的链表来讲，可以没有数据，即头节点，尾节点等，但是不能没有哨兵位，因为哨兵位并不是帮我们存储数据的，只是来定位链表的。即使是一个空链表，它也会有哨兵位，所以我们可以用哨兵位是否为空来检测程序运行情况。

        2.对于链表来讲，一个很重要的地方就是头的位置，而哨兵位则可以起到定位头的作用，它的下一个节点就是头节点。

        3.在双向循环链表中，如果我们要遍历，那么很难去说明结束条件，而我们可以用哨兵位来作为结束条件，当当前节点为哨兵位时，遍历结束。

 所以双向链表的初始化需要注意：

史上最强数据结构----双向循环链表的实现（带哨兵位）_鹿九丸的博客-CSDN博客

第一种：传二级指针的

void ListInit(ListNode** phead);//初始化函数的声明
void ListInit(ListNode** phead)//为什么要传二级指针，因为改变的是结构体的指针，所以要传结构体的指针
{
	assert(phead);
	*phead = BuyListNode(-1);//此处是开辟一个哨兵位的节点，存储的是无效数据，-1也是随便给的
	(*phead)->next = (*phead);
	(*phead)->prev = (*phead);
    //这两行代码主要是使哨兵位的next指针和prev指针自己指向自己，形成双向循环结构
}
//下面是main函数中调用初始化函数的地方，为了方便理解二级指针
int main()
{
	ListNode*phead = NULL;//初始化之后，phead就会指向哨兵位，即NULL发生了改变，即改变的是结构体的指针，所以要传二级指针
	ListNode(&phead);
	return 0;
}

 第二种：不传二级指针的

        这样之后尾插或者头插，当是空链表的时候不用传地址，因为改变的是哨兵位，即传参时，不需要传p的地址，因为函数不会改变phead的指向，因为phead永远指向哨兵位头节点，使用哨兵位头节点进行改变，所以用plist传递，用一级指针接收就行。

ListNode* ListInit(ListNode* phead);//初始化函数的声明
ListNode* ListInit()//此处为什么不传二级指针，因为在函数中会将开辟的哨兵位的地址作为返回值返回
{
	ListNode*phead = NULL;
	phead = BuyListNode(-1);//此处是开辟一个哨兵位的节点，存储的是无效数据，-1也是随便给的
	phead->next = phead;
	phead->prev = phead;
    //这两行代码主要是使哨兵位的next指针和prev指针自己指向自己，形成双向循环结构
    return phead;
}
int main()
{
	ListNode*phead = ListInit();
	return 0;
}

 二、具体实现

1.创建节点

LTNode* BuyLTNode(LTDataType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
 
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

 2. 打印链表

void ListPrint(LTNode* phead)
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n\n");
}

 3. 初始化链表

LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
 
	return phead;
}

4. 尾插

注意：这里不用二级指针是因为：

        对比一下单链表的尾插，当链表为空的时候，直接尾插，如果传入的是SList,那么SList和phead都是SListNode类型的指针，是传值传参，形参的改变不会影响实参，所以传入的是SList的地址，所以用二级指针接收，那么对改地址解引用可以得到SList本身，SList和phead都是指向第一个节点的指针，存放的是第一个节点的地址，所以*SList或者*phead得到的就是第一个节点，当链表为空，说明*phead == NULL，如果链表不为空，那么需要让phead指向第一个节点，改变了phead中存放的地址。

        而对于双向带头循环链表，其存在哨兵位，如下尾插采用的方法，如果空链表的时候，就是说phead->next == phead的时候，直接尾插，我们只需要改变phead的prev和next，比如让phead->next = newnode。改变的只是哨兵位的指向，改变的是指针本身，而单链表改变的是指针的地址，故这里不需要使用二级指针。

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
 
	tail->next = newnode;
	newnode->prev = tail;
 
	newnode->next = phead;
	phead->prev = newnode;
 
	//ListInsert(phead, x);
}

SListNode* SList = NULL;
SListPushBack(SList,i);
void SListPushBack(SListNode* phead,SLDataType x);尾插
 
 
 
void SListPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);//空指针的解引用是耍流氓
	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)//pphead接收的&SList,*pphead就是SList本身
	{
		//这就是说该链表无节点，可以直接插入
		*pphead = newnode;//现在让SList指向newnode即可插入成功
	}
	else
	{//找尾，尾插即可
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

  5.在pos位置后插入

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);
 
	LTNode* newnode = BuyLTNode(x);
	LTNode* posPrev = pos->prev;
 
	newnode->next = pos;
	pos->prev = newnode;
	posPrev->next = newnode;
	newnode->prev = posPrev;
}

6.尾删 

void ListPopBack(LTNode* phead)
{
	assert(phead);
	// 链表为空
	assert(phead->next != phead);
 
	/*	LTNode* tail = phead->prev;
	LTNode* tailPrev = tail->prev;
	free(tail);
	tail = NULL;
	tailPrev->next = phead;
	phead->prev = tailPrev;*/
 
	ListErase(phead->prev);
}

7.删除pos位置

void ListErase(LTNode* pos)
{
	assert(pos);
 
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
 
	free(pos);
	pos = NULL;
 
	prev->next = next;
	next->prev = prev;
}

8. 头删

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(phead->next != phead);
 
	ListErase(phead->next);
}

 9.头插

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}

 10.寻找节点

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);
 
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}
 
		cur = cur->next;
	}
 
	return NULL;
}

11.销毁

void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		//ListErase(cur);
		free(cur);
		cur = next;
	}
 
	free(phead);
	//phead = NULL;
}

 三、顺序表与链表的区别（个人亲身经历的一道面试题）

1.链表与顺序表的区别总图

2. malloc开辟空间，内存碎片产生的原因？

        内存碎片一般是由于空间的连续空间比要申请的空间小，导致这些小内存块无法被利用。

        比如有100个单位的连续空闲内存空间，范围0-99，如果申请10个单位空间，那么区间就是0-9，继续申请5个单元的空间，那么应该是10-14，如果我们把第一块内存释放，然后再申请10个单位的内存空间，那么倒是会继续利用0-9，但是如果申请一块大于10个单位的空间，比如20个空间，那么只能从15开始分配，15-34，此时0-9处于空闲状态，那么如果之后申请都刚刚好用不到0-9,0-9就成为了内存碎片即造成了内存浪费。

3. 链表的优缺点

        链表是一种逻辑结构上连续，物理存储结构上非连续、非顺序的存储结构，因为链表是通过指针链接次序实现的，因为创建链表时，申请的空间是随机的，所以物理上非连续。

优点：1）双向链表在任意位置插入删除都是时间复杂度为O(1)

           2）没有增容问题，插入一个开辟一个空间

缺点：1）空间不连续，不支持随机访问

          2）需要额外的空间存放指针，浪费空间

          3）因为是一小块一小块开辟的，所以形成内存碎片，造成空间利用率低

4. 怎么理解缓存利用率？

         说明：小数据用寄存器缓存，L1高速缓存保存着从L2高速缓存取出的缓存行，主存（DRAM）是带电存储，而本地磁盘（硬盘）是不带电存储。

        编译链接后，生成可执行程序，CPU执行这个程序,CPU要去访问内存：

        1）CPU不会直接访问内存，因为它嫌弃内存速度太慢，会把数据加载到三级高速缓存，或者寄存器去；

        2）4或者8byte小数据存放在寄存器缓存，大数据就到高速缓存区域；

        3）CPU看数据是否在缓存区，就叫命中，直接访问，不在就叫不命中，会先把数据从内存中加载到缓存区，再访问；（至于加载多少数据，是由硬件决定）

        所以顺序表的命中率高，因为，一开始就加载了一段，而链表加载可能会包含多个节点，也可能一个节点，也可能一个都没有，故命中率低

(1条消息) 灵魂一问：数组的查找为什么比链表快？_哲里哲里的博客-CSDN博客_数组为啥能快速定位