2.4　顺序表与链表的比较

以上介绍了线性表的两种存储结构：顺序表和链表。顺序表和链表各有其优缺点，不能笼统地说哪种存储结构更好，只能根据实际问题的具体需要，并对各方面的优缺点加以综合分析比较，才能选择出符合应用需求的存储结构。以下从时间性能和空间性能两方面对顺序表和链表进行比较。

1．时间性能方面

顺序表是随机存取结构，完成按位置随机访问的运算的时间复杂度为O(1)；链表不具有随机访问的特点，按位置访问元素时只能从表头开始依次遍历链表，直至找到特定的位置，平均时间复杂度为O(n)。

对于链表，在确定插入或删除的位置后，只需修改指针即可完成插入或删除运算，所需的时间复杂度为O(1)；顺序表进行插入或删除操作时，需移动近乎表长一半的元素，平均时间复杂度为O(n)。尤其是当线性表中元素个数较多时，移动元素的时间开销相当可观。

如上所述，若线性表需频繁进行插入和删除操作，则宜采用链表做存储结构。若线性表需频繁查找却很少进行插入和删除操作或其所做运算和“数据元素在线性表中的位置”密切相关，则宜采用顺序表作为存储结构。

2．空间性能方面

顺序表需要预分配一定长度的存储空间，若存储空间预分配过大，将导致存储空间浪费；若存储空间预分配过小，将造成空间溢出问题。链表不需要预分配空间，只要有可用的内存空间分配，链表中的元素个数就没有限制。

综上所述，当线性表中元素个数变化较大或者未知时，应尽量采用链表作为存储结构；当线性表中元素个数变化不大，可事先确定线性表的大致长度时，可采用顺序表作为存储结构。