2.4 顺序表与链表的比较

本章前面部分介绍了线性表的两种存储结构：顺序表和链表。顺序存储有如下优点。

（1）方法简单，高级语言都提供有数组，实现容易。

（2）无须为表示线性表中元素的逻辑关系而额外增加存储开销。

（3）具有按元素序号随机访问的特点。

顺序存储的缺点如下。

（1）在顺序表中进行插入、删除操作时，需要顺序移动元素（平均移动次数是线性表长度的一半），因此对长度较长的线性表操作效率较低。

（2）要预先分配足够大的存储空间，空间分配过大会造成浪费，过小又有可能导致一些操作（如插入）失败。

顺序表的优点就是链表的缺点，而其缺点则是链表的优点。在实际使用中究竟采用什么存储结构呢？通常有如下3点考虑。

1.基于空间的考虑

顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模，也就是说对MaxSize要有合适的设定。因此，当线性表的长度变化较大，难以估计其存储规模时，不宜采用顺序表。链表无须事先估计存储规模，但链表的存储密度较低，存储密度是指结点数据本身所占的存储单元数和整个结点所占的存储单元数的比。显然，存储密度越大，存储空间的利用率就越高。顺序表的存储密度为1，而链表的存储密度小于1。在链式存储中，双向链表的存储密度又低于单链表的存储密度。

因此，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。当线性表的长度变化较大，事先难以确定其大小时，应采用链式存储结构。

2.基于时间的考虑

顺序表可实现元素的随机存取，对表中任意结点都可以在O(1)时间内直接存取，而链表中的结点，需从头指针起顺着链逐个结点移动才能存取。因此，若线性表的操作主要是进行查找，很少进行插入和删除，则采用顺序表为存储结构较好。

在顺序表中进行插入和删除，元素的平均移动次数是线性表长度的一半，当每个结点的信息量较大时，移动结点的时间开销就相当可观。而在链表中进行插入和删除，虽然也要查找插入位置，但所做的是比较操作，插入过程只需要修改指针。因此，对于频繁进行插入和删除的线性表，宜采用链表为存储结构。

3.基于语言的考虑

各种高级语言都提供有数组，但不一定提供有指针，链表是基于指针的，所以链表的使用有时会受到高级语言的限制。

总之，两种存储结构各有利弊，究竟选择哪种结构要根据实际问题的主要因素来考虑。