顺序表 链表

•存储分配方式、时间性能、空间性能

•顺序表与链表的比较

•空间比较、时间比较、语言比较

存储分配方式比较

Ø顺序表采用顺序存储结构，即用一段地址连续的存储单元依次存储线性表的数据元素，数据元素之间的逻辑关系通过存储位置来实现。

Ø单链表采用链接存储结构，即用一组任意的存储单元存放线性表的元素。用指针来反映数据元素之间的逻辑关系。

时间性能比较

时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。

按位查找：

Ø顺序表的时间为Ｏ(1)，是随机存取；

Ø单链表的时间为Ｏ(n)，是顺序存取。

插入和删除：

Ø顺序表需移动表长一半的元素，时间为Ｏ(n)；

Ø单链表不需要移动元素，在给出某个合适位置的指针后，插入和删除操作所需的时间仅为Ｏ(1)。

空间性能比较

空间性能是指某种存储结构所占用的存储空间的大小。

定义结点的存储密度：

存储密度＝数据域占用的存储量/整个结点占用的存储量

结点的存储密度：

Ø顺序表中每个结点的存储密度为1（只存储数据元素），

Ø单链表的每个结点的存储密度<1（包括数据域和指针域），有指针的结构性开销。

整体结构：

Ø顺序表需要预分配存储空间，如果预分配得过大，造成浪费，若估计得过小，又将发生上溢；

Ø单链表不需要预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。

•空间比较：

(1) 顺序表空间静态分配；链表空间动态分配

(2)顺序表的存储密度 = 1；链表的存储密度 < 1。

•时间比较：

(1)顺序表可随机存取，也可顺序存取；链表只能顺序存取

(2)插入/删除时，顺序表平均移动一半左右元素；链表不需移动元素，只修改指针。若插入/删除仅在表的两端，宜采用带尾指针的循环链表。

•语言比较：

顺序表实现简单：数组；动态链表：指针；静态链表：数组