线性表总结

顺序表和链表的比较

存取方式

• 顺序表支持顺序存取和随机存取；
• 链表只能从表头顺序存取元素，支持顺序存取；

逻辑结构与物理结构

• 顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻【一定性】。
• 链式存储时，逻辑上相邻的元素，对应的物理存储位置不一定相邻【可以相邻，也可以不相邻】。
• 链式存储的逻辑关系通过指针链接表示；

时间复杂度

按值查找

• 顺序表无序的情况下，顺序表和链表的时间复杂度均为O(n)
• 顺序表有序的情况下，顺序表的时间复杂度为O(log₂n)，链表的时间复杂度为O(n)；

注意：O(log₂n) < O(n)

按序号查找

• 顺序表支持随机访问，时间复杂度为O(1)；
• 顺序表不支持随机访问，时间复杂度为O(n)；

插入、删除

• 顺序表平均需要移动半个表长的元素；
• 链表只需要修改相应结点的指针域，不需要移动元素；
• 链表结点除了数据域，还有指针域，在存储空间上比顺序存储需要更大的存储空间，付出更大的存储代价，存储密度不够大

空间分配

顺序存储

静态分配

• 需要预先分配足够大的存储空间；
• 空间装满后不能扩充，存储新元素将出现内存溢出；
• 存储空间过大，顺序表后部闲置空间过多，造成内部碎片
• 存储空间过小，会造成内存溢出

动态分配

• 动态分配能够扩充存储空间，但需要移动大量元素，操作效率降低
• 内存中没有更大块的连续存储空间，将会导致空间分配失败；

链式存储

• 链式存储的结点空间只在需要的时候申请分配
• 只要内存由空间就可以分配，操作灵活、高效

存储结构的选取

基于存储的考虑

• 对线性表的长度和存储规模难以估计时，不宜采用顺序表存储
• 链表不用事先估计存储规模，但存储密度较低
• 链式存储结构的存储密度小于1，不要求连续的存储空间

基于运算的考虑

• 顺序表支持随机存取，按序号查找顺序表的时间复杂度为O(1)；
• 链表不支持随机存取，按序号查找链表的时间复杂度为O(n);
• 顺序表的插入、删除操作，平均需要移动表中一半的元素，当表的数据量较大时，这种情况需要重点考虑的。
• 链表的插入、删除操作，也是需要找插入位置（前驱结点、后继结点），主要的操作还是比较操作，相对较好；

基于环境的考虑

• 顺序表容易实现，任何高级语言中都有数组类型；
• 链表操作是基于指针的，指针移动，相对复杂；

综上比较

• 通常比较稳定的线性表选择顺序存储；
• 频繁进行插入、删除操作的线性表，应该选择链式存储，动态性较强

知识补充

• 无论是链表的插入还是删除操作，必须保证不断链【重要】
• 顺序存储结构可以随机存取也能顺序存取，链式结构只能进行顺序存取
• 顺序存储方式同样适合图和树的存储，例如：满二叉树的顺序存储
• 队列需要在表头删除元素，在表尾插入元素【先进先出】，采用带尾指针的循环单链表比较方便
• 数组排序最少时间复杂度为O(nlog₂n)【重要】
• 静态链表中的指针称为游标，指示下一个元素在数组中的下标
• 静态链表用数组表示，需要预先分配较大的连续空间，同时具有一般链表的特点（插入、删除元素不需要移动元素）

单链表设置头结点

目的

主要是方便运算。

好处

• 有头结点后，插入、删除数据元素的算法统一起来了，不需要判断是否在第一个元素之前插入或者删除第一个元素了。
• 不论链表是否为空，头指针是指向头结点的非空指针，链表的头指针不变，因此空链表和非空链表的处理也就统一起来了。