数据结构-----顺序表vs链表

📎个人主页：我的主页
📎小白一枚，欢迎指教👏

---

• 逻辑结构：都属于线性表，都是线性结构，数据元素之间存在着一对一的关系。
• 存储结构：1. 顺序表（顺序存储），只要知道其实地址，就可以知道第i个元素的存储位置，顺序表拥有随机存取的特性。 优点：支持随机存取、存储密度高；缺点：大片连续空间分配不方便，改变容量不方便。

2. 链表（链式存储），各个结点可以离散的分布在各个空间当中，添加结点的时候只需要用malloc函数动态申请一小片空间即可。各个结点的存储空间不要求连续，所以改变容量也方便。但是查找时只能从第一个头结点依次查找。 优点：离散的小空间分配方便，改变容量方便；缺点：不可随机存取，存储密度低。

(顺序存储时，逻辑上相邻的元素，对应的物理位置也相邻，链式存储时，逻辑上相邻的元素，物理上不一定相邻)

---

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

1、创：

• 顺序表：需要分配大片连续的空间，若分配的空间过小，则之后不方便拓展容量，若分配的空间过大，则浪费资源；
• 链表：只需要分配一个头结点（也可以以不要头结点，只声明一个头指针），之后方便拓展。

2、销：

（注意动态分配一定要手动free）

3、增，删：

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

4、查找：

---

二、如何选择