第四节　顺序表和链表的比较

一、顺序表的优缺点

优点：① 空间利用率高。 ② 可以实现随机存取。

缺点：① 插入、删除操作中要大量移动结点，时间性能差。

　　　② 需要事先确定顺序表的大小，估计小了会发生溢出现象，估计大了又将造成空间的浪费。

二、链表的优缺点

优点：① 插入、删除操作中无需移动结点，时间性能好。

　　　② 因为是动态分配存储空间，所以只要有空闲空间就不会发生溢出现象。

缺点：因为每个结点都要额外设置指针域，因此空间利用率低。

三、顺序表和链表比较

通过上述比较，可以看出算法的时间性能与空间性能往往是一对矛盾，时间性能的改善要以牺牲空间性能为代价，反之亦然。因此在实际中，要根据具体情况来确定采用哪种存储结构。

①对线性表的操作是经常性的查找运算，以顺序表形式存储为宜。因为顺序存储可以随机访问任一结点，访问每个结点的复杂度均为O (1)。而链式存储结构必须从表头开始沿链逐一访问各结点，其时间复杂度为O (n)。

②如果经常进行的运算是插入和删除运算，以链式存储结构为宜。因为顺序表作插入和删除操作需要移动大量结点，而链式结构只需要修改相应的指针。

③对于线性表结点的存储密度问题，也是选择存储结构的一个重要依据。所谓存储密度就是结点空间的利用率。它的计算公式为

存储密度=(结点数据域所占空间)／(整个结点所占空间)

结点存储密度越大，存储空间的利用率就越高。

真题选解

本章小结

本章着重介绍了线性表在顺序存储结构和链式存储结构上各种运算实现的算法，并给出了算法的时间复杂度的分析。

本章是整个数据结构的基础，也是考试的重点内容，尤其考试大纲要求：利用顺序表和链表设计算法解决应用问题，要求达到"综合应用"层次。大多数情况下，试题的最后一道算法设计题目是线性表链式存储结构的有关运算。