四、进阶概念

1. 动态数组 (Dynamic Array)

普通的数组（如 int a[10]）一旦声明，大小就定死了。如果装满了怎么办？ 现代语言（Java ArrayList, C++ vector, Python list）使用的是动态数组。

• 策略：
  1. 初始化给一个小空间（比如 10）。
  2. 如果满了，自动开辟一块更大的新空间（通常是 1.5 倍或 2 倍）。
  3. 把旧数据复制过去。
  4. 扔掉旧数组。
• 代价：虽然扩容很慢（$O(n)$），但因为不常发生，平均下来每次插入还是接近 $O(1)$。

2. 数组 vs 链表

这是数据结构最经典的对比：

维度	数组 (Array)	链表 (Linked List)
内存	连续存储	分散存储，通过指针连接
访问	$O(1)$ (秒杀)	$O(n)$ (得从头数)
插入/删除	$O(n)$ (要搬运)	$O(1)$ (改指针即可，不含查找时间)
空间利用	可能浪费（预分配）	无浪费，但每个节点多存一个指针
CPU缓存	友好 (预读数据)	不友好

3. 二维数组

内存其实是一维的。二维数组（矩阵）在内存里也是拉成一条直线存的。

• 行优先（C/Java）：先存第一行，再存第二行...
• 列优先（Fortran）：先存第一列，再存第二列...

---