【2.4】顺序表和链表的比较

顺序表的主要优点

• 没有使用指针，不用花费额外开销
• 线性表元素的读访问非常简洁便利

链表的主要优点

• 无需事先了解线性表的长度
• 允许线性表的长度动态变化
• 能够适应经常插入删除内部元素的情况

总结

• 顺序表是存储静态数据的不二选择
• 链表是存储动态变化数据的良方

一、顺序表和链表的比较

顺序表

• 插入、删除运算时间代价 O(n)，查找则可常数时间完成
• 预先申请固定长度的连续空间
• 如果整个数组元素很满，则没有结构性存储开销

链表

• 插入、删除运算时间代价 O(1)，但找第i个元素运算时间 代价 O(n)
• 存储利用指针，动态地按照需要为表中新的元素分配存 储空间
• 每个元素都有结构性存储开销

二、顺序表和链表存储密度

• n 表示线性表中当前元素的数目，
• P 表示指针的存储单元大小(通常为 4 bytes)
• E 表示数据元素的存储单元大小
• D 表示可以在数组中存储的线性表元素的最大数目

空间需求：

• 顺序表的空间需求为 DE
• 链表的空间需求为 n(P + E)

n 的临界值，即 n > DE / (P+E)

• n 越大，顺序表的空间效率就更高
• 如果P = E，则临界值为 n = D / 2

三、应用场合的选择

顺序表不适用的场合：

• 经常插入删除时，不宜使用顺序表
• 线性表的最大长度也是一个重要因素

链表不适用的场合：

• 当读操作比插入删除操作频率大时，不应选择链表
• 当指针的存储开销，和整个结点内容所占空间相比其 比例较大时，应该慎重选择

四、顺序表和链表的选择

顺序表：

• 结点总数目大概可以估计
• 线性表中结点比较稳定(插入删除少)
• n > DE / (P + E)

链表：

• 结点数目无法预知
• 线性表中结点动态变化(插入删除多)
• n < DE / (P + E)

五、思考

5.1 顺序表和链表的选择?

• 结点变化的动态性
• 存储密度

5.2 一元多项式的表达

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾