顺序表&有序表

1. 顺序表（指存储结构）

定义

顺序表是一种线性表（Linear List）的实现形式，它是通过一段连续的存储空间来存储线性表的数据元素的。

特点

1. 数据以连续的内存空间存储，类似于数组。
2. 每个元素之间的存储地址是连续的。
3. 可以通过索引直接访问任意位置的元素（时间复杂度为 O(1)）。
4. 插入和删除操作效率较低，因为需要移动大量元素（平均时间复杂度为 O(n)）。
5. 常见操作包括插入、删除、访问、遍历等。

优点

1. 支持快速的随机访问。
2. 节省额外的存储空间（不像链表需要额外指针）。

缺点

1. 内存空间要求连续，可能会引发存储分配问题。
2. 插入和删除操作效率较低。

应用场景

适用于需要频繁访问数据、插入和删除操作较少的场景。

2. 有序表（指表结构）

定义

有序表（Ordered List）是指其数据元素按照一定的顺序排列（例如从小到大、从大到小等）的表结构。 与顺序表不同，有序表强调的是数据逻辑上的有序性，与是否采用顺序存储无关。

存储方式

有序表可以通过顺序存储实现，也可以通过链式存储实现。 无论存储方式如何，其逻辑上要求数据元素是有序排列的。

特点

1. 数据按某种逻辑顺序排列。
2. 插入操作需要找到合适的位置，保证有序性。
3. 查找效率高，可以使用二分查找（时间复杂度 O(log n)），但插入和删除效率较低（O(n)）。

优点

1. 查找操作效率较高。
2. 在需要有序数据的场景中非常高效。

缺点

1. 插入和删除操作需要调整数据以保持有序性，开销较大。

应用场景

适用于需要频繁查找操作、有序性要求高的场景，如有序字典、优先队列等。