主题
第二章 数组、切片与链表
1. 线性结构为什么是整个课程的起点
线性结构是最基础的一类逻辑结构。所谓线性，不是说它一定画成一条直线，而是说元素之间存在一对一的先后关系：除首尾外，每个元素通常都只有一个前驱和一个后继。数组、切片、链表、栈、队列，本质上都建立在这种关系之上。
学习线性结构最重要的，不是把“顺序表”和“链表”背下来，而是理解它们分别代表了两种几乎贯穿全课程的设计哲学：
- 用连续内存换随机访问和缓存友好。
- 用指针连接换动态插删和结构灵活。
2. 数组：最纯粹的连续存储
数组是固定长度、元素类型相同、地址连续的一段内存。它的最大优势是可以直接按下标定位。
2.1 为什么数组按下标访问是 O(1)
若数组首地址为 base，每个元素大小为 size，第 i 个元素地址就是：
text
address(i) = base + i * size这意味着读取 a[i] 不需要从头遍历，只要做一次偏移量计算就能定位。
2.2 数组的代价
数组最典型的问题是中间插入和删除需要搬移元素。例如在位置 k 插入新值时，k 之后的元素都要整体向后腾位，因此时间复杂度通常是 O(n)。
如果数据规模固定、随机访问频繁、插删较少，数组往往是非常好的选择。很多更复杂的结构，例如二叉堆、哈希桶数组、图的邻接矩阵，底层都继承了数组这套连续存储思想。