单链表结构与顺序存储结构优缺点

简单地对单链表结构和顺序存储结构做对比:

单链表顺序表
存储分配方式采用链式存储结构,用一组任意地存储单元存放线性表地元素用一段连续地存储单元以此存储线性表地数据元素
时间性能查找的时间复杂度O(n),插入和删除时间为O(1)查找的时间复杂度O(1),插入删除平均需要移动表长一半的元素,时间为O(n)
空间性能不需要预先分配存储空间,元素个数不受限制需要预先分配存储空间,分大了浪费,分小了易发生上溢
通过上面的对比可以发现:

若线性表需要频繁查找,很少进行插入和删除时,宜采用顺序存储结构。
若需要频繁插入和删除时,宜采用单链表结构。

如在游戏开发中,对于用户注册的个人信息,除了注册时插入数据外,绝大多数情况都是读取,所以应该考虑用顺序存储结构。
而游戏中玩家的装备或武器列表,随着玩家的游戏过程中,随时会增加或删除,单链表结构更适合这种情况。
当然,这只是简单的类比,现实的软件开发中,要考虑的问题会复杂很多。

当线性表中的元素个数变化较大或根本不知道有多大时,最好用单链表结构,这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度
,比如一年12个月,一周7天,这种用顺序存储结构效率会高很多。

总之,线性表的顺序存储结构和单链表结构各有其优缺点,不能简单的说哪个好哪个不好,需要根据实际情况,综合平衡采用哪种数据结构更能满足和达到需求和性能。

技术
©2019-2020 Toolsou All rights reserved,
程序员的520,送给女友的几行漂亮的代码(python版)基于stm32控制四轮小车电机驱动(一)linux查看磁盘空间命令实验四 自动化测试工具-软件测试axios拦截器封装与使用C语言——qsort函数opencv-python傅里叶变换以及逆变换在算法研究过程中如何进行算法创新nc的安装和简单操作C语言做一个简易的登陆验证(功能)界面