在YouTube上，讲“数据结构”的视频多如牛毛，但能把大学一整学期的内容装进一条超长视频、并且常年霸榜的，freeCodeCamp频道的《Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer》是绕不开的一条。主讲人William Fiset是一位谷歌工程师，他从最基础的数组讲到并查集，全程配动画与代码实现。本文替你把这条课程视频“读厚”：它讲了什么、每个结构背后的真实历史与理论出处、哪些说法经得起推敲，以及普通开发者能带走的三件可操作的东西。你没看过视频也能读懂本文；看过视频的人，会多懂一层它没明说的“为什么”。
| 项目 | 内容 |
|---|---|
| 标题 | Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer（《数据结构：从易到难全程课——谷歌工程师主讲》） |
| 频道 | freeCodeCamp.org（非营利开源教育组织，全球头部免费编程教育频道） |
| 主讲 | William Fiset（谷歌软件工程师） |
| 发布时间 | 约2020–2021年间（据频道页面，本轮未能实时核验） |
| 形态 | 单条超长系统课，从线性结构一路讲到并查集 |
| 热度 | freeCodeCamp算法与数据结构方向的长课代表作之一（具体播放量据频道页面，本轮未实时核验） |
说明：本轮采编环境网络受限，上表信息以频道公开页面历史记录为准，发稿时未能逐项实时复核；下文理论部分均为教科书级公开知识。
第一站，先立尺子：Big-O不是公式，是“增长直觉”。 课程开篇不写任何结构，先花大篇幅讲时间复杂度与空间复杂度：同样一份任务，O(1)、O(log n)、O(n)、O(n²)在输入规模翻倍时表现完全不同。这是整门课的“度量衡”——后面每个结构都会被放到这把尺子上量一次。这个安排暗合一个事实：数据结构课真正教的不是结构本身，而是权衡。
第二站，线性结构三兄弟：动态数组、链表、栈与队列。 数组支持O(1)随机访问但中间插入要搬移元素；链表反过来，插入删除是O(1)，但定位第i个元素必须从头走。栈（后进先出）和队列（先进先出）则是“加了限制的线性结构”——限制带来的是更清晰的使用契约。课程在这一段反复演示同一件事：每个结构都有一张代价表，没有全能选手。
第三站，哈希表：平均O(1)的魔法与它的最坏情况。 课程用“哈希函数把键映射到桶”的动画讲清了哈希表为何平均常数时间，也讲了两件容易被略过的事：负载因子升高要扩容重哈希（rehash），以及所有键撞进同一个桶时退化成O(n)的链表扫描。链地址法与开放寻址两种流派各有取舍——这是整门课里“平均与最坏”反差最大的结构。
第四站，树的世界：从二叉搜索树的病，到自平衡的药。 二叉搜索树（BST）让查找变成“每步排除一半”，但如果按有序顺序插入，它会退化成一条链表。课程随后给出解药：AVL树这类自平衡结构通过旋转保持左右平衡，让最坏情况也稳定在对数级；堆（heap）则是一种“只在顶端讲道理”的树，支撑起优先队列，也是堆排序的地基。
第五站，并查集：小众结构的一击致命。 课程尾声的并查集（Union-Find）处理“元素分属哪些集团”这类问题：合并两个集合、查询两个元素是否同属一集。配上路径压缩与按秩合并后，它的单次操作代价低到反直觉。这是整门课“看似冷门、实战封神”的代表，也是面试高频考点。
贯穿全程的主张只有一句：选数据结构，就是选一张时间与空间的汇率表——你愿意为读得快付出什么，为写得快放弃什么。
这门课的每个模块背后都有真实的学术源流，这里把最关键的几条铺开。
Big-O记号：符号"O"由德国数学家保罗·巴赫曼（Paul Bachmann）在1894年的数论著作中首次引入，经兰道（Edmund Landau）推广成数论标准工具，因此又称“兰道记号”。把 systematically 引入计算机科学语境并规范成今天教科书用法的，是高德纳1976年发表在SIGACT News上的著名信件《Big Omicron and Big Omega and Big Theta》。课程里“最坏情况复杂度”的口径，正来自这一脉。
链表：并非教科书原创。1955–1956年，艾伦·纽厄尔（Allen Newell）、克利夫·肖（Cliff Shaw）与赫伯特·西蒙（Herbert Simon）在开发IPL信息处理语言时发明了链表，用于构造他们的“逻辑理论家”推理程序；三人后来共获1975年图灵奖。链表从诞生起就是为“人工智能程序管理动态内存”服务的——这段出身很少在入门课里被讲起。
哈希表：公认起点是1953年IBM内部的一份备忘录，作者汉斯·彼得·卢恩（Hans Peter Luhn）提出了哈希与链地址解决冲突的想法；高德纳在《计算机程序设计艺术》第三卷里给出了系统的分析。今天Python的dict、Java的HashMap，本质都是这条线的工程化后代。
AVL树：1962年，苏联数学家格奥尔基·阿德尔松-维利斯基（Georgy Adelson-Velsky）与叶夫根尼·兰迪斯（Evgenii Landis）发表论文《An Algorithm for the Organization of Information》，提出史上第一个自平衡二叉搜索树。"AVL"正是两人姓氏缩写——课程里“旋转”动画的学术原点。
堆：1964年，J. W. J. Williams为提出堆排序发表了堆结构；同年罗伯特·弗洛伊德（Robert Floyd）给出自底向上建堆的改进，把建堆复杂度压到线性。今天操作系统调度、Dijkstra算法里的优先队列，都是这对1964年工作的直系后代。
并查集：结构雏形见于1964年Galler与Fischer的论文；真正让它“封神”的是罗伯特·塔扬（Robert Tarjan）1975年的分析——在路径压缩与按秩合并下，单次操作的摊还代价正比于阿克曼反函数α(n)，对一切现实规模输入，α(n)不超过4，几乎是“常数中的常数”。课程演示“快到反直觉”的数学凭证就在这里。
证据充分的部分：课程各结构的复杂度结论与《算法导论》（CLRS）等标准教材完全一致；动画演示的插入、删除、旋转过程符合各结构的规范定义；Big-O、哈希、AVL、堆、并查集的理论出处如上，全部可查证。作为“知识骨架”，这条课程视频是可靠的。
需要打折扣的部分：
其一，“Easy to Advanced”的标题承诺要谨慎对待。看懂动画与能写出无bug实现之间隔着大量练习——这也是课程配套开源实现仓库的原因。把它当成“一次看完的地图”是恰当的；当成“一次学会的捷径”则会翻车。
其二，课程用Java做实现载体，这点利弊并存。自动垃圾回收与泛型让代码干净易读，但也掩盖了C/C++世界里手动内存管理与缓存布局的真实代价。现代硬件上，“理论更优”的链表因为指针跳转破坏缓存局部性，实际性能常常反而不如数组——这是工程界长期存在的争论，课程没有太多着墨。
其三，哈希表“平均O(1)”的表述在面试语境里被过度简化了。平均背后是哈希函数质量、负载因子、扩容时机三个前提；现实中还要叠加常数因子——这正是各语言标准库不断调参的原因。
其四，课程天然带有面试导向的取舍：每个结构像“考点清单”一样被逐一介绍，但工程中真正难的往往不是结构本身，而是读写比例、数据规模与一致性要求决定的选择——这部分产品级判断，任何入门课都给不了。
各章节在不同年份版本中的详略与顺序略有调整，具体以频道页面当前版本为准。
第一，给每个新结构画一张“代价表”。 遇到任何数据结构，只问四件事：读、写、查、删各要几步？把这个答案写成表格再动手写代码。这张表会让你在“用数组还是用哈希”这类决策上不再凭感觉——本文开头那句“选结构就是选汇率表”，落到实处就是这张表。
第二，用“退化测试”检验自己是否真懂。 每学一个结构，问：什么输入会让它最惨？BST的答案是按序插入，哈希表的答案是全部撞桶。把这些退化条件直接写成单元测试的边界用例——这既是面试答题的深度来源，也是生产代码里真正的防御点。
第三，挑一个结构自己实现一遍。 从哈希表或并查集里选一个，不看库、写出来、再做压力测试，最后对照语言标准库的源码找差距。“实现一遍”对心智模型的塑造，超过“看十遍动画”——这也是这条课程视频把自己与配套练习仓库绑在一起的原因。
flowchart TD
A[先立尺子<br/>Big-O增长直觉] --> B[动态数组<br/>读快插慢]
A --> C[链表<br/>插快读慢]
B --> D[栈与队列<br/>限定线性结构]
C --> D
A --> E[哈希表<br/>平均O1最坏On]
E --> F[二叉搜索树<br/>有序可查]
F --> G[AVL自平衡<br/>旋转治病]
F --> H[堆与优先队列]
A --> I[并查集<br/>小众利器]
G --> J[选结构=选代价表]
H --> J
I --> J
本文由「51学通信」技术团队出品。51学通信由通信行业18年老兵爱卫生（微信ID: gprshome201101）维护，聚焦5G/6G核心网、3GPP标准解读、通信前沿技术深度分析。 出版作品有《5G核心网原理与实践》《IMS原理与实践》等4本通信专业书籍。知识星球「51学通信」提供深度技术答疑和行业洞察。
[!tip] 51学通信知识星球 星主：爱卫生（微信：gprshome201101）——公众号「51学通信」创办者，19 年通信行业运维与讲师经验，著有《GPRS网络信令实例详解》《EPC原理与实践》《5G核心网原理与实践》三本纸质书（各大电商平台有售）。 星球定位：深耕 5G 核心网、IMS、NFV/AI、云原生等 ICT 领域，主打运维岗位与信令分析。 当前规模：5200 篇主题 / 990 个回答，198 元/年。 加入福利：加入星球后请加爱卫生微信，拉您进知识星球年度陪伴与答疑群——不限量回复您的各种问题，另有群内分享。 AI 加持：51学通信知识星球已作为 skill 接入 WorkBuddy，使用 deepseek-4-flash 在海量星球帖子中精准找贴、找视频、找 FAQ 和案例，做总结、找文档和 PPT 等场景全覆盖。