【数据结构】二、线性表：6.顺序表和链表的对比不同（从数据结构三要素讨论：逻辑结构、物理结构（存储结构）、数据运算（基本操作））

6.对比：顺序表&链表

6.1逻辑结构

顺序表和链表都是线性结构。

6.2物理结构（存储结构）

6.2.1顺序表

顺序存储

优点：

1. 使用顺序存储，每个数据元素大小相同，所以可以随机访问，即可以在O(1)时间内找到第i个元素。
2. 存储密度高，每个节点只存储数据元素。

缺点：

1. 拓展容量不方便，使用大片连续的空间，即便采用动态分配的方式实现，拓展长度的时间复杂度也比较高。
2. 插入、删除操作不方便，需要移动大量元素。

6.2.2链表

链式存储

优点：

1. 离散分配空间，分配方便，改变容量方便。
2. 单链表的节点是通过指针来连接的，因此在插入、删除节点时不需要移动其他节点，只需要修改指针的指向即可。

缺点：

1. 由于链表每个节点只存储了指向下一个节点的指针，只能顺序存储，不可随机存储，所以访问节点时需要从头指针开始依次遍历访问，直到找到需要的节点，或者到达链表的结尾。
2. 存储密度低，每个结点除了存储数据元素，还存储了指针。

6.3数据运算（基本操作）

6个基本操作：创销增删改查

6.3.1初始化

顺序表：

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

• 静态分配：静态数组，容量不可以改变。
• 动态分配：动态数组（malloc、free）：容量可改变，但需要移动大量元素，时间代价高。

链表：

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

6.3.2销毁表

顺序表：

1. 修改Length = 0
2. 释放空间
   • 静态分配：静态数组，系统自动回收空间。
   • 动态分配：动态数组（malloc、 free），需要手动free。

链表：

依次删除各个结点（free）。

6.3.3插入、删除

顺序表：

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

时间复杂度O(n)，时间开销主要来自移动元素。

链表：

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

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

若元素占用空间很大，那么移动元素花费的时间要比查找元素花费是时间代价更大。

6.3.4查找

顺序表：

按位查找：使用顺序存储，每个数据元素大小相同，所以可以随机访问，即可以在**O(1)**时间内找到第i个元素。

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

链表：

按位查找：由于单链表每个节点只存储了指向下一个节点的指针，只能顺序存储，不可随机存储，所以访问节点时需要从头指针开始依次遍历访问，直到找到需要的节点O(n)。

按值查找：只能遍历O(n)