数组
1. 无序数组
| 操作 | 时间复杂度 |
| 查询 | O(1) |
| 插入 (空间充足) | O(1) |
| 插入 (空间不足) | O(n)+O(1)=O(n) |
| 删除 (末尾元素) | O(1) |
| 删除 (非末尾元素且元素个数> 1) | O(1)+O(n)=O(n) |
分析
1. 查询：通过 index 直接定位，即 O(1)。
2. 插入分为以下两种情况：
2.1 空间充足：无序数组不需要考虑插入位置，直接插入到末尾，即 O(1)。
2.2 空间不足：如果空间不足，则需要将整个数组移动到另一个空间，再添加元素，即 O(n)。
3. 删除分为以下两种情况：
3.1 删除末尾元素：删除末尾不需要考虑移动元素位置，即 O(1)。
3.2 非末尾元素且元素个数 > 1：删除操作 O(1)+ 移动元素位置 O(n)=O(n)。
2. 有序数组
| 操作 | 时间复杂度 |
| 查询 | O(1) |
| 插入 (基于二分查找法) | O(log2n)+O(n)=O(n) |
| 插入 (基于顺序查找法) | O(n)+O(n)=O(n) |
| 删除 (末尾元素) | O(1) |
| 删除 (非末尾元素且元素个数> 1) | O(1)+O(n)=O(n) |
分析
1. 查询：通过 index 直接定位，故时间复杂度为 O(1)。
2. 插入有序数组的插入需要考虑插入位置，即分下列两种情况查询插入位置：
2.1 二分查找法 二分查找法的时间复杂度为 O(log2n)，移动元素位置的时间复杂度为 O(n)，即 O(log2n)+O(n)=O(n)。 2.2 顺序查找法 顺序查找法查找的时间复杂度为 O(n)，移动元素位置的时间复杂度为 O(n)，即 O(n)+O(n)=O(n)。 ps：如果数组本身无序，还需要进行排序的话，使用冒泡排序复杂度达到 o(n^2)。
3. 删除分为以下两种情况：
3.1 删除末尾元素：删除末尾不需要考虑移动元素位置，即 O(1)。
3.2 非末尾元素且元素个数 > 1：删除操作 O(1)+ 移动元素位置 O(n)=O(n)。
链表 (单向链表)
1. 有序链表 (失去了链表插入快的特性)
| 操作 | 时间复杂度 |
| 查询 | O(n) |
| 插入 | O(n) |
| 删除 | O(n)+O(1)=O(n) |
分析
1. 查询：依次比较，最好情况下第一个就是即 o(1)，最坏情况 o(n)，取最坏情况 o(n)。
2. 插入：有序链表的插入需要先查询到该插入的位置，且链表不能使用二分查找，即 o(n)。
ps: 可以考虑使用跳跃表来达到 o(logn) 的时间复杂度，但是其空间复杂度达到了 o(n)，也是可以接受的。
3. 删除：和插入一样，需要先去找到要删除的元素，查询元素位置 O(n)+ 删除操作 O(1)=O(n)。
2. 无序链表
| 操作 | 时间复杂度 |
| 查询 | O(n) |
| 插入 | O(1) |
| 删除 | O(n)+O(1)=O(n) |
分析
1. 查询：同有序链表查询，取最坏情况 o(n)。
2. 插入：不需要考虑插入位置，即 o(1)。
3. 删除：同有序链表一样，即查询元素位置 O(n)+ 删除操作 O(1)=O(n)。
PS：如有错误，还请各位老师不吝赐教！
