免费做标签格式网站,做网站用php还是python,网页设计茶叶网站建设,提供石家庄网站推广不同点#xff1a;
顺序表和链表是两种常见的数据结构#xff0c;他们的不同点在于存储方式和插入、删除操作、随机访问、cpu缓存利用率等方面。
一、存储方式不同:
顺序表#xff1a;
顺序表的存储方式是顺序存储#xff0c;在内存中申请一块连续的空间#xff0c;通…不同点
顺序表和链表是两种常见的数据结构他们的不同点在于存储方式和插入、删除操作、随机访问、cpu缓存利用率等方面。
一、存储方式不同:
顺序表
顺序表的存储方式是顺序存储在内存中申请一块连续的空间通过下标来进行存储
链表
链表的存储方式是链式存储申请的空间是未必连续的以节点的形式连接每个节点会有一个next指针指向下一个节点通过指针来访问元素
二、插入、删除的效率不同:
顺序表:
插入删除元素时需要移动元素的位置也就是搬移元素导致效率低下
链表
插入删除时只需要修改指针指向。
三、内存利用率
顺序表
需要扩容创建空间大小是固定的当空间不够时需要进行扩容以2倍的关系扩增的你少一个空间我增大到原来的2倍还会有多余空间未使用所以扩容会造成空间浪费的现象。
但是注意我们因为用的realloc扩容所以扩容本身会有消耗 由于realloc扩容的特性不确定是原地还是异地扩容这个与编译器有点关系 原地扩容扩容的空间地址与原来地址相同 异地扩容扩容的空间地址与原来地址不同将原来的数据拷贝过来还要销毁原来的空间 链表
按需申请的空间不会存在空间浪费现象利用率极高 四、随机访问
顺序表
支持用下标随机访问
链表
不支持因为空间在物理上就不是连续的next找到下一个节点在用该节点的next找一个找起来比较麻烦 五、缓存利用率
缓存CPU高速缓存 内存在带电的情况下存储当断电后未保存的数据会丢失就像我们在用画板时画了画你给电脑关机下次进去就找不到了但其速度快而硬盘可以不带电存储但是速度慢。 为啥有寄存器和三级缓存
✨✨主要是cpu的运行速度很快看不上内存日常不会去访问内存但是寄存器和三级缓存的速度还是能入下眼✨✨
我们写的代码时变量存在内存里面当你要修改变量时会将数据放到寄存器然后cpu对其接收指令进行修改 看下面代码的反汇编mov 是将 i 放到 eax寄存器中然后对寄存器的数据进行inc指令也就是加1 在讲寄存器的数据放到可i中 但是寄存器个数有限一般对于4个 8个字节会放到寄存器数据比较大会加载到缓存 缓存里面还要涉及到三级缓存的调用有点深奥不讲这么难的可以自己去查资料 cpu访问数据会先访问数据是否在缓存中在---》缓存命中直接访问。 不在---》不命中先将数据加载到缓存中再进行访问。 怎么加载到缓存的
cpu会按cpu字长去读会认为你访问当前数据后面连续在一起的都不在缓存中给它加载进去
举个例子数组为例子下面的20个人就是一个数组。度假村相当于缓存领导是cpu大巴车也是cpucpu给你加载到缓存再访问 注意缓存有一定的范围新进来的过多放不下了就给旧的清理掉 对于链表了你的物理空间是不连续拉的数据太多会把缓存区之前的一些数据排挤走了 顺序表 CPU缓存利用率高。 链表 CPU缓存利用率低。 六、总结
不同点顺序表单链表存储空间物理上一定连续底层是数组只是逻辑上连续物理上并不连续随机访问下标访问 O(1)不支持要遍历O(N)任意位置的增删需要搬运元素效率低O(N)无需搬运只需要修改指针指向插入动态顺序表需要扩容成倍扩容可能会造成空间浪费按需申请没有扩容这一说法应用场景元素的高效存储频繁的访问任意位置插入删除频繁CPU缓存利用率缓存利用率高缓存利用率低
链表和顺序表各有优势互相弥补各自的缺点 总之顺序表用于数据元素较少、读取操作频繁的场景而链表更适用于数据元素较多、插入、删除操作频繁的场景。 就到 这吧 ❤️
