请选择 进入手机版 | 继续访问电脑版

顺序表和链表的区别和联系

[复制链接]
时间苍白了等待 发表于 2021-1-3 11:57:22 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
文章目次



1.线性表

在先容顺序表和链表之前,先先容一下线性表;
线性表是N个具有相同特性的数据元素的有限序列。线性表是一种常见的数据布局,常见的有顺序表,链表,栈,队列,字符串等等…
线性表顾名思义是一种一连的直线布局,但是这种线性布局只是在逻辑上。在物理布局上不一定是线性布局。在物理存储上通常以数组和链式布局举行存储;
2.顺序表

顺序表是用一段物理所在一连的存储单元,依次举行元素存储的线性布局,通常用数组存储;
即顺序表在本质上面就是数组;
顺序表可以分为两种:
一种为使用固定命组举行存储,别的一种是使用动态开辟的数组举行存储;
顺序表的优点:
1.尾插尾删时间复杂度为O(1);
2.可以随机访问;
3.缓存掷中率较高(相对于链式),物理空间一连,预加载有优势;

顺序表缺点:
1.中间和头部的插入和删除的时间复杂度为O(N);
2.增容需要增长空间,就会需要拷贝数据,会产生消耗;
3.空间的浪费:扩容一般以两倍的速度扩容,这是因为不会因为扩容太小而频仍扩容,也不至于太大浪费太多空间,但是在整体上来说照旧会有一定的空间浪费;
3.链表

链表是一种物理存储布局上非一连、非顺序的存储布局,数据元素的逻辑顺序是通过链表的指针链接序次实现的;
链表的产生是为了增补顺序表的不敷,但是不能替代顺序表,每种布局都有自己的优势和不敷,出现一种互补的状态;
链表的布局多达8种,由下列所述情况分列组合而成:
1.单向,双向;
2.带头,不带头;
3.循环,非循环;
常用的有两种范例:
1.不带头不循环的单向链表:
布局简朴,不会单独用来存储数据,更多是应用于OJ题中,作为数据布局的子布局,如哈希表,图等等…
2.双向带头循环链表:
布局虽然复杂,应用简朴,非常方便,大多作为链表布局使用,STL中就是这种布局;
4.总结——顺序表和链表的区别和接洽

4.1顺序表的优缺点

顺序表的优点:
1.布局简朴,尾插尾删时间复杂度为O(1);
2.可以随机访问;
3.缓存掷中率较高(相对于链式),物理空间一连,预加载有优势;
顺序表缺点:
1.中间和头部的插入和删除的时间复杂度为O(N);
2.增容需要增长空间,就会需要拷贝数据,会产生消耗;
3.空间的浪费:扩容一般以两倍的速度扩容,这是因为不会因为扩容太小而频仍扩容,也不至于太大浪费太多空间,但是在整体上来说照旧会有一定的空间浪费;
适用场景:
适合频仍访问的场景;
4.2链表的优缺点

链表的优点:
1.不会造成空间浪费,用一个节点开辟一个节点;
2.双向链表在任意位置的插入删除都是O(1);
链表的缺点:
1.以节点为存储单元,不支持随机访问;
2.非一连布局,布局较为复杂;
3.缓存掷中率低,而且容易造成内存碎片;
适用场景:
频仍插入删除的场景;
5.实战运用

5.1顺序表的运用(附博客链接点击进入)

1.动态增长空间的通讯录
2.固定巨细的通讯录
3.旋转数组的四种解法
5.2链表的运用

1.双向循环链表的增删查减
2.单链表奇偶节点分离组合
3.链表节点删除的一些细节
4.反转链表
5.环形链表
6.对链表插入排序
7.链表的递归

来源:https://blog.csdn.net/ych9527/article/details/112004414
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )