主题
第二章 数组、切片与链表
1. 线性结构为什么是整个课程的起点
线性结构是最基础的一类逻辑结构。所谓线性，不是说它一定画成一条直线，而是说元素之间存在一对一的先后关系：除首尾外，每个元素通常都只有一个前驱和一个后继。数组、切片、链表、栈、队列，本质上都建立在这种关系之上。
学习线性结构最重要的，不是把“顺序表”和“链表”背下来，而是理解它们分别代表了两种几乎贯穿全课程的设计哲学：
- 用连续内存换随机访问和缓存友好。
- 用指针连接换动态插删和结构灵活。
2. 数组：最纯粹的连续存储
数组是固定长度、元素类型相同、地址连续的一段内存。它的最大优势是可以直接按下标定位。
2.1 为什么数组按下标访问是 O(1)
若数组首地址为 base，每个元素大小为 size，第 i 个元素地址就是：
text
address(i) = base + i * size这意味着读取 a[i] 不需要从头遍历，只要做一次偏移量计算就能定位。
2.2 数组的代价
数组最典型的问题是中间插入和删除需要搬移元素。例如在位置 k 插入新值时，k 之后的元素都要整体向后腾位，因此时间复杂度通常是 O(n)。
如果数据规模固定、随机访问频繁、插删较少，数组往往是非常好的选择。很多更复杂的结构，例如二叉堆、哈希桶数组、图的邻接矩阵，底层都继承了数组这套连续存储思想。
3. Go 中的数组与切片
Go 里数组和切片都很重要，但它们不是一回事。
3.1 数组
数组长度是类型的一部分：
go
var a [4]int[4]int 和 [5]int 是不同类型，长度固定，值拷贝语义明确。
3.2 切片
切片是对底层数组的一个窗口描述，包含三部分元数据：
- 指向底层数组某位置的指针。
- 长度
len。 - 容量
cap。
切片看起来像“动态数组”，本质上是“数组 + 自动扩容策略 + 视图语义”。这就是为什么切片既方便，又需要警惕共享底层数组带来的副作用。
4. 用 Go 实现一个最小动态数组
理解切片很方便，但为了真正掌握“动态数组为什么能工作”，最好手写一次扩容逻辑。
go
package arraylist
import "fmt"
type ArrayList struct {
data []int
size int
}
func NewArrayList(capacity int) *ArrayList {
if capacity < 1 {
capacity = 1
}
return &ArrayList{
data: make([]int, capacity),
}
}
func (a *ArrayList) Len() int {
return a.size
}
func (a *ArrayList) Get(index int) (int, error) {
if index < 0 || index >= a.size {
return 0, fmt.Errorf("index out of range")
}
return a.data[index], nil
}
func (a *ArrayList) Append(value int) {
a.Insert(a.size, value)
}
func (a *ArrayList) Insert(index, value int) {
if index < 0 || index > a.size {
panic("index out of range")
}
if a.size == len(a.data) {
a.grow()
}
for i := a.size; i > index; i-- {
a.data[i] = a.data[i-1]
}
a.data[index] = value
a.size++
}
func (a *ArrayList) Remove(index int) (int, error) {
if index < 0 || index >= a.size {
return 0, fmt.Errorf("index out of range")
}
removed := a.data[index]
for i := index; i < a.size-1; i++ {
a.data[i] = a.data[i+1]
}
a.size--
a.data[a.size] = 0
return removed, nil
}
func (a *ArrayList) grow() {
next := make([]int, len(a.data)*2)
copy(next, a.data)
a.data = next
}这段代码体现了动态数组的核心事实：
- 追加在大多数时候只是在尾部写入，近似
O(1)。 - 一旦容量耗尽，就要整体复制到更大的底层数组。
- 因此
Append的单次最坏复杂度可能是O(n)，但均摊复杂度通常是O(1)。
5. 链表：把“位置关系”从地址连续变成指针连接
链表不要求元素物理连续，而是把每个元素包装成节点，再通过指针把节点连起来。
5.1 单链表节点定义
go
package linkedlist
type Node struct {
Value int
Next *Node
}5.2 为什么链表按下标访问是 O(n)
因为链表没有“基地址 + 偏移量”这套定位能力。若要访问第 k 个节点，只能从头节点出发，一步步沿 Next 指针走过去。
5.3 为什么链表局部插入删除可以很快
只要已经拿到待操作位置的前驱节点，修改几根指针即可完成插入删除，不需要整体搬移元素。这是链表最大的理论优势。
6. 用 Go 实现一个单链表
go
package linkedlist
import "fmt"
type List struct {
head *Node
size int
}
func (l *List) Len() int {
return l.size
}
func (l *List) PushFront(value int) {
l.head = &Node{
Value: value,
Next: l.head,
}
l.size++
}
func (l *List) InsertAfter(prev *Node, value int) error {
if prev == nil {
return fmt.Errorf("prev node is nil")
}
prev.Next = &Node{
Value: value,
Next: prev.Next,
}
l.size++
return nil
}
func (l *List) RemoveAfter(prev *Node) (int, error) {
if prev == nil || prev.Next == nil {
return 0, fmt.Errorf("no node to remove")
}
removed := prev.Next
prev.Next = removed.Next
l.size--
return removed.Value, nil
}
func (l *List) Find(value int) *Node {
for cur := l.head; cur != nil; cur = cur.Next {
if cur.Value == value {
return cur
}
}
return nil
}7. 双向链表和哨兵节点
单链表的一个局限是只能顺着 Next 向前走。如果需要频繁从尾部删除、双向遍历或在已知节点前插入，双向链表会更自然。
go
type DNode struct {
Value int
Prev *DNode
Next *DNode
}工程里还经常引入哨兵节点（dummy node），把头尾边界统一起来，减少“空表”“只剩一个节点”这类特殊分支。这不是语法技巧，而是典型的数据结构设计能力：通过增加一个稳定节点，让算法边界更统一。
8. 顺序存储与链式存储的核心比较
| 维度 | 数组 / 切片 | 链表 |
|---|---|---|
| 随机访问 | O(1) | O(n) |
| 中间插入删除 | O(n) | 找到位置后可 O(1) |
| 缓存局部性 | 好 | 差 |
| 额外空间 | 少 | 需要指针 |
| 扩容问题 | 需要整体复制 | 无连续空间要求 |
很多教材会把“链表插入删除快”讲成绝对结论，这是不严谨的。更准确的说法是：如果你已经定位到待操作位置，链表的局部改链非常快；但若定位本身要线性扫描，总代价仍可能是 O(n)。
9. 典型误区
9.1 把 Go 切片误当作纯粹链表式动态结构
切片扩容仍依赖底层连续数组，和链表是两种完全不同的设计。
9.2 认为链表一定比数组“高级”
链表不是更高级，而是适合不同场景。现代 CPU 对连续内存极度友好，在很多扫描型任务里，数组往往比链表快得多。
9.3 只记结论，不看边界条件
链表代码最容易错在：
- 空链表插入。
- 删除头节点。
- 尾节点的
Next是否置空。 - 更新
size时机是否正确。
10. 本章小结
这一章真正要掌握的不是“数组和链表的定义”，而是三件事：
- 连续存储为什么能带来随机访问和缓存友好。
- 指针连接为什么能带来局部插删灵活性。
- Go 的切片虽然好用，但底层仍然属于连续存储模型。
后面的栈、队列、堆、哈希桶、图的邻接表，都会反复用到本章奠定的这些思想。