线性表顺序存储与链式存储实现线性表的比较

时间上的比较

线性表的基本操作: 查询, 插入, 删除。

查询:

数组顺序存储,直接通过索引值访问每个元素, 实现了数组元素的随机访问。

链式存储, 每次从头结点或者尾结点开始依次查找。

如果线性表主要是查询操作, 优先选择顺序存储的线性表。

插入与删除

数组顺序实现的线性表, 在插入/删除时,需要移动大量的元素。

链式存储,只需要修改结点的前驱后续指针即可,不需要移动元素。

如果线性表经常用于插入/删除操作, 优先选择链式存储实现的线性表。

空间比较

顺序存储, 预先分配一块连续的存储空间, 在使用过程中会出现闲置的空间。

链式存储的空间是动态分配的, 不会浪费空间。

如果线性表的长度经常变化, 优先选择链式存储。

如果线性表的长度变化不大时, 优先选择顺序存储, 因为链式存储需要额外的空间存储它前驱和后继。