为什么数组的插入和删除平均是 O(n)？

简化版

数组是连续内存，元素一个挨一个不能有空隙。在中间插入一个元素，后面所有元素都得整体往后挪一格腾位置；删除中间元素，后面的又要整体往前补一格填空。平均要搬移一半元素，所以是 O(n)。只有在末尾插入删除才是 O(1)（不用搬移别人）。

详细版

位置	插入	删除	原因
末尾	O(1)*	O(1)	不影响其他元素
头部	O(n)	O(n)	后面全部元素都要搬移
中间第 k 个	O(n-k)	O(n-k)	第 k 个之后的都要搬移

（*末尾插入在动态数组里是均摊 O(1)，偶尔触发扩容那次是 O(n)。）

核心原因：数组必须保持连续。要在中间腾出/填补一个位置，就得移动它后面的一整段元素来维持「连续、无空洞」。平均插入/删除位置在中间，要搬移约 n/2 个元素，量级是 O(n)。

完整版教学

一、为什么非搬移不可

数组靠「连续内存 + 下标寻址」实现 O(1) 随机访问（地址 = 首地址 + i×元素大小）。这个公式成立的前提是元素之间没有空隙。如果你在中间抠掉一个元素留个洞，或者硬塞一个进去，后面元素的下标和实际地址就对不上了，寻址公式就失效。所以为了维持「连续无洞」这个不变式，插入要把后面的元素整体后移腾位，删除要整体前移补位。

二、插入的过程

在下标 k 处插入一个新元素：

原:  [a, b, c, d, e]        在 index=2 插入 x
步骤: 从末尾开始，e、d、c 依次向后挪一格
结果: [a, b, x, c, d, e]

从后往前挪（避免覆盖），需要移动 n - k 个元素。在头部插入（k=0）最坏，要挪全部 n 个。

三、删除的过程

删除下标 k 处的元素：

原:  [a, b, x, c, d]        删除 index=2 的 x
步骤: c、d 依次向前挪一格，覆盖掉 x
结果: [a, b, c, d]

同样要移动 n - k - 1 个元素。删头部最坏 O(n)。

四、末尾操作为什么快

在末尾插入或删除，后面没有元素需要搬移，直接放/移即可，是 O(1)。这就是为什么栈（只在一端操作）用数组实现效率很高，也是为什么 ArrayList 的 add(e)（尾部追加）均摊 O(1)、而 add(0, e)（头部插入）是 O(n)。

五、想要高效增删怎么办

频繁在两端增删 → 用链表或双端队列（ArrayDeque），增删是 O(1)。
只在末尾增删 → 数组/动态数组就很好。
一个技巧：删除不要求保序时，可以把「要删的元素」和「最后一个元素」交换，再删末尾，这样把 O(n) 删除降成 O(1)（代价是打乱顺序）。

操作位置	插入需要移动	删除需要移动	复杂度
头部 `index=0`	移动 n 个元素	移动 n-1 个元素	O(n)
中间 `index=i`	移动 `n-i` 个元素	移动 `n-i-1` 个元素	O(n)
尾部	不需要移动已有元素	不需要移动已有元素	O(1)

举个数字例子：长度 10000 的数组在下标 2500 插入一个元素，需要把原下标 2500 到 9999 的 7500 个元素整体后移；删除下标 2500 的元素，则要把 2501 到 9999 的 7499 个元素前移。复杂度里的 O(n) 就来自这批搬移。

数组的“删除”通常不是把内存中间挖掉一块，而是把后续元素前移并把有效长度减 1。底层连续性必须被维护。

六、常见误区与追问

误区：数组删除元素只要把该位置置空。 置空会留下洞，破坏连续有效区；顺序表语义下必须移动后续元素。
误区：数组尾部删除也是 O(n)。 如果只删除最后一个有效元素，直接 size-- 即可，通常是 O(1)。
误区：中间插入慢是因为找位置慢。 即使下标已知，插入仍要搬移后续元素，因此仍是 O(n)。
追问：如果不要求保持顺序，删除能不能更快？ 可以用最后一个元素覆盖被删位置，再 size--，这样 O(1)，但元素相对顺序会改变。
追问：动态数组能否解决中间插入删除 O(n)？ 不能，扩容只解决容量不足；连续存储决定了中间操作要搬移。
追问：为什么链表中间删除可能是 O(1)？ 前提是已经拿到目标节点及其前驱/双链表节点引用，只改指针即可；定位节点仍可能是 O(n)。

七、加强记忆

数组必须保持「连续无空洞」才能 O(1) 寻址，所以中间插入要把后面元素整体后移、删除要整体前移，平均搬移半数元素，是 O(n)。只有末尾操作不搬移别人，是 O(1)。要频繁在两端增删就改用链表 / ArrayDeque；不要求保序时可用「和末尾交换再删」把删除降到 O(1)。

简化版

详细版