每章核心概念与考点对比表，按教材顺序排列：线性表与链表 → 栈与队列 → 串/数组/广义表。
一. 线性表和链表
一、时间复杂度 & 空间复杂度（总表）
1）核心概念总结表
| 概念 | 它在问什么 | 直观理解 | 常见写法 | 你学习时要关注什么 |
| 时间复杂度 | 算法运行时间随数据规模 n 增长的变化趋势 | 数据变大后，程序会慢多少 | O(1), O(logn), O(n), O(nlogn), O(n²) | 关注「循环层数、递归层数、是否嵌套」 |
| 空间复杂度 | 算法额外占用内存随 n 的变化趋势 | 数据变大后，要多占多少内存 | O(1), O(n) 等 | 关注「有没有新开数组/链表/递归栈」 |
2）常见复杂度等级（从快到慢）
| 复杂度 | 名称 | 直观速度 | 常见场景 |
O(1) | 常数级 | 非常快，数据再大也差不多 | 数组按下标访问、栈顶操作 |
O(logn) | 对数级 | 很快 | 二分查找 |
O(n) | 线性级 | 数据翻倍，时间大约翻倍 | 遍历数组/链表 |
O(nlogn) | 线性对数级 | 常见高效排序 | 快排（平均）、归并、堆排 |
O(n²) | 平方级 | 数据稍大就变慢明显 | 冒泡、选择、插入（最坏） |
O(2^n) | 指数级 | 很慢 | 暴力枚举子集、部分递归 |
O(n!) | 阶乘级 | 极慢 | 全排列暴力 |
3）如何快速判断时间复杂度（口诀表）
| 代码结构特征 | 常见复杂度 |
| 单条语句、固定次数操作 | O(1) |
| 单层循环（跑 n 次） | O(n) |
| 两层嵌套循环（都跑 n 次） | O(n²) |
每次规模减半（n → n/2） | O(logn) |
| 循环里再做一次线性操作 | O(n²)（常见） |
| 递归树分裂（如分治） | 常见 O(nlogn)（需具体分析） |
4）时间复杂度 vs 空间复杂度（对比表）
| 对比项 | 时间复杂度 | 空间复杂度 |
| 衡量对象 | 运行快慢趋势 | 内存占用趋势 |
| 主要看哪里 | 循环、递归、调用次数 | 新开空间、递归深度 |
| 优化思路 | 减少重复计算、降低嵌套 | 原地操作、减少辅助数组 |
| 常见取舍 | 用空间换时间（如哈希） | 用时间换空间（少开数组） |
二、线性表和链表（建立整体认识）
线性表是「逻辑结构」（数据之间是一条线）； 链表是「存储实现方式」之一（另一种常见实现是顺序表/数组）。
1）线性表（Linear List）总结表
| 项目 | 内容 |
| 定义 | 具有相同数据类型的元素组成的有限序列 |
| 逻辑特点 | 元素之间是「一对一」的前后关系（除首尾外） |
| 常见操作 | 查找、插入、删除、获取长度、判空 |
| 常见实现 | 顺序表（数组实现）、链表（链式实现） |
| 学习重点 | 区分「逻辑结构」和「存储结构」；同一个线性表可以有不同实现方式 |
2）顺序表 vs 链表（核心对比总表）
| 对比项 | 顺序表（数组实现） | 链表（链式实现） |
| 存储方式 | 连续内存 | 非连续内存（节点靠指针连接） |
| 访问第 i 个元素 | 快，O(1) | 慢，需从头找，O(n) |
| 插入/删除（中间位置） | 慢，需移动元素，O(n) | 已找到位置则 O(1)；含查找则总 O(n) |
| 空间利用率 | 可能预留空间，扩容麻烦 | 按需申请，更灵活，但有指针额外开销 |
| 缓存友好性 | 好（连续内存） | 较差（离散内存） |
| 实现难度 | 较简单 | 稍复杂（指针容易出错） |
| 适合场景 | 查询多、插入删除少 | 插入删除多、长度变化大 |
三、链表（重点）总结表
1）链表的基本结构
| 项目 | 内容 |
| 节点组成 | 数据域(data) + 指针域(next)（单链表） |
| 头指针 | 指向第一个节点 |
| 头节点（可选） | 有些实现会加一个不存有效数据的头节点，方便操作 |
| 本质 | 通过指针把离散节点「串」成线性关系 |
2）链表常见类型
| 类型 | 特点 | 适合记忆方式 |
| 单链表 | 每个节点只有 next | 只能往后走 |
| 双链表 | 节点有 prev 和 next | 前后都能走 |
| 循环单链表 | 尾节点 next 指回头节点 | 首尾连成环 |
| 循环双链表 | 双向 + 首尾成环 | 操作更灵活 |
3）顺序表与链表的常见操作复杂度对比
设表长为 n
| 操作 | 顺序表 | 链表 | 说明 |
| 按位查找（第 i 个） | O(1) | O(n) | 顺序表可直接下标访问 |
| 按值查找 | O(n) | O(n) | 都要遍历（平均情况） |
| 表尾插入 | O(1)（若容量够） | O(1)（有尾指针）或 O(n) | 看是否维护尾指针 |
| 中间插入 | O(n) | O(n) + O(1)（改指针） | 链表优势在「改链接不搬元素」 |
| 中间删除 | O(n) | O(n) + O(1)（改指针） | 单链表删除前需要前驱节点 |
| 获取长度 | O(1)（若维护长度） | O(n)（若不维护长度） | 实现方式有关 |
| 判空 | O(1) | O(1) | 看头指针/长度即可 |
四、关键结论
| 结论 | 一句话理解 |
| 线性表是逻辑结构，链表是存储结构 | 不要把两者当成同级概念 |
| 顺序表查找快，链表插删灵活 | 一个偏「访问」，一个偏「修改」 |
| 链表不是插入删除一定快 | 前提是你已经找到插入/删除位置 |
| 复杂度要分情况写 | 最好/平均/最坏可能不同（考试常问） |
二. 栈和队列
一、栈和队列的整体认识
| 结构 | 本质 | 规则 | 典型关键词 | 常见应用 |
| 栈（Stack） | 受限线性表 | 后进先出（LIFO） | 栈顶、压栈、出栈 | 函数调用、括号匹配、表达式求值、DFS |
| 队列（Queue） | 受限线性表 | 先进先出（FIFO） | 队头、队尾、入队、出队 | 排队模型、BFS、任务调度、缓冲区 |
二、栈（Stack）
1）核心概念表
| 项目 | 内容 |
| 定义 | 只允许在一端进行插入和删除的线性表 |
| 允许操作的一端 | 栈顶（Top） |
| 插入操作 | 压栈（Push） |
| 删除操作 | 出栈（Pop） |
| 读取栈顶 | 取栈顶元素（GetTop / Peek） |
| 特点 | 后进先出（LIFO） |
2）两种实现对比
| 对比项 | 顺序栈（数组） | 链栈（链表） |
| 存储方式 | 连续内存 | 链式节点 |
| 栈顶位置 | 用 top 下标表示 | 用头指针表示栈顶 |
| 入栈/出栈 | O(1) | O(1) |
| 空间特点 | 容量固定（或需扩容） | 按需申请空间 |
| 适合场景 | 容量大致可预估 | 容量变化较大 |
3）高频应用场景
| 场景 | 为什么用栈 |
| 括号匹配 | 最近遇到的左括号要最先匹配（LIFO） |
| 表达式求值（中缀/后缀） | 运算符优先级处理天然适合栈 |
| 函数调用栈 | 后调用的函数先返回 |
| 递归实现 | 递归本质依赖系统栈 |
| 深度优先搜索（DFS） | 回溯过程符合栈结构 |
4）易错点
| 易错点 | 说明 |
| 栈空/栈满判断 | 顺序栈常考边界条件 |
| top 的定义差异 | 有教材 top 指向栈顶元素，有指向下一个可插入位置（代码要统一） |
| 出栈前先判空 | 否则越界 / 非法访问 |
| 链栈释放节点 | 出栈后记得 free（C/C++） |
三、队列（Queue）
1）核心概念表
| 项目 | 内容 |
| 定义 | 只允许一端插入、另一端删除的线性表 |
| 插入位置 | 队尾（Rear） |
| 删除位置 | 队头（Front） |
| 特点 | 先进先出（FIFO） |
2）三种实现
| 类型 | 特点 | 优缺点 |
| 顺序队列（数组） | 用数组 + front/rear | 容易出现「假溢出」 |
| 循环队列 | 数组首尾连起来 | 能复用空间，重点考点 |
| 链队列（链表） | 队头队尾指针 | 动态空间，入队出队方便 |
3）循环队列核心知识
| 项目 | 内容 |
| 目的 | 解决顺序队列「假溢出」问题 |
| 思想 | 数组逻辑上首尾相接（下标取模） |
| 常见写法 | rear = (rear + 1) % MaxSize，front = (front + 1) % MaxSize |
| 判空条件 | front == rear |
| 判满条件（牺牲一个单元方案） | (rear + 1) % MaxSize == front |
| 队列长度 | (rear - front + MaxSize) % MaxSize |
4）高频应用场景
| 场景 | 为什么用队列 |
| 广度优先搜索（BFS） | 按层推进，先进先出 |
| 操作系统调度 | 任务排队处理 |
| 消息队列 / 缓冲区 | 数据按到达顺序处理 |
| 树的层序遍历 | 按层访问节点天然是队列模型 |
四、栈 vs 队列（对比记忆表）
| 对比项 | 栈 | 队列 |
| 规则 | 后进先出（LIFO） | 先进先出（FIFO） |
| 插入删除位置 | 同一端（栈顶） | 两端（队尾入、队头出） |
| 典型应用 | 回溯、递归、括号匹配 | BFS、调度、缓冲 |
| 常考实现 | 顺序栈、链栈 | 循环队列、链队列 |
| 易错点 | 栈空/栈满、top 边界 | 循环队列判满、取模公式 |
三. 串、数组、广义表
三者对比总结
| 对比项 | 串 | 数组 | 广义表 |
| 逻辑结构 | 线性 | 线性 / 多维线性映射 | 递归结构 |
| 元素类型 | 字符 | 同类型元素 | 原子或子表 |
| 存储特点 | 常用顺序存储 | 连续存储 | 链式递归存储 |
| 核心优势 | 文本处理、匹配 | 随机访问快 | 表示嵌套结构强 |
| 课程重点 | KMP | 地址计算、矩阵压缩 | 长度/深度、表头表尾 |
| 常见难点 | next 数组理解 | 二维地址公式、压缩下标 | 递归定义易混 |
关键结论
| 结论 | 一句话理解 |
| 串是特殊线性表，重点不是插删而是匹配 | KMP 是核心 |
| 数组的灵魂是连续存储 + O(1) 随机访问 | 地址公式很重要 |
| 数据结构课讲数组，常常重点在特殊矩阵压缩 | 稀疏矩阵常考 |
| 广义表是递归结构，不是普通线性表 | 长度和深度一定分清 |
| 广义表是理解树/递归思想的过渡 | 后面学树会更轻松 |