下载掌阅APP，畅读海量书库
立即打开
前面介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。表2-1列出了用这两种存储方式实现线性表的优缺点。
表2-1 顺序表和链表的比较
在实际中怎样选取存储结构呢？通常有以下几方面考虑。
（1）基于存储的考虑
顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模。也就是说，事先对“MAXSIZE”要有合适的设定，过大造成浪费，过小造成溢出。可见，对线性表的长度或存储规模难以估计时，不宜采用顺序表。链表不用事先估计存储规模，但链表的存储密度较低。存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然，链式存储结构的存储密度是小于1的。
（2）基于运算的考虑
在顺序表中按序号访问a i 的时间复杂度为O（1），而在链表中按序号访问a i 的时间复杂度为O（n）。所以，如果经常做的运算是按序号访问数据元素，显然顺序表优于链表。而在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应被忽视的。在链表中做插入和删除，虽然也要找插入位置，但主要是比较操作，从这个角度考虑显然链表优于顺序表。
（3）基于环境的考虑
顺序表容易实现，任何高级语言中都有数组类型，而链表的操作是基于位置的，相对来讲，前者简单些，这也是用户考虑的一个因素。
总之，两种存储结构各有长短，选择哪一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁进行插入和删除等“动态性”较强的线性表宜选择链式存储。