顺序表与链式表的比较

一、顺序表与链式表的优缺点

线性表的两种存储结构:顺序表与链式表,它们各有优缺点。

顺序表的优点如下:

  1. 方法简单,各种高级语言中都有数组,容易实现。
  2. 不用为表示结点之间的逻辑关系而采用额外的存储空间。
  3. 可以按元素序号随机访问表中结点。

有两个缺点:

  1. 在顺序表中做插入、删除操作时,平均需要移动一半的元素。对于比较大的表来说,效率比较慢。
  2. 需要预先估计合适的存储空间,过大可能造成浪费,过小又会造成溢出。

链式表的优缺点刚好与顺序表相反。

二、选择何种存储结构

(一)基于存储考虑

如果存储规模比较难以估计,那么选择链式表;如果对存储密度要求较高,选择顺序表。

所谓存储密度,是指一个结点中,数据元素所占空间与结点整体所占空间的比率。

(二)基于运算考虑

如果按序号查找运算比较多,可以选择顺序表,因为顺序表查找运算的时间复杂度为O(1),而链式表的查找时间为O(n)。

如果插入、删除运算比较多,可以选择链式表。对于大规模的顺序表来说,插入、删除操作平均需要表中的一半的元素;而链式表虽然也查找位置,但主要是比较操作。

(三)基于环境考虑

顺序表较容易实现,任何高级语言都有数组类型;而链式表稍微就麻烦一些。


总之,选择何种存储结构要具体问题具体分析。一般情况下,对于比较稳定的线性表,可以选择顺序存储结构;而动态性较高,需要频繁插入、删除的线性表可以选择链式存储结构。

用户头像
登录后发表评论