2.6.3　链式存储结构与顺序存储结构的优缺点

下面简单对单链表存储结构和顺序存储结构进行对比。

1．存储分配方式

顺序存储结构用一组连续的存储单元依次存储线性表的数据元素。单链表采用链式存储结构，用一组任意的存储单元存放线性表的数据元素。

2．时间性能

采用顺序存储结构时，查找操作时间复杂度为O（1），插入和删除操作需要移动平均一半的数据元素，时间复杂度为O（n）。采用单链表存储结构时，查找操作时间复杂度为O（n），插入和删除操作不需要大量移动元素，时间复杂度仅为O（1）。

3．空间性能

采用顺序存储结构时，需要预先分配存储空间，分配的空间过大会造成浪费，分配的空间过小不能满足问题需要。采用单链表存储结构时，可根据需要临时分配，不需要估计问题的规模大小，只要内存够就可以分配；其还可以用于一些特殊情况，如一元多项式的表示。