第二章 线性心法：数组、链表、栈、队列与哈希表

第二章 · 线性心法：数组、链表、栈、队列与哈希表

本章要回答的三个问题：为什么"按下标取元素"在数组里是一步直达、在链表里却要一步步走？栈和队列只是"受限的线性表"，凭什么值一个专章？哈希表号称一步命中，它的代价和翻车条件是什么？

为什么会有这一章

线性结构是所有结构的原材料：字符串是字符数组、哈希桶挂的是链表、树的节点间靠"指针链"相连、图的邻接表本质是链表的集合。它们回答同一个母题——元素排成一条线时，不同的"接线方式"让哪些操作一步到位、哪些操作寸步难行。

数组和链表是这条线的两种极端接法：连续内存对随机访问，离散节点对插删。栈与队列在这条线上加了访问规则（只许一头进出），换来了"顺序即语义"的简洁，函数调用栈、撤销栈、消息队列全靠它。哈希表则干脆跳出"相邻关系"，用哈希函数直接算出元素的住址，把查找的价格打到常数——代价藏在冲突与扩容里。五种结构吃透，后面树、图、排序的每一步推理都有落点。

这五种结构也是面试与工程选型的高频考点，但背结论没有用：数组的均摊扩容、链表的反转、哈希的退化条件，每一个都要能边画图边推演，才算真正入手。本册的讲法因此一律"先给现场、再给结论"——每个复杂度数字都有可复算的实验垫底。

读完能解决什么

对照开头的问题，本章的知识点清单如下，全部可动手验证：

• 能画出数组与链表的内存布局，解释按下标访问的复杂度差异（O(1) 对 O(n)）；
• 能数出数组指定位置插入的搬移次数，并解释动态数组追加为何均摊 O(1)；
• 能手写单链表的反转与快慢指针找中点，说出双向链表与循环链表的适用场景；
• 能用栈实现括号匹配并解释函数调用栈的行为；能用取模法实现环形队列并说明判满条件；
• 能手工模拟链地址法与线性探测法的冲突处理过程，算出装载因子与探测次数；
• 能识别本章六大走火入魔场景：列表当队列用、头插建链表读序颠倒、循环队列判满写反、可变对象当键等；
• 能按"访问模式"给五种结构排座次：按下标、按顺序、按最近与否、按先来后到、按关键字，各归其位。

各节怎么分工

先决条件

• 第一章的复杂度推导规则（相加取最大、相乘、均摊）与递归栈模型，本章多处直接引用；
• Python 列表的基本操作（索引、切片、append、pop）；不需要任何指针语言经验，链表用类的实例引用模拟。

往下走到哪

本章出口是三件兵器：随机访问（数组）、顺序访问（链表及其衍生）、关键字定位（哈希表）。第三章的树是"链表的多叉推广"——每个节点不止一个后继；堆与优先队列（第三章）建立在数组的父子下标映射上；第四章图的邻接表是链表数组；第五章排序的主战场就是数组。线性心法不牢，后面每章都要回头补课。自检方法也很简单：合上书，把五种结构各画一张内存示意图，标出每个操作的代价来源——画不出的那种，就是该重读的节。

线性结构全景