顺序与链表综合比较

顺序表和链表这两种存储表示方法各有优缺点。在实际应用中究竟选用哪一种存储结构呢？这要根据具体的要求和性质决定。 顺序表和链表的比较

1．基于空间的考虑

顺序表的存储空间是静态分配的，在程序执行之前必须明确规定它的存储规模。若线性表的长度n变化较大，则存储规模难于预先确定。估计过大将造成空间浪费，估计太小又将使空间溢出的机会增多。在静态链表中，初始存储池虽然也是静态分配的，但若同时存在若干个结点类型相同的链表，则它们可以共享空间，使各链表之间能够相互调节余缺，减少溢出机会。动态链表的存储空间是动态分配的，只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，采用动态链表作为存储结构较好。

存储密度(Storage Density)是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即：存储密度=结点数据本身所占的存储量/结点结构所占的存储总量链表中的每个结点，除了数据域外，还要额外设置指针（或游标）域，从存储密度来讲，这是不经济的。

一般地，存储密度越大，存储空间的利用率就高。显然，顺序表的存储密度为1，而链表的存储密度小于1。例如单链表的结点的数据均为整数，指针所占空间和整型量相同，则单链表的存储密度为50%。因此若不考虑顺序表中的备用结点空间，则顺序表的存储空间利用率为100%，而单链表的存储空间利用率为50%。由此可知，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。

2．基于时间的考虑

顺序表是由向量实现的，它是一种随机存取结构，对表中任一结点都可以在O (1) 时间内直接地存取，而链表中的结点，需从头指针起顺着链找才能取得。因此，若线性表的操作主要是进行查找，很少做插入和删除时，宜采用顺序表做存储结构。

在链表中的任何位置上进行插入和删除，都只需要修改指针。而在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。因此，对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。

3．基于语言的考虑

在没有提供指针类型的高级语言环镜中，若要采用链表结构，则可以使用光标实现的静态链表。虽然静态链表在存储分配上有不足之处，但它是和动态链表一样，具有插入和删除方便的特点。

值得指出的是，即使是对那些具有指针类型的语言，静态链表也有其用武之地。特别是当线性表的长度不变，仅需改变结点之间的相对关系时，静态链表比动态链表可能更方便。

线性表链式存储方式的比较

操作名称 操 作链名表 名链表名称 称带头结点单链表L 找表头结点 称找表尾结点 找P结点前驱结点 L->next 时间耗费O(1) L->next 时间耗费O(1) R->next O(1) L->next O(1) 带头结点循环单链表（头指针）L 带尾指针的循环单链表R 带头结点双向循环链表L

顺P结点的next一重循环 域无法找到P结点时间耗费O(n) 的前驱 顺P结点的next一重循环 域可以找到P结点时间耗费O(n) 的前驱 时间耗费O(n) 顺P结点的nextR 域可以找到P结点时间耗费O(1) 的前驱 时间耗费O(n) L->prior P->prior 时间耗费O(1) 时间耗费O(1)