(14)王道数据结构-顺序表和链表比较

逻辑结构

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

存储结构

相同点：
都属于线性表，都是线性结构

顺序表

优点：

支持随机存取、存储密度高

缺点：

大片连续空间分配不方便，改变容量不方便

链表

优点：

离散的小空间分配方便，改变容量方便

缺点

不可随机存取，存储密度低

基本操作

创建

顺序表

需要预先分配大片连续空间，分配空间过小不好扩展，过大浪费空间。容量不可改变

链表

只需要分配一个头结点（或头指针）之后方便扩展。容量可以改变，但需要移动大量元素，时间代价高

销毁

顺序表

修改lengh=0，使用静态数组系统自动回收空间。

链表

依次删除各个节点（free）使用的是动态数组。需要特别注意的是malloc和free必须成对出现，使用的是stdllib包

增删

顺序表

插入/删除元素要将后续元素都后移/前移，时间复杂度O(n),时间开销主要来自移动元素。如果数据元素很大，则移动的时间代价很高

链表

插入/删除元素只需要修改指针即可，时间复杂度O(n)，时间开销主要来自查找目标元素。查找元素的时间代价更低

查找

顺序表

按位查找：O(1)
按值查找：O(n)，若表内元素有序，可在O(log2n)时间内找到

链表

按位查找：O(n)
按值查找：O(n)

选择

表长难以预估、经常需要增加/删除元素选择链表
表长可以预估、查询（搜索）操作较多选择顺序表