数组插入、链表插入的时间复杂度对比？

数组插入 vs 链表插入的时间复杂度可以这样对比： ## 1. **数组插入** * **情况 1：尾部插入** * 如果数组未满，直接放到末尾 → **O(1)** * 如果已满，需要扩容（新建数组 + 复制数据） → **O(n)** * **情况 2：中间插入** * 需要把插入位置之后的元素整体后移一位 → **O(n)**（移动元素是瓶颈） **总结**： * 尾插（有容量）→ O(1) * 任意位置插入 → O(n) ## 2. **链表插入** * **单链表**： * 如果已知要插入位置的节点引用 → **O(1)**（只需改指针） * 如果只知道位置索引，需要先遍历找到位置 → **O(n)**（查找是瓶颈） * **双向链表**： * 同样，如果已拿到节点引用 → **O(1)** * 需要按索引查找 → O(n) **总结**： * 已知节点插入 → O(1) * 按索引插入 → O(n) ## 3. **对比表** | 操作场景 | 数组 | 链表 | | -------------- | ----------- | ------------------- | | **尾插（有容量）** | O(1) | O(1)（需要先到尾节点则 O(n)） | | **中间插入（已知索引）** | O(n)（移动元素） | O(n)（遍历）/O(1)（已知节点） | | **满容量插入** | O(n)（扩容+复制） | 不存在扩容成本 | **一句话总结** * **数组**插入慢在**移动元素**，**链表**插入慢在**找位置**。 * 如果频繁随机插入且已知节点位置 → 链表更优；如果按索引访问多 → 数组更优。