第3章数组、链表与递归：数据结构的积木块 🧱

第3章封面

真正的数据结构从本章开始！数组、链表、递归——后面所有花哨结构都是这三块积木搭出来的。

🎮 数组的第一战：游戏高分榜

书里用一个游戏记分板热身：维护 top 10 高分。核心问题来了——新分数插进有序榜单怎么办？

数组插入的成本是 O(n)（最坏全体搬家）。这个痛点，正是引出链表的动机 ⬇️

数组 vs 链表

单链表 = 一串节点，每个节点装「数据 + next 指针」：

struct Node {
    string elem;   // 数据
    Node* next;    // 指向下一个节点
};

头插法是链表的招牌动作——两步搞定，O(1)！

Node* v = new Node;   // 1. 新建节点
v->elem = e;
v->next = head;       // 2. 新节点指向原头
head = v;             // 3. 头指针让位

双链表升级版：每个节点有 prev 和 next 两个指针，可以倒着走、可以 O(1) 删除「自己」——标准库 std::list 的真身。删除节点 x 的口诀：让 x 的前驱越过 x 指向后继，让 x 的后继越过 x 指回前驱，然后 delete x ✂️。

循环链表：尾节点的 next 指回头部，转一圈是圆的。书里用它实现「轮流转」的游戏逻辑（比如报数淘汰），还演示了一个经典面试题：不用栈，纯指针操作反转链表——三指针（prev/cur/next）轮流推进，一遍线性扫描搞定。

递归 = 函数调用自己。每个正确的递归必须有三要素：

int factorial(int n) {
    if (n <= 1) return 1;      // 基准情形
    return n * factorial(n-1); // 更小的自己
}

书里用「线性数组求和」「汉诺塔」示范递归思维：相信递归会正确处理更小的子问题，你只管处理当前这一层——这个「递归的信仰之跃」（leap of faith）是初学者最重要的心法 🧘。

下一章：怎么科学地比较这些操作的快慢？答案是大 O 记号 ⏱️

description	第 3 章笔记：数组的游戏计分板应用、单链表与双链表的插入删除、循环链表反转，以及递归的三要素——初学者最友好的图解版。
tags	C++数据结构