K：顺序表和链表的比较
2024-10-07 23:14:07
顺序表和链表是线性表的两种基本实现形式（链表还有多种变化形式），对于这两种实现方式，没有一种方法可以称是最好的，他们各自有着各自的特点和优缺点，适用于不同的应用场景。
与顺序表相比，链表较为灵活，它既不要求在预先分配的一块连续的存储空间中存储线性表的所有数据元素，也不要求按其逻辑顺序来分配存储单元，可根据需要进行存储空间的动态分配。因此，当线性表的长度变化较大或长度难以估计时，宜用链表。但在线性表的长度基本可以预计且变化较小的情况下，宜用顺序表，因为链表的存储密度较顺序表的低，且顺序表具有随机存取的优势。
在顺序表中按序号访问第i个数据元素时的时间复杂度为O(1),而在链表中做同样操作的时间复杂度为O(n)。所以，若要经常对线性表按序号范文数据元素时，顺序表要优先于链表；但在顺序表上做插入和删除操作时，需要平均移动一般的数据元素，而在链表上做插入和删除操作时，不需要移动任何数据元素，虽然要查找插入或删除数据元素的位置，但由于主要是比较操作，所以总体而言，链表要优先于顺序表。
总之，链表比较灵活，插入和删除操作的效率较高，但链表的空间利用率较低，适用于实现动态的线性表；顺序表实现比较简单，因为在任何高级程序语言中都有数组类型，并且空间利用率也较高，可高效的进行随机存取，但顺序表不易扩充，插入和删除操作的效率较低，适合于实现相对“稳定”的静态线性表。
最新文章
- 问题解决——CVSListBox的使用
- Dom中的继承关系
- 示例篇-购物车的简单示例和自定义JS
- C++常见gcc编译链接错误解决方法
- 【转载】Linux系统，设置Oracle开机启动，待整理
- Go语言并发与并行学习笔记(一)
- Add Two Numbers ---- LeetCode 002
- iphone dev 入门实例5:Get the User Location & Address in iPhone App
- 数据分析≠Hadoop+NoSQL，不妨先看完善现有技术的10条捷径(分享)
- PHP PDO函数库具体解释
- 第六讲 smart qq C#开发总结
- Android ANR的产生与分析
- VC编译连接选项详解
- applicationContext.xml的文件位置就可以有两种默认实现
- Buildroot make网卡interfaces文件被修改
- java selenium webdriver第四讲 应用小结
- Ubuntu18.04安装thunderbird并设置中文
- SystemVerilog中枚举类型注意事项
- Android耗时操作
- Error C1189: #error： Please use the /MD switch for _AFXDLL builds（转）