数组

#数组

• 什么是数组
• 内存中的存储方式
• 随机访问
• 添加和删除数据
• 时间复杂度
• 数组与链表的对比

#什么是数组

数组是一种数据呈线性排列的数据结构。你可以把它想象成电影院里一排连续的座位——每个座位都有编号（索引），从 0 开始，座位之间没有空隙。

索引:   0      1      2      3      4
      ┌──────┬──────┬──────┬──────┬──────┐
数据:  │ Blue │Yellow│ Red  │Green │ Pink │
      └──────┴──────┴──────┴──────┴──────┘
       ↑
    a[0] 就是第一个元素

数组最大的特点是：数据按顺序存储在内存的连续空间内。

#内存中的存储方式

计算机内存就像一大堆带地址的抽屉。数组在申请内存时，会一次性申请一块连续的空间，所有元素紧挨着存放。

内存地址:  100   101   102   103   104
         ┌─────┬─────┬─────┬─────┬─────┐
         │  10  │  20  │  30  │  40  │  50  │
         └─────┴─────┴─────┴─────┴─────┘
           ↑
       a[0] 在地址 100
       a[1] 在地址 101 (= 100 + 1个元素的大小)
       a[2] 在地址 102 (= 100 + 2个元素的大小)

因为元素是连续存放的，所以只要知道数组起始地址和元素大小，就能直接算出任意元素的地址——这就是随机访问（Random Access）的基础。

#随机访问

想访问第 3 个元素？直接用 a[2] 就行，不需要从头遍历。不管数组有 10 个元素还是 1000 万个元素，访问任意一个元素的时间都是固定的。

a = [10, 20, 30, 40, 50]
print(a[2])   # 输出 30，一步到位
print(a[4])   # 输出 50，同样一步到位

#添加和删除数据

数组的添加和删除比较麻烦，因为要保持元素的连续性。

在中间插入元素（比如在第 2 个位置插入 Green）：

插入前:  Blue  Yellow  Red  Pink
                    ↓ 要在这里插入 Green

步骤1: 末尾申请空间
        Blue  Yellow  Red  Pink   _

步骤2: 把 Red 往后移
        Blue  Yellow  _    Red  Pink

步骤3: 把 Yellow 往后移（哦不，Yellow 留着）
        Blue  Yellow  _    Red  Pink

步骤4: 在空位写入 Green
        Blue  Yellow  Green  Red  Pink

删除元素反过来：先删掉目标，然后把后面的元素一个个往前移。

#时间复杂度

#数组与链表的对比

选择建议：

• 如果需要频繁随机访问（如通过索引读取元素），用数组
• 如果需要频繁插入和删除（如在头部添加元素），用链表
• 数组中所有元素的类型必须相同

#应用场景

• 存储需要按索引快速访问的数据（如查找表）
• 实现其他数据结构（栈、队列、堆的底层常用数组）
• 二分查找要求数据存储在数组中（因为需要随机访问）
• 动态数组（如 Python 的 list、Java 的 ArrayList）在底层也是数组，满了就自动扩容