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

经典面试题之顺序表和链表的优缺点

[复制链接]
云韵 发表于 2021-1-2 12:12:41 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
1.什么是顺序表?

顺序表是用一段物理地点一连的存储单元依次存储数据元素的线性结构,一般情况下接纳数组存储。在数组上完成数据的增删查改,而且插入时可以动态增长。

2、什么是链表?

链表是一种物理存储结构上非一连、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链
接序次实现的 。每个结点的构成:数据域 + 指针域(结构体指针)。
实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:

  • 单向、双向
  • 带头、不带头
  • 循环、非循环

①顺序表的优缺点:

优点:
  (1).空间一连。
(2).缓存使用率较高(相对于链式),物理空间一连,预加载有优势
(3).支持随机访问。
缺点
  (1).大概存在一定的空间浪费:一般扩容是以两倍扩容
(2).增容有一些效率损失
(3).中间大概头部的插入删除需要遍历整个顺序表,时间复杂度为O(n).
②链表的优缺点

优点:
  (1).不存在空间浪费,用就申请不消就不申请。
(2).任意位置的插入删除的效率高
缺点
  (1).缓存使用率低,而且容易造成内存碎片
(2).不能随机访问

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

使用道具 举报

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

本版积分规则


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

18768367769

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

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

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