【数据结构】数组：最基础也最重要

如果要选一个最能代表计算机底层思维的数据结构，那非**数组（Array）**莫属。

它是所有编程语言里最常见的结构，也是几乎所有高级数据结构（比如堆、栈、哈希表）的基石。但你真的了解它吗？为什么数组下标要从 0 开始？为什么它的随机访问快如闪电，而插入删除却慢如蜗牛？

今天，小明带你揭开数组的“裙摆”。

一、数组的定义：连续与一致

在计算机科学中，数组的定义非常严苛：数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。

关键词有三个：

1. 线性表：数据排成一条线。
2. 连续的内存空间。
3. 相同类型的数据。

正是因为这三点，数组获得了一个逆天的技能：随机访问。

二、随机访问：为什么是 O(1)？

想象一下，内存就像一排整齐的储物柜。每个柜子都有一个编号（内存地址）。

当你向系统申请一个长度为 5 的 int 数组时，系统会分配一段连续的空位给你。假设首地址是 1000，每个 int 占 4 字节。

那么：

• a[0] 的地址是 1000
• a[1] 的地址是 1000 + 1 * 4 = 1004
• a[2] 的地址是 1000 + 2 * 4 = 1008
• ...

计算公式就是：a[i]_address = base_address + i * data_type_size。

因为计算机计算这个加法和乘法非常快，而且不需要遍历，所以无论数组有多长，根据下标找数据的时间复杂度都是 O(1)。

2.1 为什么下标从 0 开始？

如果下标从 1 开始，公式就变成了： a[i]_address = base_address + (i - 1) * data_type_size。

看到了吗？多了一个 (i - 1) 的减法运算。对于数组这种最底层、使用最频繁的操作，能省掉一个减法就是巨大的性能提升。

三、插入与删除：为什么很慢？

成也萧何败也萧何。数组为了保持内存的“连续性”，在修改数据时付出了沉重的代价。

3.1 插入操作

如果你想在数组的第 1 个位置插入一个数据，为了腾出空位，你需要把后面所有的元素都往后挪一个位置。

• 最好情况：插在末尾，O(1)。
• 最坏情况：插在开头，O(n)。
• 平均情况：O(n)。

3.2 删除操作

同理，删掉中间一个元素，为了不留“坑”，后面所有的元素都要往前挪。

• 复杂度：同样是 O(n)。

小明的小贴士： 在某些高性能场景下，如果我们需要连续删除多个元素，可以先记录下这些“待删除”标记，等数组空间不够时，再统一进行一次大规模的搬移（这就是 JVM 标记-清除垃圾回收算法的核心思想）。

四、数组 vs 容器（如 JavaScript 的 Array）

有些朋友会问：“小明，我在 JS 里用数组，又是插又是删，还能存不同类型的数据，没感觉慢啊？”

那是由于高级语言的数组已经不是纯粹的底层数组了。

• 它们通常是动态数组（Dynamic Array），会自动扩容。
• 它们在底层可能做了很多优化，比如针对不同类型的数据使用不同的存储策略。
• 它们甚至可能是用哈希表模拟的（在某些 JS 引擎早期版本中）。

但无论如何封装，连续内存空间带来的 CPU 缓存友好性（CPU Cache Locality）是其他结构无法比拟的。

总结

1. 数组是连续内存空间、相同类型数据的线性集合。
2. 随机访问极快 (O(1))，主要归功于寻址公式。
3. 插入删除较慢 (O(n))，因为需要搬移数据以维持连续性。
4. 低级语言中数组更接近底层，高级语言中数组多为封装好的容器。

小明建议： 如果你在做性能极其敏感的开发，或者在处理大规模数值计算，请务必使用最原始、类型确定的数组。如果只是处理日常业务，高级语言提供的动态数组（如 JS 的 Array, Python 的 List）是更方便的选择。

“为什么数组这么快？” “因为它比你想象的更‘简单’，而计算机最喜欢简单的东西。” —— 小明

最后，送你一个冷笑话： 一个程序员去相亲，女方问：“你有什么特长？” 程序员想了想说：“我能在一秒钟内找到数组里的任意一个元素。” 女方：“……那插入呢？” 程序员：“那得看你能不能接受 O(n) 的等待时间。” 程序员，卒。