线性表学习终章–顺序表与链表的最终对决！

逻辑结构

都属于线性表，都是线性结构🙋‍♂️

物理结构

顺序表(顺序存储)

优点:支持随机存取、存储密度高👍
缺点:大片连续空间分配不方便，改变容量不方便👎

链表(链式存储)

优点:离散的小空间分配方便，改变容量方便👍
缺点:不可随机存取，存储密度低👎

数据的运算\基本操作

创建

顺序表👎

需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量;若分配空间
过大，则浪费内存资源。

静态分配:静态数组

容量不可改变
动态分配:动态数组

容量可改变，但需要移动大量元素，时间代价高

链表👍

只需分配一个头结点(也可以不要头结点，只声明一个头指针)，之后方便拓展。

销毁

顺序表👎

修改Length = 0

静态分配:静态数组->系统自动回收空间
动态分配:动态数组->需要手动free

malloc函数申请的空间为堆区，系统不会自动回收

链表👍

依次删除各个结点(free)

增删

顺序表👎

插入/删除元素要将后续元素都后移/前移

时间复杂度0(n),时间开销主要来自移动元素

若数据元素很大，则移动的时间代价很高

链表👍

插入/删除元素只需修改指针即可

时间复杂度0(n)，时间开销主要来自查找目标元素

查找元素的时间代价更低

查找

顺序表👍

按位查找: 0(1)

按值查找: 0(n)若表内元素有序，可在O(logn)(以2为底)时间内找到

链表👎

按位查找: O(n)

按值查找: O(n)

小结

线性表·完🎊