【数据结构】之 线性表详解(8)

?

?

顺序表和链表的比较总结

在数据结构绪论中就有提及算法的性能评价，既要从时间方面考虑（时间复杂度），又要从空间方面考虑（空间复杂度）。线性表在物理结构上的存储造成了顺序表和链表性能上的差异：顺序表使用一组连续的物理地址存储（逻辑上通常为数组，能够随机存取），而链表的物理存储地址是任意的（不能随机存取）。如此一来，线性表的基本操作会受到影响。

基于时间

适合顺序表的情况：因为顺序表通常是用数组表示决定了顺序表能够随机存储，所以当线性表的操作主要是进行查找而很少做插入和删除操作时应用顺序表。

适合链表的情况：与顺序表的情况想反，需要频繁的进行插入或删除操作的线性表应用链表。

?

基于空间

存储密度，是指结点数据本身所占的存储量和整个结点结构所占的存储量之比。

由前面提到顺序表和链表的物理存储地址可知：顺序表是静态分配的，链表是动态分配。静态分配的一个缺点就只，分配时空间有多大就是多大，存储规模是确定的，若数据元素无法用完静态分配的空间，就会造成浪费，存储密度小，空间利用率低。而动态分配则不会有这种情况。

因此，当线性表的长度变化不大，易于事先确定其存储规模时宜采用顺序表，反之应采用链表。

?

线性表链式存储方式比较

（编辑：ASP站长网）