数组是什么？

一个显示一周气温的天气应用需要七个数字。它可以用七个单独的变量，比如 monday、tuesday 等等，但这样就没法用循环遍历它们，而且要加上第八天还得写新代码。数组把这七个数字放在同一个名字 temperatures 下，存进编号从 0 到 6 的格子里。

数组是如何工作的

数组把元素一个挨一个地放在同一块内存里，每个元素占用相同数量的字节。这种布局让计算机只需一次计算就能找到任意元素：

address of element i = start address + i × element size

假设一个 32 位整数数组（每个元素 4 字节）从内存地址 1000 开始。元素 0 在 1000，元素 1 在 1004，元素 2 在 1008，元素 3 在 1012。访问元素 3 和访问元素 3,000,000 一样只需一步，所以通过索引读取数组被称为常数时间，记作 O(1)。

Python 的 array 模块就是这样存储原始数字的，你可以验证一下这个算式：

from array import array

scores = array("i", [90, 75, 88, 62])
print(scores.itemsize, "bytes per element")
print(len(scores) * scores.itemsize, "bytes in total")

start = 1000  # pretend the array starts at address 1000
for index in range(len(scores)):
    address = start + index * scores.itemsize
    print("scores[" + str(index) + "] =", scores[index], "at address", address)

4 bytes per element
16 bytes in total
scores[0] = 90 at address 1000
scores[1] = 75 at address 1004
scores[2] = 88 at address 1008
scores[3] = 62 at address 1012

这个公式也解释了为什么大多数语言从 0 开始计数。索引其实是偏移量：从开头要跳过多少个元素。第一个元素距离开头 0 个元素，所以它的索引是 0；长度为 n 的数组，最后一个元素的索引是 n − 1。也有少数语言从 1 开始，比如 Lua、MATLAB、R 和 Fortran。

在 Python 中使用数组

大多数 Python 代码把内置的 list 当作数组来用。用方括号创建它，通过索引读取和修改元素，用 len() 获取它的长度：

temperatures = [18, 21, 25, 23, 19]

print(temperatures[0])   # first element
print(temperatures[2])   # third element
print(temperatures[-1])  # last element
print(len(temperatures))

temperatures[1] = 22     # change one element
temperatures.append(20)  # add one at the end
print(temperatures)

18
25
19
5
[18, 22, 25, 23, 19, 20]

负数索引从末尾开始数，所以 temperatures[-1] 是最后一个元素。这是 Python 特有的写法，C 和 Java 都没有负数索引。

数组操作的开销

连续的内存布局让一些操作很快，另一些则很慢。开销随元素个数 n 增长：

在开头插入很慢，因为每个元素都得往后挪一格腾出位置。在无序数组中查找，需要用线性查找依次检查每个元素；而有序数组可以用二分查找，每一步都把剩余范围缩小一半。

遍历数组

数组和循环总是形影不离：循环依次访问每个元素，这叫作迭代。同样几行代码，既能处理 5 个元素的数组，也能处理 500 万个元素的数组。

prices = [4.50, 12.00, 3.25, 8.75]

total = 0
for price in prices:
    total = total + price

print("Total:", total)
print("Most expensive:", max(prices))

Total: 28.5
Most expensive: 12.0

其他语言中的数组

在 C 语言中，数组的大小在声明时就固定了，里面存放的是同一类型的原始值。sizeof 会给出它占用的字节数：

int scores[5] = {90, 75, 88, 62, 100};   /* 5 × 4 bytes = 20 bytes */

Java 数组的长度同样是固定的，新元素以默认值开始，比如数字的默认值是 0。如果需要一个能增长的 Java 数组，就用 ArrayList：

int[] scores = new int[5];   // five elements, all 0
scores[0] = 90;

JavaScript 数组可以自由增长和缩短，还能混合不同类型，比如 [1, "two", true]。

能够增长的数组，例如 Python 的 list、Java 的 ArrayList 和 C++ 的 std::vector，叫作动态数组。它们会在末尾预留额外空间。空间用完时，就分配一块更大的内存，把所有元素复制过去，然后继续使用。由于复制很少发生，平均来看追加元素依然很快。

数组里也可以放数组。grid[row][col] 读取二维数组中的一个单元格，游戏棋盘、电子表格和图像都采用这种布局。C 语言多维数组指南介绍了它们在内存中的排列方式。

常见错误

差一错误。 有 3 个元素的数组，索引是 0、1 和 2，所以索引 3 已经越界。Python 会报错并停止：

scores = [90, 75, 88]
print(scores[3])

IndexError: list index out of range

Java 会抛出 ArrayIndexOutOfBoundsException，JavaScript 则悄悄返回 undefined。C 完全不做检查：越界读取属于未定义行为，可能返回垃圾值，也可能让程序因段错误而崩溃。

用赋值来复制。 在 Python、Java 和 JavaScript 中，b = a 并不会复制数组；两个名字指向的是同一个数组，所以修改 b 也会改变 a。要真正复制，在 Python 中用 a.copy()，在 JavaScript 中用 [...a]。变量页面解释了其中的原因。

下一步学什么

数组要配合循环遍历才有用，所以接下来可以读读迭代是什么；想了解上面元素大小背后的单位，可以看字节是什么。Python 列表指南讲解了切片、排序和列表方法，链表可视化则展示了一种用快速插入换掉快速索引的数据结构。