顺序表和链表的对比

round1 逻辑结构

都属于线性表，都是线性结构

round2 存储结构

顺序表：顺序存储
优点：支持随机存储，存储密度高（没有存储冗余数据）
缺点：大片连续空间分配不方便，改变容量不方便
链式表：链式存储
优点：离散的小空间分配方便，改变容量方便
缺点：不支持随机存储，存储密度低（每个结点都存储了指向结点的指针）

round3 基本操作（创、销、增、删、改、查）

创：

顺序表（顺序存储）：
需要预分配大片连续空间。若分配空间过小，则之后不方便扩展容量；若分配过大空间过大，则浪费内存资源。
链表（链式存储）[win]：
只需分配一个头节点（也可以不要头节点，只声明一个头指针），之后方便拓展。
*静态分配：静态数组，容量不可以改变
*动态分配：动态数组（malloc-free，new-delete）容量可以改变，但是需要移动大量元素，时间代价高

销：

顺序表：
静态分配：静态数组，系统自动回收
动态分配：动态数组（malloc-free，new-delete），手动释放(free、delete),系统不会自动回收,
链表：
依次删除各个结点（free、delete）

增（插入）、删：

顺序表：
插入/删除元素要将后续元素都后移/前移。时间复杂度为O(n)，时间开销主要来自数据的移动，若数据很大，则移动的时间代价很高。
链表[win]：
插入\删除元素只需要修改指针即可。时间复杂度为O(n),时间开销主要来自查找目标元素。相较于移动元素，查找元素的时间复杂度更低。

查：

顺序表{win]：
按位查找：O(1)
按值查找：若无需O(n）,若有序O(log2n)
链表：
按位查找：O(n)
按值查找；O(n)

总结：