数据结构与算法基础（青岛大学-王卓）

优点:

1、动态存储，可以结点动态进行申请和释放；

2、插入或删除的时候，不用移动其它结点

缺点：

1、存储密度小

2、还需要格外的存储空间来存储指针

3、不是随机存取

存储密度？假如存储本身数据需要8字节，存储下一个结点的指针需要4字节，那么存储密度就等于8/12

空间复杂度：

存储空间：顺序表<链表

存储密度：顺序表>链表

时间复杂度：

存取元素：顺序表<链表

插入和删除：顺序表>链表

适用情况!!!!

线性表的应用

• 线性表的合并：求AB的并集

算法：从B中取出每一个元素，看该元素存在于A中，如果存在就取下一个元素，如果不存在就插入到A中表尾。

• 有序表的合并：AB有序，将其合并仍未非递增/非递减序列

算法：循环两个线性表，比较两个元素，始终将较小的一个元素放入新表C，直到有一个表为空，最后将有剩余的表中元素依次假如C。

代码：

用单链表实现有序表的合并：

不需要新的单链表，直接改变指针即可。

算法！！！！

循环结束的条件：AB链表有一个为空。