【数据结构】链表带环问题分析及顺序表链表对比分析

【C语言】链表带环问题分析及顺序表链表对比分析

🔥个人主页：大白的编程日记

🔥专栏：C语言学习之路

---

前言

哈喽，各位小伙伴大家好！由于考试周很久没有更新博客了。今天给大家带来的是链表的带环问题和顺序表链表的对比分析。话不多说，进入正题。向大厂冲锋！

一.顺序表和链表对比

1.1顺序表和链表的区别

顺序表和链表是两种不同的数据结构。他们各有各的优劣。我们就来对比分析一下他们的区别。我们这里用带头双向循环链表和顺序表做对比。

• 存储空间
  顺序表：物理上是连续的。
  链表：因为链表是由节点组成，每个节点由指针连接。 所以在逻辑上是连续的，但每个节点都是malloc动态开辟的，在物理空间上不一定连续。
  
• 随机访问
  顺序表：顺序表可以通过下标来进行随机访问。
  链表：链表不支持随机访问，只能从头节点开始遍历寻找节点。
  
• 任意位置插入删除
  顺序表：如果不是尾插尾删，需要挪动数据。
  链表：链表由节点组成，插入或删除只需要修改前后节点的指针指向即可。
  
• 扩容
  顺序表：空间不够需要扩容。
  扩容realloc本身会有消耗且异地扩容消耗不小，2倍扩容可能存在空间浪费。
  链表：按需申请释放，需要一个申请一个，不存在扩容，不会浪费空间。

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
int main()
{int* p = (int*)malloc(4);printf("%p\n", p);int* p1 = (int*)realloc(p, 40);printf("%p", p1);
}

异地扩容：
只要空间大一点，基本都是异地扩容。
原地扩容：

• 应用场景

顺序表和链表的优劣是互补的。
顺序表适合随机访问，不适合中间位置的插入删除。
链表适合任意位置的插入删除，但无法随机访问。
所以如果经常随机访问，但只需要尾插尾删就选择顺序表。
如果不经常随机访问，在中间位置插入删除就选择链表。
具体根据他们的优劣进行选择。

1.2缓存利用率（缓存命中率）

顺序表和链表的区别还有一个就是
顺序表的缓存命中率高。
链表的缓存命中率低。

为什么呢?什么是缓存命中率呢?

• 内存和硬盘
  

这是我们计算机的内部的存储结构。
主存也就是我们的内存和硬盘的区别就是

内存的存储空间更小，通常为8G和16G,但速度快。需要带电存储
硬盘存储空间更大，速度慢，但不需要带电存储。
他们的本质是带不带电。

例如：

如果我正在写一份ppt，因为硬盘的速度慢，所以是存在内存中的，如果我这时电脑突然没电关机。重新开机后，我的ppt就不见了。因为我没有另存到硬盘中。
只用当我们另存到硬盘中才存在。

• 寄存器和三级缓存
  那既然已经有内存，内存的速度也还行，为什么还有寄存器和三级缓存呢？

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
int main()
{int i = 0;int ret = i++;
}

以这段代码为例：

i存在内存中，也就是main函数的栈帧里。i++的执行过程是这样的：
先把i放在eax寄存器中，
对eax++,
把eax寄存器放i的内存位置

那为什么要这样做呢？
因为CPU和内存不同频，CPU跑的太快了。
如果直接访问内存数据进行++,因为内存太慢了。
他宁愿把内存中数据加载到寄存器中，CPU在寄存器执行指令，再把运行结果返回内存。

一般来说，CPU不会直接访问内存

• 寄存器
  如果数据比较小(4或8字节)就会把数据加载到寄存器。

• 缓存
  如果数据比较大就加载到缓存中。

缓存命中：如果要访问的数据在缓存，叫缓存命中，直接访问。
缓存不命中，如果要访问的数据不在缓存，叫缓存不命中，先把数据加载到缓存中，再访问。

• 缓存的加载
  如果你要加载4个字节到缓存，通常会加载一长段空间到缓存中。而不只是4个字节。为什么呢？

把内存看作学校，缓存看作大巴，CPU看作度假村。
现在学校安排大巴把学生(数据)送到度假村去。

所以顺序表的缓存命中率高，
链表的缓存命中率低，而且会造成缓存污染。
如果大家想多了解缓存的话可以看这篇文章
与程序员相关的CPU缓存知识

二.链表的带环问题

链表带环是链表中的经典问题，值得我们深入学习。解决带环问题通常使用快慢指针相遇解决。但是你如何证明快慢指针一定相遇，以及快指针的步长不同会怎样呢？接下来，小编带大家一一探讨。

2.1快慢指针

• 题目
  环形链表

• 思路
  创建一个快指针和一个慢指针，快指针一次走两步，慢指针一次走一步。
  如果是链表带环，快慢指针最终会相遇。不带环，则快指针走到尾。
• 代码实现

 typedef struct ListNode ListNode; 
bool hasCycle(struct ListNode *head) 
{ListNode*slow,*fast;slow=fast=head;while(fast&&fast->next){slow=slow->next;//慢指针走一步fast=fast->next->next;//快指针走两步if(fast==slow)//快慢指针相遇{return true;}}return false;//不带环
}

2.2证明快慢指针相遇问题

那如何证明题目一定会相遇呢？

当慢指针入环时，快指针与慢指针相差N个节点。
由于快指针每次走两步，慢指针走一步。
每次移动快指针都会与慢指针的距离缩小一个节点。
当他们的距离节点缩小为0时，就会相遇。
所以快慢指针一定能够相遇。

2.3快指针的步长

那快指针是不是只能走一步呢？如果快指针走3，4，5…N步还一定能相遇吗？

• 步长为3时
  证明结果如下
  

我们用快慢指针步长的关系列出等式，反推证明N为奇数和C为偶数的情况不会出现，从而得出结论步长为3时一定能相遇。

• 验证
  

• 步长为3，4，5…N
  这些情况和前面的推导证明过程相似，大家有兴趣可以自己深入探究。

2.4环的入口

• 题目
  环形链表二

• 思路
  创建一个快指针和一个慢指针，快指针一次走两步，慢指针一次走一步。
  如果是链表带环，快慢指针最终会相遇。
  一个指针相遇点开始走，一个指针从头节点开始走，每次两个指针都走一步。
  当两个指针相遇时，相遇节点就是入环节点。
  不带环，则快指针走到尾。

• 代码实现

 typedef struct ListNode ListNode ;
struct ListNode *detectCycle(struct ListNode *head) 
{ListNode*slow,*fast;slow=fast=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(slow==fast){ListNode* pcur=slow;while(pcur!=head){pcur=pcur->next;head=head->next;}return pcur;}}return NULL;
}

• 证明

具体证明过程如下：

• 验证
  -

所以根据推导我们得出只要再相遇后，一个head指针从头节点出发，一个pcur节点从相遇点出发，等他们相遇时，相遇点就是入环点。

后言

这就是链表的带环问题和顺序表链表的对比。这些都是我们数据结构学习时的重要内容。大家一定要好好掌握。今天就分享到这里，咱们下期见！拜拜~