很多人在学一门新课程时最容易忽略的偏偏是第一张。第一张通常看起来“全是概念、没有代码”感觉像是空话于是翻两页就过去了等后面真正写程序、做算法题时才发现什么都对不上。这次我把自己重新整理的《数据结构》第一章笔记重发出来就是因为我之前的那版笔记有遗漏还有两个地方把“逻辑结构”和“存储结构”给混着写了导致后期复习时自己把自己绕晕。这次我重新梳理把容易踩的坑一次性说清楚。这篇笔记不仅适合正在上数据结构课的人也适合考研复习、准备技术面试或者单纯自学编程基础的人。数据结构这门课的第一个章节核心就是四个东西逻辑结构、存储结构、抽象数据类型、算法与复杂度。把这四样吃透后面链表、栈、队列、树、图才能真的学明白这四样没建立好后面全靠死记硬背遇到变形题就崩。1. 为什么这一章的笔记值得专门重写1.1 “重发”不是复制粘贴而是一次完整的复盘第一版笔记是我当时一边听课一边匆匆记的问题很明显概念解释抄得多自己的理解少。比如“逻辑结构”和“存储结构”各自给了一个定义看起来都对但没有说明它们之间是什么关系结果复习的时候我盯着笔记问自己链表到底是逻辑结构还是存储结构答案其实应该是一条完整的链路逻辑上它是线性表存储上它采用链式存储链表二者兼顾。这种“二分法混淆”如果不及时纠正后面学到二叉树、图时会更痛苦。所以这次重发我做的事情有三件第一把概念重新归类明确每个术语到底在回答什么问题上第二给每个概念配了一两个“说人话”的例子第三把章末练习题里容易出的理解偏差整理成了问题清单。笔记不是教科书的搬运笔记应该是把抽象文字转成自己能复用的思维模型。1.2 第一章决定了后面章节的学习方式教材或者讲义一般把第一章命名为“绪论”或“概论”内容不外乎数据结构的定义、分类、算法效率的度量方法。但这部分恰恰决定了整本书的骨架。不懂“逻辑结构”和“存储结构”的区分学栈的时候不知道“顺序栈”和“链栈”的取舍从何而来不懂“抽象数据类型ADT”学完线性表后只会调用现成的库而无法自己设计数据类型不懂时间复杂度后面比较排序算法优劣时只能靠背结论。我后来和一些同样学过这门课的朋友聊大家普遍反馈一个感受一开始把第一章当“快速浏览”章节结果第二、第三章难度一上来就卡住。所以我把第一章看得比某些实操章节还重这一章是在建“坐标系”坐标系没建好后面所有的点都无处安放。2. 第一章核心概念四个大坑和四条主线2.1 逻辑结构数据结构到底“长什么样”逻辑结构描述的是数据元素之间的抽象关系它不考虑计算机内存怎么存储只讨论“人与人之间怎么联系”。例如一个班同学的名单前后顺序是确定的这就是线性结构一个公司的组织架构一个经理管多个员工这是树形结构一张地图上多个城市之间的道路连接这是图形结构一堆没有联系的数据放在一起就是集合结构。这里我强烈建议画图理解。不要把四种逻辑结构只当成名词背下来而是先问自己某个场景如果我要用程序表示最自然的逻辑关系是什么答案会引导你选择结构。比如通讯录通常适合线性表目录系统适合树路由表本质上更接近图。实际编程中真正处理问题时选择数据类型的第一步不是“我该用什么高级API”而是“这些数据之间的逻辑关系是什么”。2.2 存储结构数据在内存里的“物理姿势”存储结构才是真正和硬件、内存打交道的部分它解决一个核心问题逻辑结构如何在物理内存中落地并支持高效操作常见四种存储结构顺序存储把逻辑相邻的元素存储到物理位置也相邻的存储单元里典型代表是数组。链式存储借助指针把逻辑相邻的元素通过指针串联起来物理位置可以不相邻典型代表是链表。索引存储通过建立一个索引表来映射关键字和存储地址的关系常见于数据库场景。散列存储根据元素的散列值直接计算出存储位置典型代表是哈希表。顺序存储读取速度快因为通过下标就能直接算地址但插入和删除需要大量移动元素。链式存储相反插入删除灵活但每次访问某个节点都要从头或者从尾遍历而且额外空间存指针。这些取舍恰恰是后续章节反复提到的核心思想。2.3 抽象数据类型ADT把“做什么”和“怎么做”分开ADT 这个概念是很多初学者过不去的坎。它听起来高大上其实说白了就是“一个黑盒说明书”。ADT 由三部分组成数据对象、数据关系、基本操作。比如栈数据对象是若干同类型元素数据关系是线性关系基本操作有入栈、出栈、判断空栈等。至于栈内部是用数组实现还是链表实现ADT 不关心。一开始我也不明白为什么要搞这么一层抽象后来写项目时体会到了。如果你在写代码时依赖具体的实现类型那么一旦换一种存储方案整套逻辑就崩了。而如果你面向 ADT 编程比如只关心栈支持 push 和 pop那底层从数组换成链表调用方完全无感。这就是第一章一直强调的“逻辑结构、存储结构、算法实现分离”的实战意义。2.4 算法的五大特性与好坏评价第一章后半部分通常开始讨论算法。严格讲算法不等于程序算法是解决问题的一系列明确计算步骤它必须满足五点有穷性、确定性、可行性、有输入、有输出。我自己见过最典型的误区是把“死循环的程序”称为算法因为不满足有穷性还有人不给输入最后程序写成“写死”的常量计算严格说那也不是个好算法。评价算法的好坏核心看正确性、可读性、健壮性、高效性其中高效性最常被量化讨论这也是下一节大O记号出场的原因。3. 时间复杂度与空间复杂度内功心法的第一式3.1 为什么第一章就要学大O记号很多初学者会问我又不搞竞赛学这玩意儿干嘛实际上从第一章开始引入时间复杂度是为了让数据结构的比较有依据。说链表插入比数组快到底快在哪里说哈希表查找是常数级别到底意味着什么没有复杂度工具这些结论只能靠感觉而复杂度给了我们一个与具体机器无关的“数学标尺”。大O记号表达的是一种“增长趋势”而不是具体的运行秒数。它描述的是当问题规模 n 趋向于无穷大时算法的执行时间或空间随 n 增长的数量级。例如一个操作是 O(n)另一个是 O(n²)当 n10 时或许差距不大但当 n10000 时差的就不是倍数而是几个数量级。3.2 常见复杂度的直觉判断与代码示例O(1)常数级几条固定语句。例如读取数组下标arr[i]。O(logn)对数级常见于每次迭代将问题规模除以某个常数。例如int i 1; while (i n) { i i * 2; }这段代码中循环次数是 log2(n) 量级所以是 O(logn)。O(n)线性级单层循环遍历全部元素。O(nlogn)线性对数级常见于高效排序也容易出现在“外层循环 n 次、内层循环每次规模减半”的结构中。O(n²)平方级典型的二重循环。关于嵌套循环有个特别容易踩的误区不是所有二重循环都是 O(n²)。比如for (i 1; i n; i) { for (j 1; j n; j j * 2) { // 执行次数约为 n * log2(n) } }外层 n 次内层 log2(n) 次总复杂度是 O(nlogn)。判断嵌套复杂度时不能只看有几层循环要看每层循环的迭代步长和终止条件才能确定真正的执行次数。3.3 空间复杂度与“以空间换时间”空间复杂度衡量算法执行过程中额外需要的存储空间同样使用渐进记号描述。比如归并排序典型是 O(n) 的额外空间因为它需要临时数组原地排序算法可以做到 O(1) 额外空间。工程上经常出现“以时间换空间”或“以空间换时间”的设计。哈希表就是拿大量存储空间换常数的查找时间某些嵌入式环境内存极小就只能用更慢但省内存的算法。第一章讲明白了这种取舍后续所有数据结构都像是这两个维度上做选择题宁可更快还是更省空间。这种思维方式比记住任何具体 API 都重要。4. 实操过程我是怎样重新整理这章笔记的4.1 使用三种结构重组笔记内容我重新整理时没有继续使用传统“抄书式”的线性笔记而是把内容拆成三种模块概念地图把逻辑结构、存储结构、ADT、算法分析之间的关系画出来这能很快看出各知识点的归属。对比表格把顺序存储 vs 链式存储、四种逻辑结构、大O复杂度等做成对照表方便考前两三分钟快速扫一眼。问题卡片把每个知识点对应成一道自测问题。比如“如何判断一个操作是不是 O(1)”“为什么顺序插入是 O(n)”这种卡片比单纯看文字有用得多。比如我把逻辑结构做成了一个简单的表格逻辑结构描述典型例子集合结构元素之间无特定关系只是“同处一个集合”班级花名册无排序线性结构元素之间一对一有前后顺序排队买票的队列树形结构元素之间一对多有层次关系公司组织架构图形结构元素之间多对多网状关系地铁线路图表格的存在就是为了解决“名词太多、关系太绕”的问题我在复习第二天就能直接看着空表把内容默写出来。4.2 关键示例复盘从数组到链表的思维转变第一章里最经典的存储结构例子就是数组和链表。我学习时给自己打了一个比喻数组像电影院的连排座位每个座位都紧紧挨着你只要知道座位号马上能找到座位链表像寻宝游戏你知道第一个线索在哪儿然后根据纸条上的提示一步步找到下一个线索。这个类比很简单但它解释了两者所有区别数组随机访问快可以通过下标直接定位时间复杂度 O(1)链表要访问某个节点需要从头开始顺着指针找平均 O(n)。数组插入和删除大概率需要搬动后面所有元素O(n)链表插入删除只需要改指针如果已经知道前驱节点操作是 O(1)。这些推导不是靠背而是靠那个画面感一步步推出来的。笔记里我特意把数组和链表从“逻辑结构”到“操作复杂度”做了整个链条的整理线性表是逻辑结构数组和链表是它的两种存储实现选择哪种实现取决于你的数据访问模式和修改频率。这个“从逻辑到物理再从物理到操作代价”的路径才是第一章最该学会的分析方法。4.3 章末练习题中的常见错误复盘教材第一章的习题通常不会太难但我发现错误很有代表性集中在几个地方第一把“逻辑结构”等同于“存储结构”。比如有人说“图是链式结构”这就错了。图是一种逻辑结构图中每个顶点之间的关系是多对多至于图的存储方式可以用邻接矩阵也可以用邻接表那是存储结构的设计不能混为一谈。第二把“抽象数据类型”等同于“具体类”。有同学在问栈的 ADT 时直接写了 C 的 stack 类。ADT 是规格说明类是实现类可以实现 ADT也可以包含很多额外方法不能划等号。第三算时间复杂度时只看循环不看循环条件。在上面提到过的例子中内层循环每次 ii*2但不少人在第一次做时还是给出 O(n²)。我就吃过这个亏最后只能老老实实把每轮循环次数写在草稿纸上才纠正过来。这三点错误我在重写笔记时详细放在了显眼的位置因为我知道它们不是偶然的错误而是因为它们暴露了概念之间的联系没有建立。5. 常见问题与排查技巧实录5.1 概念混淆清理一张表解决三个高频问题复习时最容易忘的多数是容易混淆的界限我整理了一张高频问题速查表问题答案要点易错提示链表属于逻辑结构还是存储结构链表是线性表的链式存储实现属于存储结构逻辑上它表示线性关系物理上它是链式存储两者维度不同哈希表是哪种结构逻辑上看可以是集合或映射存储上属于散列存储不能说“哈希表是 O(1)”就完了还要说清楚在什么条件下是 O(1)算法和程序的关系算法不依赖具体语言程序是算法的一种具体实现程序可以不满足有穷性死循环但不能说它是算法为什么 ADT 重要它分离使用者和实现者降低耦合不要把它当作某个特定语言的 interface它是一种方法论这种表我会在每次阶段复习前更新一次发现不懂的知识点就再新增一行。第一遍可能很慢但第二遍、第三遍会快很多。5.2 时间复杂度计算中容易翻车的三种情况算复杂度除了嵌套循环那个经典误区还有几种情况容易翻车。情况一忘记去掉常数项。比如某个算法执行了 3n10 次基本语句复杂度是 O(n)不是 O(3n)大O只关注增长量级常数可以忽略。情况二误把不同的输入规模同时放进一个表达式。例如在同时涉及两个独立问题规模 m、n 的地方复杂度写 O(mn) 和写 O(n²) 含义完全不同不要默认 mn。情况三递归复杂度没有用递推式。第一章如果快速带过递归很多人会用循环结构硬套。典型例子是二分查找它的复杂度递推式为 T(n)T(n/2)O(1)结果是 O(logn)不要凭“循环里没嵌套就写 O(n)”的直觉。排查时间复杂度的经验其实就是回归定义用“随着 n 变大执行次数怎么变”来判断而不是按代码行数猜。5.3 笔记工具怎么选我用的是多层组织而不是单一软件做笔记这件事最怕的是把工具当成目的。我尝试过很多方式最后稳定下来的是一个非常简单的组合用 Markdown 笔记文件存放文字和代码用思维导图做概念层级梳理再用一个卡片工具做遗忘点复习。导读概念时Markdown 文件只需要一个不必追求几千条标签导图只画主干逻辑结构、存储结构、ADT、复杂度四条主线卡片里只写“容易错”的问题比如“为什么链表的随机访问是 O(n)”不要什么知识点都做成卡片不然复习时负担太大。工具可以换但核心思路是不变的结构化存放 主动回忆。6. 给初学者的一些个人建议6.1 不要在第一章省时间这是我的切身体会。我学数据结构第一次失败就是因为跳过了第一章觉得概念太简单。结果学到二叉树时发现自己连“为什么树节点要动态分配”“为什么递归要依赖栈”这类基础逻辑都理解得很吃力。第一次重看第一章后很多东西突然通了特别是前序、中序、后序遍历本质上就是不同顺序的递归入栈出栈过程而这个过程依赖的就是第一章关于栈和递归的底层理解。所以如果你是初学者建议在第一章多留一周时间哪怕每天只是“读一段概念、写一个小例子”也比后面花两周补要好得多。6.2 用自己的话定义术语而不是背教材原句每学一个概念我会强制自己在不看书的情况下写下“我的理解”。比如对 ADT 我的理解是它像电器说明书中的接口规格消费者只知道插头是三孔还是两孔不用知道内部电路怎么走这种抽象让它更安全、更易迭代。把自己的比喻写下来比反复抄定义记得牢得多。如果发现自己写不出口说明还没真正理解。6.3 永远把“复杂度分析”当成工具而非考试题在刚开始学大O时我也觉得它很抽象。后来做题看别人题解发现所有的“为什么这个解法更快”本质上都是在做复杂度分析。数据结构的终极意义就是让你在合适的时间与空间约束下做选择。就算不考研、不面试平时做项目时如果你在一个超大列表里反复用indexOf查找最终发现卡顿也是因为你没有考虑复杂度这一层。所以我建议把第一章所有复杂度结论都当成分析工具来记数组按索引查是 O(1)按值查找无序数组是 O(n)这就是你在选择数据结构时最重要的依据。最后再分享一个我在重发笔记过程中发现的细节自己之前写“链表插入复杂度为 O(1)”时漏了“在已知被插入位置的前驱节点的前提下”这个限制条件。这看起来是个很不起眼的表述但实际工程里你要插入一个元素通常还得先 O(n) 找到那个位置这时候整体操作依然是 O(n)。这种细节最容易在考试和面试中被拿出来做文章。重看一遍第一章笔记花不了多少时间但它能帮你把后面所有章节的“地基”重新夯一遍。如果你也正准备学数据结构希望这份重发的笔记思路能给你一点参考。