【顺序表和链表的对比】

简介: 【顺序表和链表的对比】

1.空间性能的比较

1.1存储空间的分配

1.顺序表的存储空间必须预先分配,元素个数扩充受一定限制,易造成存储空间浪费或空出现象;

2.而链表不需要为其预先分配空间,只要内存空间允许,链表中的元素个数就没有限制。

3.基于此,当线性表的长度变化较大,难以预估存储规模时,宜采用链表作为存储结构。

1.2存储密度的大小

1.链表的每个结点除了设置数据域用来存储数据元素外,还要额外设置指针域,用来存储元素之间逻辑关系的指针,从存储密度上来讲,这是不经济的。所谓存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比。

2.存储密度越大,存储空间的利用率就越高。显然,顺序表的存储密度为1,而链表的存小于1。如果每个元素数据域占据的空间较小,则指针的结构性开销就占用了整个结点的大部分空间,这样存储密度较小。例如,若单链表的结点数据均为整数,指针所占用的空间和整型量相同,则单链表的存储密度为0.5。因此,如果不考虑顺序表中的空闲区,则顺序表的存储空可100%,而单链表的存储空间利用率仅为50%。

3.基于此,当线性表的长度变化不大,易于事先确定其大小时,为了节约存储空间,宜采用顺序表作为存储结构。

2.时间性能的比较

2.1存储元素的效率

1.顺序表是由数组实现的,它是一种随机存取结构,指定任意一个位置序号 i ,都可以在 O(i)时间内直接存取该位置上的元素,即取值操作的效率高;而链表是一种顺序存取结构,按位置访问链表中第 i

个元素时,只能从表头开始依次向后遍历链表,直到找到第 i 个位置上的元素,为 O(n)即取值操作的效率低。

2.基于此,若线性表的主要操作是和元素位置紧密相关的这类取值操作,很少做插入或删除序表作为存储结构。

2.2插入和删除操作的效率

1.对于链表,在确定插人或删除的位置后,插入或删除操作无需移动数据,只需要修改指针,时间复杂度为 O (1)。而对于顺序表,进行插人或删除时,平均要移动表中近一半的结点,时间( n)。尤其是当每个结点的信息量较大时,移动结点的时间开销就相当可观。

2.基于此,对于频繁进行插人或删除操作的线性表,宜采用链表作为存储结构。

3.区别

需要注意的是我们这里比较的是带头结点的双向循环链表,而对于缓存利用率,我们则需要了解存储体系结构 以及 局部原理性,具体如下图:

对于我们数据结构而言,则是存在内存中的大家要记住!(仅需了解)

总结:到此我们对于顺序表和链表的学习便告一段落了,接下来我将会不定期的出LeetCode的题解来进行对知识的巩固!

相关文章
|
2天前
|
存储
顺序表和链表(2)
【10月更文挑战第23天】
顺序表和链表(2)
|
3天前
|
存储 算法 数据管理
顺序表和链表(1)
【10月更文挑战第22天】
|
25天前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
21 3
|
5月前
|
存储 缓存 算法
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
数据结构和算法学习记录——总结顺序表和链表(双向带头循环链表)的优缺点、CPU高速缓存命中率
46 0
|
6月前
|
存储 缓存
[数据结构]——顺序表和链表
[数据结构]——顺序表和链表(下):https://developer.aliyun.com/article/1515507
|
3月前
|
存储 算法
【初阶数据结构篇】顺序表和链表算法题
此题可以先找到中间节点,然后把后半部分逆置,最近前后两部分一一比对,如果节点的值全部相同,则即为回文。
28 0
|
3月前
|
存储 缓存
【数据结构】——顺序表与链表
【数据结构】——顺序表与链表
|
5月前
|
存储 索引
顺序表和链表
通过以上示例,我们可以看到顺序表和链表在实际应用中如何操作。顺序表适合于需要频繁读取数据的场景,而链表则更适用于频繁修改数据的情况。在选择使用哪种数据结构时,应考虑到实际应用的需求和上下文环境。
29 2
|
5月前
|
存储
2.顺序表_链表(附练习)
2.顺序表_链表(附练习)
|
5月前
|
存储 算法
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
数据结构和算法学习记录——线性表之单链表(上)-初始单链表及其尾插函数(顺序表缺陷、单链表优点、链表打印)
37 0