2.6顺序表和链表的比较
前面两节介绍了线性表的两种存储结构：顺序表和链表。在实际应用中，不能笼统地说哪种存储结构更好，由于它们各有优缺点，选用哪种存储结构，则应根据具体问题作具体分析，通常从空间性能和时间性能两个方面作比较分析。
2.6.1空间性能的比较
（1）存储空间的分配
顺序表的存储空间必须预先分配，元素个数扩充受一定限制，易造成存储空间浪费或空间溢出现象；而链表不需要为其预先分配空间，只要内存空间允许，链表中的元素个数就没有限制。基于此，当线性表的长度变化较大，难以预估存储规模时，宜采用链表作为存储结构。
（2）存储密度的大小
链表的每个结点除了设置数据域用来存储数据元素外，还要额外设置指针域，用来存储指示元素之间逻辑关系的指针，从存储密度上来讲，这是不经济的。所谓存储密度是指数据元素本身所占用的存储量和整个结点结构所占用的存储量之比，即
存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。如果每个元素数据域占据的空间较小，则指针的结构性开销就占用了整个结点的大部分空间，这样存储密度较小。例如，若单链表的结点数据均为整数，指针所占用的空间和整型量相同，则单链表的存储密度为0.5。因此，如果不考虑顺序表中的空闲区，则顺序表的存储空间利用率为%，而单链表的存储空间利用率仅为50%。
基于此，当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。
2.6.2时间性能的比较
（1）存取元素的效率
顺序表是由数组实现的，它是一种随机存取结构，指定任意一个位置序号i，都可以在O(1)时间内直接存取该位置上的元素，即取值操作的效率高；而链表是一种顺序存取结构，按位置访问链表中第i个元素时，只能从表头开始依次向后遍历链表，直到找到第i个位置上的元素，时间复杂度为O(n)，即取值操作的效率低。
基于此，若线性表的主要操作是和元素位置紧密相关的这类取值操作，很少做插入或删除时，宜采用顺序表作为存储结构。
（2）插入和删除操作的效率
对于链表，在确定插入或删除的位置后，插入或删除操作无需移动数据，只需要修改指针，时间复杂度为O(1)。而对于顺序表，进行插入或删除时，平均要移动表中近一半的结点，时间复杂度为O(n)。尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。
基于此，对于频繁进行插入或删除操作的线性表，宜采用链表作为存储结构。
2.7线性表的应用
2.7.1线性表的合并
求解一般集合的并集问题。
已知两个集合A和B，现要求一个新的集合A=AUB。例如，设
A=(7，5，3，11)
B=(2，6，3)
合并后
A=(7，5，3，11，2，6)
可以利用两个线性表LA和LB分别表示集合A和B（即线性表中的数据元素为集合中的成员），这样只需扩大线性表LA，将存在于LB中而不存在于LA中的数据元素插入到LA中去。只要从LB中依次取得每个数据元素，并依值在LA中进行查访，若不存在，则插入之。
上述操作过程可用算法2.15来描述。具体实现时既可采用顺序形式，也可采用链表形式。
2.15线性表的合并
①分别获取LA表长m和LB表长n。
②从LB中第1个数据元素开始，循环n次执行以下操作：
·从LB中查找第i（1≤i≤n）个数据元素赋给e；
·在LA中查找元素e，如果不存在，则将e插在表LA的最后。
上述算法的时间复杂度取决于抽象数据类型List定义中基本操作的执行时间，假设LA和LB的表长分别为m和n，循环执行n次，则：
当采用顺序存储结构时，在每次循环中，GetElem和ListInsert这两个操作的执行时间和表长无关，LocateElem的执行时间和表长m成正比，因此，算法2.15的时间复杂度为O(m×n)。
当采用链式存储结构时，在每次循环中，GetElem的执行时间和表长n成正比，而LocateElem和ListInsert这两个操作的执行时间和表长m成正比，因此，若假设m大于n，算法2.15的时间复杂度也为O(m×n)。
2.7.2有序表的合并
若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，则称该线性表为有序表（OrderedList）。
求解有序集合的并集问题。
有序集合是指集合中的元素有序排列。已知两个有序集合A和B，数据元素按值非递减有序排列，现要求一个新的集合C=AUB，使集合C中的数据元素仍按值非递减有序排列。例如，设
A=(3,5,8,11)
B=(2,6,8,9,11,15,20)
则
C=(2,3,5,6,8,8,9,11,11,15,20)
与例2.1一样，可以利用两个线性表LA和LB分别表示集合A和B，不同的是，此例中的LA和LB有序，这样便没有必要从LB中依次取得每个数据元素，到LA中进行查访。
如果LA和LB两个表长分别记为m和n，则合并后的新表LC的表长应该为m+n。由于LC中的数据元素或是LA中的元素，或是LB中的元素，因此只要先设LC为空表，然后将LA或LB中的元素逐个插入到LC中即可。为使LC中的元素按值非递减有序排列，可设两个指针pa和pb分别指向LA和LB中的某个元素，若设pa当前所指的元素为a，pb当前所指的元素为b，则当前应插入到LC中的元素c为
显然，指针pa和pb的初值分别指向两个有序表的第一个元素，在所指元素插入LC之后，在LA或LB中顺序后移。
根据上述分析，分别给出有序表的顺序存储结构和链式存储结构相应合并算法的实现。
1．顺序有序表的合并算法
2.16顺序有序表的合并
①创建一个表长为m+n的空表LC。
②指针pc初始化，指向LC的第一个元素。
③指针pa和pb初始化，分别指向LA和LB的第一个元素。
④当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
⑤如果pb已到达LB的表尾，依次将LA的剩余元素插入LC的最后。
⑥如果pa已到达LA的表尾，依次将LB的剩余元素插入LC的最后。
若对算法2.16中第一个循环语句的循环体做如下修改：分出元素比较的第三种情况，当*pa==*pb时，只将两者中之一插入LC，则该算法完成的操作和算法2.15相同，但时间复杂度却不同。在算法2.16中，由于LA和LB中元素依值非递减，则对LB中的每个元素，不需要在LA中从表头至表尾进行全程搜索。如果两个表长分别记为m和n，则算法2.16循环最多执行的总次数为m+n。所以算法的时间复杂度为O(m+n)。
此算法在归并时，需要开辟新的辅助空间，所以空间复杂度也为O(m+n)，空间复杂度较高。利用链表来实现上述归并时，不需要开辟新的存储空间，可以使空间复杂度达到最低。
2．链式有序表的合并
假设头指针为LA和LB的单链表分别为线性表LA和LB的存储结构，现要归并LA和LB得到单链表LC。因为链表结点之间的关系是通过指针指向建立起来的，所以用链表进行合并不需要另外开辟存储空间，可以直接利用原来两个表的存储空间，合并过程中只需把LA和LB两个表中的结点重新进行链接即可。
按照例2.2给出的合并思想，需设立3个指针pa、pb和pc，其中pa和pb分别指向LA和LB中当前待比较插入的结点，而pc指向LC中当前最后一个结点（LC的表头结点设为LA的表头结点）。指针的初值为：pa和pb分别指向LA和LB表中的第一个结点，pc指向空表LC中的头结点。同算法2.16一样，通过比较指针pa和pb所指向的元素的值，依次从LA或LB中“摘取”元素值较小的结点插入到LC的最后，当其中一个表变空时，只要将另一个表的剩余段链接在pc所指结点之后即可。
算法2.17链式有序表的合并
①指针pa和pb初始化，分别指向LA和LB的第一个结点。
②LC的结点取值为LA的头结点。
③指针pc初始化，指向LC的头结点。
④当指针pa和pb均未到达相应表尾时，则依次比较pa和pb所指向的元素值，从LA或LB中“摘取”元素值较小的结点插入到LC的最后。
⑤将非空表的剩余段插入到pc所指结点之后。
⑥释放LB的头结点。
可以看出，算法2.17的时间复杂度和算法2.16相同，但空间复杂度不同。在归并两个链表为一个链表时，不需要另建新表的结点空间，而只需将原来两个链表中结点之间的关系解除，重新按元素值非递减的关系将所有结点链接成一个链表即可，所以空间复杂度为O(1)。