数组 Array

数据结构 · 连续内存里的带下标序列

什么是数组

数组是一段连续的内存，里面挨个排着同类型的元素。每个元素都有一个从 0 开始的下标（index）。要取第 i 个元素，直接按下标一步到位、不用从头挨个找——这叫随机访问，时间复杂度 O(1)。

但代价藏在改动里：因为元素必须保持连续，往中间插入一个，下标 i 往后的元素就得整体右移一格腾位；删除一个，后面的又得左移补位。这两步都是 O(n)。下面亲手试试——点一个格子选中它的下标，再用工具栏操作。

点中下标 2 按「访问」，它瞬间高亮，不管数组多长都一样快。再按「在 2 处插入」，看下标 2 起的元素怎么排队右移给新元素让位；删除则反过来左移补位；而「尾部追加」放在末尾，谁也不用动， O(1)。插几次后你会发现：下标和值不再相等——下标是位置，值是内容，本就是两码事。

动态数组：容量满了怎么办——翻倍扩容

上面这个数组容量是固定的。可现实里我们天天用的「数组」——JS 的 Array、C++ 的 vector、Java 的 ArrayList、Python 的 list——却能一直 append 下去，靠的就是动态扩容。

它的办法是：当容量正好装满、还要再放，就开一个2 倍大的新数组，把旧元素逐个拷过去（O(n)），再放新元素。拷贝很贵，但只在「装满」那一刻才发生。一直点「追加」试试。

关键全在「翻倍」上：容量 4 → 8 → 16 → … 指数增长，扩容越来越稀疏。把每次扩容的拷贝成本摊到它之后那一大批 append 上，平均下来每次 append 只花常数次操作——这就是「尾部追加均摊 O(1)」的摊还分析。看右边那个均摊读数，无论追加多少次它始终有界，不会越长越慢。

数组在哪里用

几乎无处不在，凡是「按编号快速取用、整体顺序存放」的场景都靠它：

数组胜在随机访问、败在中间增删要搬移。下一篇讲链表——它把元素用指针串起来，增删只改指针、不搬移，正好和数组互为镜像。