线性表第一波总结

作者: 喜忧参半 | 来源:发表于2021-08-31 16:51 被阅读0次

顺序表

顺序表最主要的特点是随机访问，通过首地址和元素序号可在时间复杂度为O(1)内找到指定元素。(优点)
顺序表的存储密度高，每个结点只存储数据元素(顺序存储结构的优点)。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。（缺点）

顺序表插入、删除的时间复杂度

最好情况：在表尾插入(删除)，元素不需要后移，时间复杂度O(1)。
最坏情况：在表头插入(删除)，元素全部后移，有n个元素，时间复杂度O(n)。
平均情况：设第i个位置上插入(删除)的概率为P_i，那么满足均匀分布。
$\sum_{i=1}^{n+1}p_i(n-i+1)={1 \over n+1}·{n(n+1) \over 2}={n \over 2}→O(n)$ 因此平均情况下，线性表插入(删除)算法的平均时间复杂度是O(n)，同理删除也是如此。

按值查找(顺序查找)

最好情况：查找的元素就在表头，仅匹配一次，时间复杂度为O(1)。
最坏情况：查找的元素在表尾(或不存在)时,需要匹配n次，时间复杂度为O(n)。
平均情况：设查找的元素在第i个位置上，那么满足均匀分布。
$\sum_{i=1}^{n+1}p_i×i={1 \over n}·{n(n+1) \over 2}={n+1 \over 2}→O(n)$ 因此平均情况下，线性表按值查找算法的平均时间复杂度是O(n)。

小结：
顺序表是一种支持随机存取的存储结构，可以很方便的随机访问任意一个元素。
顺序存储需要连续的存储空间，当n个空间已满时，再申请增加m个空间的实现原理是：
增加申请时需要申请n+m个连续的存储空间，然后将表中原有的n个元素复制到新申请的n+m个连续的存储空间中。

单链表

链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理上也相邻，它通过"链(指针)"建立起数据之间的逻辑关系，因此插入和删除时不需要移动元素，只需要修改指针。但也失去了顺序表可随机存取的优点。

头插法与尾插法

采用头插法建立单链表时，读入数据的顺序与生成的链表中元素的顺序是相反的。每个结点插入的时间是O(1)，设链表长度为n，因此总时间复杂度为O(n)。

按序查找与按值查找

由于单链表不可随机存取，因此单链表查找元素，需要从头结点出发，依次往下寻找。按值查找和按序查找的时间复杂度均为O(n)。

链表的插入、删除操作

已知链表在插入和删除时，不需要移动元素，因此操作的时间复杂度都为O(1),但是插入和删除的位置需要通过遍历找到，因此插入、删除算法的时间开销都用在了查找操作上，因此插入、删除算法的时间复杂度为O(n)。
若在给定的结点后插入或删除，则时间复杂度仅为O(1)。

小结：单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点(插入、删除操作时)，只能从头开始遍历，访问后继结点的时间复杂度为O(1),访问前驱结点的时间复杂度为O(n)。
在单链表中，添加一个头结点是为了方便运算的实现。

双链表

双链表在单链表的结点中添加了一个指向其前驱的prior指针，因此双链表中的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上，与单链表有较大不同。
由于在"链"变化时也需要对prior指针做出修改，其关键是保证在修改的过程中，不断链。此外，双链表可以很方便地找到其前驱结点，因此，双链表插入、删除操作的时间复杂度仅为O(1)。

双链表插入操作的顺序（先学后做）

顺序其实就是先从将对方的指针作为自己的指针，自己再指出去。

循环链表

循环单链表的插入、删除算法与单链表是一样的，不同的是如果操作在表尾进行，则执行的操作不同，以让单链表继续保持循环的性质。因为循环单链表是一个“环”，因此在任何位置上的插入和删除操作都是相同的，无需判断是否在表尾。

单链表只能从表头开始往后遍历整个链表，而循环链表可以从表中的任意一个结点开始遍历整个链表。
有时对单链表常做的操作是在表头和表尾进行的，此时对循环单链表不设头指针而仅设尾指针，从而使得操作效率更高。
原因在于：若设的是头指针，对表尾进行操作需要O(n)的时间复杂度，而尾指针的下一个指针即是头指针，对表头和表尾进行操作都只需要O(1)的时间复杂度。

循环双链表

循环双链表中，不同于循环单链表的是，头结点的prior指针还要指向表尾结点。
在循环双链表L中，某结点*p为尾结点时，p->next==L,当循环双链表为空表时，其头结点的prior域和next域都等于L。

静态链表

静态链表是借助数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，但这里的指针是结点的相对地址(数组下标)，又称为游标。由于静态链表采用数组来描述链式结构，因此也需要预先分配一块连续的内存空间。

顺序表与链表的区别

顺序表	链表
可随机存取，也可顺序存取	顺序存取
逻辑上相邻的元素，物理存储位置也相邻	逻辑上相邻的元素，物理存储不一定相邻
无序时,按值查找复杂度O(n),有序时,折半查找复杂度O(log₂ⁿ)	有序、无序都是O(n)
插入、删除操作需要移动表的元素	插入、删除只需要修改相关结点的指针
需要预先分配合适的存储空间	无需预先分配，内存有空间即可

基于存储的考虑

顺序表的存储空间是静态分配的，必须需先分配合适的大小，过大造成浪费，过小造成溢出。可见对线性表的长度或存储规模难以估计时，不宜采用顺序表；
链表不用事先估计存储大小，但链表的存储密度较低（存储密度是指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比，显然链式存储结构的存储密度是小于１的）。
因此，从空间利用率的角度上看，顺序表的空间利用率显然要比链表高。

基于运算的考虑

在顺序表中按序号访问 a[i] 的时间性能是O(1)，而链表中按序号访问的时间性能是O(n)，所以如果经常做的运算是按序号访问数据元素，显然顺序表优于链表；
在顺序表中做插入、删除时平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的；在链表中作插入、删除，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然，显然链表优于顺序表。

基于环境的考虑

顺序表容易实现，任何高级语言中都有数组类型。
链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。

基于空间利用率

从空间利用率的角度上看，顺序表的空间利用率显然要比链表高。
这是因为，链表在存储数据时，每次只申请一个节点的空间，且空间的位置是随机的。
这种申请存储空间的方式会产生很多空间碎片，一定程度上造成了空间浪费。
不仅如此，由于链表中每个数据元素都必须携带至少一个指针，因此，链表对所申请空间的利用率也没有顺序表高。