What is an array?什么是数组？

A row of boxes with numbers. If you know the number, you jump straight to the box.一排带编号的盒子。知道编号，就能一步走到那一格。

Short answer先给答案An array is a row of numbered boxes that sit next to each other. You reach a box by its number (index), which starts at 0. Reading is O(1); inserting in the middle is O(n).数组是一排紧挨着、带编号的盒子。用编号（下标，从 0 开始）直接跳到某一格。读是 O(1)，往中间插入是 O(n)。

Basics基础data structure数据结构O(1) read读 O(1)

01The idea先有一个画面

Think of it like this先这样想Ten lockers in a row. They touch each other. Each locker has a number: 0, 1, 2 … 9. If you know the number, you walk straight to that locker. You do not open the other nine first.十个储物柜排成一排，紧挨着。每个柜子有编号：0、1、2……9。知道编号，你就直接走到那个柜子，不用先把另外九个都打开。

An array is that row of boxes. It has two facts:数组就是这一排盒子。它只有两个事实：

The boxes are next to each other in memory.这些盒子在内存里紧挨着。
Each box has a number, called an index. The first index is 0, not 1.每个盒子有个编号，叫 index（下标）。第一个是 0，不是 1。

index下标	0	1	2	3	4
value值	apple苹果	banana香蕉	cherry樱桃	date枣	fig无花果

02Why reading is fast为什么“读”很快

Because the boxes touch each other, the computer can compute the address:因为盒子紧挨着，电脑可以直接算出地址：

address = start + index × size_of_one_box

So reading box 500 costs the same as reading box 0. One step. In Big O words, this is O(1) — constant time.所以读第 500 格和读第 0 格一样快：都是一步。用大 O 的说法，这叫 O(1)，常数时间。

03Why inserting is slow为什么“插入”很慢

The boxes are full and touching. If you insert an item in the middle, every item after it must move one step to the right. With one thousand items, that is one thousand moves. This is O(n) — linear time.盒子是满的、紧挨着的。在中间插入一个东西，后面的每一个都得往右挪一步。一千个元素就是一千次挪动。这叫 O(n)，线性时间。

When you add to the end and there is still room, it is O(1). Only inserting in the middle or at the front is expensive.往末尾加、并且还有空位，是 O(1)。只有往中间或最前面插才贵。

04Where you meet it你会在哪里遇到它

A list of orders for today: you know the position, you want it fast.今天的订单列表：知道位置，要快。
A HashMap is built on an array — that is why lesson 4 exists.HashMap 底层就是一个数组，所以后面要学第 4 课。

→New words新词

array /əˈreɪ/ A row of boxes that touch each other.数组：紧挨着的一排盒子 ▶ hear it

index /ˈɪndeks/ The number of a box. Starts at 0.下标：盒子的编号，从 0 开始 ▶ hear it

element /ˈelɪmənt/ One item inside an array.元素：数组里的一个东西 ▶ hear it

contiguous /kənˈtɪɡjuəs/ Touching, with no gaps.连续的：紧挨着没有空隙 ▶ hear it

traverse /trəˈvɜːrs/ Walk through the items one by one.遍历：一个个走过去 ▶ hear it

Click ▶ hear it for real people on YouGlish; 🔊 for the computer voice.点 ▶ hear it 听真人发音（YouGlish）；点 🔊 听电脑朗读。

✓Check yourself自测

Why is reading index 500 as fast as index 0?为什么读第 500 格和读第 0 格一样快？
What has to happen when you insert in the middle?往中间插入时，发生了什么？
Which is O(1) and which is O(n): read, insert at the end, insert at the front?哪个是 O(1)、哪个是 O(n)：读、末尾加、最前面插？

Answer out loud first. Only then open the answers below.先自己出声答，再看下面的答案。

Answers参考答案

01Because the address is computed, not searched: start + index × size. One step.因为地址是算出来的，不是找出来的：起始地址 + 下标 × 每格大小，一步到位。

02Every item after the insert point moves one step to the right: O(n).插入点后面的每一个元素都要往右挪一步：O(n)。

03Read O(1); add at the end with room O(1); insert at the front or middle O(n).读 O(1)；末尾还有空位时加 O(1)；最前面或中间插 O(n)。

Next: Lesson 2, linked list →下一课：第 2 课，链表 →