第1章 邂逅数据结构与算法

1.1 为什么需要学习数据结构与算法？

为什么要学习数据结构与算法？这是一个非常核心且经典的问题。很多初学者会疑惑：“现在各种编程语言都有强大的库和框架，像JavaScript直接调用Array.prototype.sort()方法不就能排序了吗？为什么还要花那么大功夫去学冒泡排序、快速排序这些底层的东西？”

学习数据结构与算法，不是为了死记硬背几个标准实现，而是为了培养一种“内功”，一种用计算机思维高效解决复杂问题的能力。归纳总结，编程的世界是对数据的处理，而数据结构与算法是对数据处理最直接的体现。编程的最终目的是对数据进行操作与处理。通过一个人是否可以更好的操作和处理数据来评判他的编程能力、水平的高低。

在当下AI盛行的时代，这门课程还有没有必要学习？我觉得是有必要的，因为数据结构与算法并不属于工具类内容（随用随学），本质是一个人底层的核心逻辑，无时无刻都在发挥作用，数据结构与算法通过AI临时掌握的概率很低，是更需要理解的课程。结合这门课程去理解应用层操作，能够利用AI更加得心应手，上手各种热门新技术也更快。

"术之尽头，炁体源流"这句话在《异人之下》的语境里，讲的是一个修行者的终极认知跃迁，是一个很有意思的概念。你可以穷尽一生去修炼各种术法、手印、法门，把每一招每一式打磨到极致，但当你真正走到"术"的尽头时，会发现所有外在的技法不过是"炁"这个根源之力的不同表达形式。术是手段，炁是本体；术千变万化，炁归于一源。修行者如果只在术的层面打转，永远只是匠人；唯有触摸到炁体源流，才算真正开悟。

把这个框架映射到计算机体系里，"术"对应的就是我们日常接触的各种上层技术——框架、语言、工具链、设计模式、架构方案。React、Vue、Spring Boot、Docker、K8s……每隔几年就会有新的"术"涌现，开发者疲于追赶，像极了修行者在不同法门之间辗转腾挪。而"炁体源流"，在计算机世界里，正是数据结构与算法这一层。它不是某种具体的技术，而是所有技术得以成立的底层逻辑根基。数据库的B+树索引、操作系统的进程调度队列、网络协议栈的哈希表路由、编译器的抽象语法树——你把任何一个看似复杂的系统层层剥开，最终裸露出来的骨架，都是数据结构。

更深一层来看，"术之尽头"这四个字暗含了一种认知上的"撞墙"体验。很多开发者在职业生涯中都会遇到这面墙：框架用得再熟也不知道它为什么快，SQL写得再溜也不理解查询优化器在干什么，分布式系统出了诡异的bug却无从下手。这面墙的本质，就是"术"的天花板。你在API的层面已经走到头了，再往前一步，必须看见底下那层东西——数据如何组织、如何流动、如何以最小的代价完成存取和变换。这就是"炁体源流"的含义：不是让你放弃术，而是让你理解术之所以成立的根因。当你真正理解了哈希表为什么是O(1)、红黑树为什么能自平衡、图的最短路径为什么能用松弛操作求解，你再回头去看那些框架和工具，会发现它们不过是这些基本结构的排列组合与工程封装，就像修行者悟了炁的本质之后，看一切术法都成了炁的不同姿态。

所以这句话最精妙的地方在于"源流"二字。它不是说"炁体本源"这种静态的说法，而是"源流"——源是起点，流是运动。数据结构在计算机体系中的地位也恰恰如此：它既是源头，定义了数据最基本的存在形态；又是流动的，因为算法本质上就是数据结构在时间维度上的展开，是结构从一个状态流向另一个状态的过程。一棵AVL树的旋转、一个堆的上浮下沉、一张图的BFS层层扩散，都是"流"的体现。源是静态的骨骼，流是动态的气血，二者合一，才撑起了整个计算机大厦从底层硬件到上层应用的全部生命力。

框架会过时，语言会迭代，但数据结构不会。它是计算机科学的"炁体源流"——你可以不从它开始，但你一定会在它面前结束你所有的困惑。

1.1.1 编程的真相 – 数据的处理

在正式学习数据结构之前，我们需要先回到一个最本质的问题：编程到底是在做什么？如果剥开所有花哨的概念——前端、后端、算法、人工智能、区块链，再撇开语言层面的差异——JavaScript、Java、C++，会发现一个极其朴素的现象：编程的最终目的只有一个，就是对数据进行操作和处理。

前端从后端获取数据，经过处理后展示在界面上；用户与界面交互产生新的数据，再传回后端；后端接收这些数据，进行业务逻辑的处理，最终保存到数据库中，以便后续的读取、操作和展示。这条数据从产生到消亡的完整链路，就是所有软件系统运转的核心脉络。无论我们站在这条链路的哪个环节上，工作本质都是在和数据打交道。

既然编程的本质是处理数据，那么评判一个开发者能力高低的标准也就变得清晰了：你能否更好地组织和处理数据。这里的"更好"包含两层含义：

（1）一是更高效，用更少的时间和空间完成同样的任务；

（2）二是更清晰，让数据的流转和存储具有良好的结构，使代码易于理解和维护。

诚然，当下的各种系统和框架已经为我们封装了大量好用的API，大多数时候我们只需要调用它们就能完成需求。但这也恰恰制造了一种危险的舒适区：当你习惯了只做API的搬运工，一旦数据变得复杂、场景变得棘手，你就会发现自己无从下手。真正的开发工程师和API调用程序员之间的分水岭，正在于此——前者理解数据应该以什么样的方式被组织、被存取、被变换，后者只知道调用哪个函数能跑通。而数据结构，正是跨越这条分水岭的第一把钥匙。

1.1.2 数据结构与算法的本质

那么，数据结构与算法究竟是什么？本质上，它是一门专门研究数据如何组织、存储和操作的学科。这三个动词精确地概括了它的全部关切：组织，决定数据之间以怎样的逻辑关系彼此关联；存储，决定这些关系在物理层面如何映射到内存或磁盘上；操作，决定在既定的组织和存储方式下，增删查改各需要付出怎样的代价。Pascal语言之父Nicklaus Wirth曾凭借一个极简的公式摘得图灵奖的桂冠：算法 + 数据结构 = 程序（Algorithm + Data Structures = Programs）。这个公式之所以能成为计算机科学的经典论断，正是因为它一针见血地指出了一个事实——数据结构与算法不是程序的附属品，而是程序本身的骨与血。我们编写的每一行代码，归根结底都是在某种数据结构之上执行某种算法，二者合一，才构成了一个完整的程序。

1.1.3 勿在浮沙筑高台

也正因如此，古人有言"勿在浮沙筑高台"。如果把编程能力比作一座建筑，数据结构与算法就是地基下的桩。框架的更迭、语言的流行都是地表之上的风景，它们可以日新月异，但地基不稳的建筑注定经不起时间的考验。只有掌握了扎实的数据结构与算法功底，你对程序的理解才不会停留在"能跑就行"的表面，而是真正知道它为什么快、为什么稳、为什么在这个场景下应该这样设计而不是那样设计。更重要的是，当你把这层根基打牢之后，再去学习任何新的系统、框架或编程语言，你都会发现自己可以做到高屋建瓴、势如破竹——因为万变不离其宗，底层的数据组织逻辑和算法思维是相通的，变化的只是语法和API的外衣。

1.2 数据结构与算法的应用

说到这里，容易产生一个疑问：数据结构与算法在实际开发中真的用得到吗？

这种困惑其实非常普遍。只要是接触过编程的人，多多少少都听说过数据结构与算法，甚至能随口说出几种耳熟能详的结构名称；很多计算机专业的同学在大学里也确实修过《数据结构》这门课。但一旦进入日常的学习和工作，大家却感觉自己很少直接用到它们，仿佛数据结构只是一个存在于课本和面试题中的概念，和真实的业务代码隔着一层纱。然而事实恰恰相反——数据结构与算法不是用得少，而是无处不在，只是它们大多藏在每天都在使用的工具的底层，我们没有意识到罢了。

1.2.1 系统、语言、框架源码中的数据结构与算法

不妨以我们最熟悉的前端领域为例来看看这种"隐身"有多彻底。

（1）你写的每一行JSX最终会被解析成一棵AST（抽象语法树），这是树结构；

（2）浏览器把你的HTML渲染到屏幕上，依赖的是DOM Tree，这也是树结构；

（3）JavaScript引擎管理异步任务的方式——微任务队列与宏任务队列——是队列结构；

（4）V8引擎内部存储对象属性用的是哈希表结构。

再往上看框架这一层，Vue的模板编译、React的Fiber调度、Webpack的模块依赖解析，源码中随处可见栈、队列、树乃至图（Graph）的身影。也就是说，无论是操作系统本身、编程语言的运行时引擎，还是我们日常开发中依赖的各种框架，它们的底层实现都是由数据结构与算法层层搭建起来的。想读懂Vue或React的源码，想理解Webpack打包的真实流程，甚至只是想搞清楚一个异步Bug为什么会出现，最终都绕不开对数据结构的理解。它不是一个简单可选的加分项。

1.2.2 Vue.js源码中的数据结构

1. Vue3调度器中的队列结构

以下这段代码来自Vue3运行时核心（runtime-core）中的调度器模块。在Vue3中，当响应式数据发生变化时，并不会立即触发组件的重新渲染，而是通过queueJob函数将更新任务统一推入一个队列中，然后由queueFlush在微任务时机（通过resolvedPromise.then(flushJobs)）一次性批量执行。这种设计避免了同一个Tick内多次数据变更导致的重复渲染，是Vue3性能优化的关键一环。核心代码如下：

▼
ts
复制代码
export function queueJob(job: SchedulerJob) {
  if (
    !queue.length ||
    !queue.includes(
      job,
      isFlushing && job.allowRecurse ? flushIndex + 1 : flushIndex
    )
  ) {
    if (job.id == null) {
      queue.push(job)
    } else {
      queue.splice(findInsertionIndex(job.id), 0, job)
    }
    queueFlush()
  }
}

function queueFlush() {
  if (!isFlushing && !isFlushPending) {
    isFlushPending = true
    currentFlushPromise = resolvedPromise.then(flushJobs)
  }
}

这段代码体现的是典型的队列（Queue）结构。queue是一个数组，通过queue.push(job)实现入队操作，而flushJobs在执行时会从头到尾依次取出任务处理，符合队列先进先出（FIFO）的基本特征。但它又不是一个纯粹的简单队列——当job.id存在时，会通过findInsertionIndex找到合适的位置并用splice插入，这实际上赋予了队列按id排序的能力，使其具备了优先级队列的特性，保证了父组件的更新一定先于子组件执行。此外，queue.includes的去重检查也保证了同一个任务不会被重复入队，这是对基础队列结构的工程增强。

2. Vue3响应式系统中的栈结构

这段代码来自Vue3响应式模块（reactivity）中的副作用追踪系统。Vue3在收集依赖时，需要一个shouldTrack标志来控制当前是否处于"可追踪"状态。但在嵌套effect的场景下，内层effect可能需要暂停追踪，执行完毕后又需要恢复到外层effect的追踪状态。trackStack就是用来保存和恢复这些嵌套状态的。核心代码如下：

▼
ts
复制代码
export let shouldTrack = true
const trackStack: boolean[] = []

export function pauseTracking() {
  trackStack.push(shouldTrack)
  shouldTrack = false
}

export function enableTracking() {
  trackStack.push(shouldTrack)
  shouldTrack = true
}

这段代码体现的是经典的**栈（Stack）**结构。trackStack虽然底层是数组，但它的使用方式严格遵循后进先出（LIFO）的栈操作规范：每次暂停或开启追踪时，先将当前的shouldTrack状态通过push压入栈顶保存，然后修改当前状态；当嵌套的effect执行完毕需要恢复时，只需从栈顶pop出上一层的状态即可。这和函数调用栈的原理一模一样——每进入一层嵌套就压栈保存现场，退出时弹栈恢复现场。栈结构在这里完美匹配了"嵌套进入、逆序退出"的场景需求。

3. Vue3编译器中的状态栈

这段代码来自Vue3编译器模块，用于解析模板表达式中的成员访问路径（如obj[key]或obj.fn()中的括号和方括号嵌套）。编译器在逐字符扫描表达式时，需要追踪当前处于哪种词法状态——是在成员表达式中、方括号内、还是圆括号内。当遇到[时，需要保存当前状态并切换到"方括号内"状态；当匹配到]时，再恢复之前的状态。核心代码如下：

▼
ts
复制代码
let state = MemberExpLexState.inMemberExp
let stateStack: MemberExpLexState[] = []
let currentOpenBracketCount = 0
let currentOpenParensCount = 0

for (let i = 0; i < path.length; i++) {
  const char = path.charAt(i)
  switch (state) {
    case MemberExpLexState.inMemberExp:
      if (char === '[') {
        stateStack.push(state)
        state = MemberExpLexState.inBrackets
        currentOpenBracketCount++
      } else if (char === '(') {
        // ...
      }
  }
}

这段代码同样体现了栈（Stack）结构，但应用场景完全不同。这里的stateStack是一个状态栈，用于处理括号嵌套这类天然具有递归结构的语法解析问题。每当遇到一个左括号[，当前的词法状态被push压入栈中，然后切换到新的状态；当遇到对应的右括号]时，从栈顶pop出之前保存的状态进行恢复。这和我们在数据结构课程中学习的经典应用——"括号匹配"——本质上是同一个问题。编译器需要处理的括号可能层层嵌套，而栈结构的后进先出特性天然保证了最内层的括号最先被匹配，完美契合了嵌套解析的需求。

概括来看，Vue3源码中仅这三个片段就涉及了队列、优先级队列、栈三种数据结构，分别对应了调度排队、优先级控制、嵌套状态管理三类问题。

1.2.3 React、Webpack源码中的数据结构

React、Vite源码中也有大量的体现，在1.2.2小节中，已经简单概述Vue3源码中所使用到的数据结构。与Vue3同级别热度的React和Vite自然也包含大量的数据结构的代码与思想，这里不再展示。

1.2.4 Homebrew作者被Google拒绝

数据结构与算法的重要性不仅体现在日常开发中，在职业发展层面同样是一道绕不过去的关卡。无论是国内的互联网大厂还是海外的科技巨头，中高级岗位的面试几乎都会将数据结构与算法作为核心考察项。

有一个在程序员圈子里广为流传的故事：Mac上那款几乎人人都用的包管理工具Homebrew，它的作者Max Howell曾经去Google面试，结果被要求手写一道"反转二叉树"的算法题——这道题我们在后续的课程（第5章）中也会讲到，并不算特别复杂。但他没有写出来，最终被Google拒绝了。Google拒绝Homebrew作者如图1-1所示。

图1-1 Google拒绝Homebrew作者

这件事在当时引发了不小的争议，很多人为之唏嘘：一个写出了被全球数百万开发者依赖的工具的人才，竟然因为一道算法题而被拒之门外。但抛开情感层面的感慨，这件事从侧面清晰地反映了一个现实：大厂对数据结构与算法的重视程度远超大多数人的想象。它们之所以执着于此，并不是为了刁难候选人，而是因为在真实的大规模系统中，一个不恰当的数据结构选择或者一段低效的算法，在百万级、千万级的数据量面前会被无限放大，直接转化为性能瓶颈甚至线上事故。所以与其把算法面试看作一道门槛，不如把它看作行业在用最直接的方式告诉你：这项能力，是真的重要。

1.2.5 互联网大厂、高级岗位面试

站在企业的角度来看，这种重视其实非常合理。面试的时间是有限的，企业需要在短短几十分钟内判断一个人的能力水平和未来的成长潜力，而数据结构与算法恰恰是最高效的考察手段。

一个能把数据结构与算法掌握扎实的开发者，对业务逻辑的把握通常不会有问题，对系统的设计也会更加合理，写出的代码自然更加高效。它不是唯一的评判维度，但确实是最能体现一个人编程内功的硬性指标。这也是为什么很多想要进入大厂的同学会去刷LeetCode——但现实往往是，大多数人打开题目就觉得晦涩难懂，看着编辑器不知道从何下手。

根本原因不在于题目本身有多难，而在于缺乏系统的数据结构与算法基础。没有这层基础，每一道题都是孤立的谜题；而一旦你系统地掌握了常见的数据结构和对应的算法思维，这些题目之间的内在联系就会浮现出来，融会贯通之后，面试时遇到相关问题自然可以对答如流。

从更长远的视角来看，学习数据结构与算法的价值远不止于通过面试。我们反复强调过，所有编程的最终目的都是处理数据，而数据结构与算法正是一门专门讲解数据应该如何存储、组织和操作的课程。系统地学习它，本质上是在训练你面对复杂数据时的逻辑思维能力和代码组织能力——当你遇到一个棘手的业务场景时，你会本能地去思考用什么样的结构来承载数据、用什么样的策略来处理数据，而不是只会写出一堆嵌套循环然后祈祷它能跑通。

更重要的是，这种能力是跨领域、跨语言的通行证。如果你未来想从前端转向后端、从业务开发转向算法工程师，甚至进入人工智能、区块链这些更前沿的领域，你会发现所有编程思想的底层逻辑都是相通的，变化的只是用哪种语言去处理数据而已。而数据结构与算法，正是这一切共通之处的基石。

1.3 如何学习数据结构与算法？

说了这么多数据结构与算法的重要性，接下来一个很现实的问题就摆在面前了：怎么学？坦白讲，数据结构与算法在大多数人心中的印象就是晦涩难懂、复杂抽象，学起来门槛不低。市面上常见的学习途径大致有四种——高质量文章、书籍、LeetCode刷题、视频课程——它们各有优劣，适合不同阶段的学习者。

第一种是通过高质量的技术文章来学习。文章的优势在于获取成本低、阅读灵活，你可以利用碎片时间快速了解某个数据结构的核心思想，而且优秀的文章往往会结合实际场景来讲解，读起来不会太枯燥。但问题也很明显：文章天然是碎片化的，一篇讲栈、一篇讲队列、一篇讲树，它们之间缺乏系统的串联和递进关系。如果你只靠文章来学，很容易陷入"每个都看过、每个都似懂非懂"的状态，知识点之间形不成体系，遇到综合性问题时依然无从下手。

第二种是看书学习，比如经典的《算法导论》《数据结构与算法分析》等。书籍最大的优势在于体系完整、论述严谨，一本好书会从最基础的概念出发，按照合理的知识递进顺序带你走完整条学习路径，这是任何碎片化内容都无法替代的。但书籍的缺点同样突出：经典教材往往偏学术化，语言抽象、公式密集，对于没有太多基础的学习者来说阅读门槛很高，很多人买回来翻了几十页就放在书架上吃灰了。此外，书籍是静态的，你在阅读过程中如果遇到理解障碍，它无法像一个老师那样换一种方式给你重新解释。

第三种是直接上LeetCode刷题。LeetCode的好处是实战性极强，每一道题都是一个具体的问题，你必须真正写出代码、通过测试用例才算完成，这种即时反馈机制对于巩固知识和锻炼编码能力非常有效。但LeetCode有一个致命的前提条件：你需要先具备一定的数据结构与算法基础。如果你连基本的数据结构都还没有搞清楚就直接去刷题，面对的大概率是一种"打开题目→完全没有思路→看答案→觉得好像懂了→换一道题→又不会了"的死循环。刷题是巩固和提升的手段，而不是从零开始的入门方式。

第四种是通过视频课程来学习。视频课程的优势在于它综合了前面几种方式的长处：既有书籍般的系统性和完整的知识递进，又比书籍更加直观——老师可以通过动画演示、手动推演、画图讲解等方式把抽象的概念变得具体可感，大大降低了理解的门槛。同时，好的课程通常也会穿插代码实战和经典题目的讲解，帮助你在学完理论后立刻动手练习。当然，视频课程也并非完美：它需要投入相对集中的时间，学习节奏由讲师控制而非自己掌握，而且市面上课程质量参差不齐，选择一门真正优质的课程本身就需要一定的甄别能力。

总的来说，最理想的学习路径是将这几种方式结合起来：以系统的视频课程或书籍作为主线建立完整的知识框架，在学习过程中辅以高质量文章来拓展视野和加深理解，最后通过LeetCode刷题将所学知识转化为真正的解题能力和编码肌肉记忆。

在本系列文章中，我们会从常见的数据结构与算法开始学习，过渡到高阶的数据结构与算法，对应内容的思维导图如图1-2、图1-3所示。文章采用层层递进的过渡写法，成体系梳理数据结构与算法的学习路径，内容几十万字且图文并茂（量大管饱），并且有对应开源的课程视频，在最后还会带大家到LeetCode上面刷题。PS：想要一起学习的可以微信联系：coderwhy666。

图1-2 常见数据结构与算法

图1-3 高阶数据结构与算法

1.4 什么是数据结构？

铺垫了这么多，我们终于要回到最根本的问题了：到底什么是数据结构与算法？你可能会期待我给出一个权威的官方定义，但有趣的是——它并没有一个被所有人统一认可的标准定义。

这并不是因为它不够重要，恰恰相反，正是因为它太过基础、太过底层，就像你很难给"数"或者"语言"下一个人人满意的定义一样，越是根基性的概念，越难用一句话框死它的边界。不过没关系，虽然没有一锤定音的官方说法，我们完全可以把"数据结构与算法"拆开来，分别去理解这两个词各自指向什么。搞清楚了"数据结构是什么"和"算法是什么"，再把它们合在一起，你自然就会对这门学科形成一个清晰而完整的认知。接下来，我们就一个一个来看。

1.4.1 数据结构的定义

我们先来看数据结构。虽然没有官方定义，但学术界有几种被广泛引用的说法。《数据结构、算法与应用》一书中的表述是：数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系，这些联系可以通过定义相关的函数来给出。《数据结构与算法分析》则更加精炼：数据结构是ADT（抽象数据类型）的物理实现。而中文维基百科给出了一个相对通俗的版本：数据结构是计算机中存储、组织数据的方式，通常情况下，精心选择的数据结构可以带来最优效率的算法。

这三种定义各有侧重，第一种强调的是数据元素之间的"联系"以及用函数来描述这些联系，偏向于形式化的数学视角；第二种强调的是数据结构与抽象数据类型之间的关系，即先在逻辑层面定义"我需要什么操作"，再在物理层面决定"我如何实现这些操作"；第三种则最为直白，直接指向了数据结构的核心关切——存储和组织。但无论哪种说法，它们最终都收敛到了同一个本质上：数据结构就是在计算机中存储和组织数据的方式。

这句话虽然简短，却值得拆开来细品。"存储"解决的是"数据放在哪里"的问题，"组织"解决的是"数据之间以什么样的关系彼此关联"的问题。可以用一个很直观的类比来理解：摆放图书。

1.4.2 如何摆放图书？

如果是在自己家里，书也没有很多，我们大可以直接叠在一起或者随意拜访，就算想拿，也很快就能找到。在家的书籍摆放如图1-4所示。

图1-4 在家的书籍摆放

想象一个庞大的图书馆，里面存放着海量的书籍。如果你只是把书一股脑地堆在地上，那存储的问题虽然解决了——书确实"放进去"了——但当你想找某一本书的时候，就只能一本一本翻过去，效率极其低下。而一个好的图书馆一定会有一套组织方式：按学科分区、按作者姓氏排列、用索引编号建立检索目录。这套组织方式的目的，就是让你不仅能把书放进去，还能在需要的时候高效地把书取出来。数据结构做的事情与此完全一样——面对计算机中庞大的数据，它要解决的核心问题就是：如何存储这些数据，以及如何组织它们之间的关系，使得后续的查找、插入、删除、修改等操作都能以尽可能高效的方式完成。

图1-5 图书馆的书籍摆放

我们继续用图书馆的例子来把这个问题说得更透彻一些。假设你是一名图书馆管理员，你日常要处理的核心操作只有两个：

第一，新书到了怎么插入书架？

第二，读者来了怎么找到指定的那本书？

就是这么简单的两个操作，因为数据组织方式的不同，效率可以天差地别。

最简单粗暴的方式是随便放——哪里有空位就往哪里塞。这种方式下，插入操作当然极其高效，一步到位，毫无心智负担。但代价是什么？当读者来找某一本书时，你只能从第一个书架开始一排一排、一本一本地扫过去，运气好也许很快就找到了，运气不好就得翻遍整个图书馆。书越多，这个过程就越痛苦。这就是典型的"写入快、读取慢"——你为了插入时的省事，把所有的复杂度都转嫁到了查找上。

稍微聪明一点的方式是按照书名的拼音字母顺序排放。这样一来，查找操作就高效多了——你不再需要从头翻到尾，而是可以用二分查找法：先看中间位置的书，判断目标在左半边还是右半边，然后不断缩小范围，几次就能定位到。但插入操作就没那么轻松了：假设新到了一本《阿Q正传》，你需要按照字母顺序找到它应该在的位置，然后把后面的书全部往后挪一个位置，才能把它插进去。书架上的书越多，这个"挪位"的成本就越高。

更进一步的方式是先把书架划分成几个大的区域，按照书籍的类别分区存放——文学区、哲学区、计算机区——然后在每个类别内部再按照字母顺序排列。这样无论是插入还是查找，第一步都是先确定类别，一下子就把范围缩小到了一个区域内，然后在这个小范围里再用二分查找来定位。插入时需要挪动的书变少了，查找时需要扫描的范围也小了，两个操作的效率都得到了提升。

三种方式，同样的书、同样的书架，仅仅因为摆放规则不同，操作效率就产生了本质的差异。这个类比揭示了一个至关重要的结论：解决问题的效率，与数据的组织方式直接相关。而计算机中存储的数据量相较于图书馆来说要庞大得多，数据的种类也远比书籍复杂——数字、文本、图像、关系、状态……面对如此海量且多样的数据，以什么样的方式来存储和组织它们，才能在后续使用时更加方便、更加高效？这，就是数据结构需要考虑的核心问题。

1.4.3 常见的数据结构

回到计算机的世界中来，道理是完全一样的。计算机中常见的数据结构种类不少：数组、栈、队列、链表、哈希表、树、堆、图等等。每一种都有其对应的应用场景，而不同数据结构在不同操作上的性能表现也各不相同。有的查询性能极快，有的插入速度出色，有的在头尾两端的操作特别高效，有的擅长范围查找，有的允许元素重复而有的要求元素唯一。

没有哪一种数据结构是万能的"银弹"，在实际开发中选择哪种结构，永远取决于你当前面对的具体需求。这也正是数据结构这门课程存在的意义：不是让你死记硬背每种结构的定义，而是让你在面对不同场景时，能够做出最合理的选择。如果只需要死记硬背，那直接查字典就好了。

这里需要特别强调一点：数据结构与编程语言无关。无论使用的是JavaScript、Java、C++、Python还是其他任何语言，它们都会直接或间接地用到上述这些数据结构，区别只在于语言层面是否内置了对应的实现。有些同学可能会疑惑：我学JavaScript这么久，为什么好像只见过数组，几乎没有接触过其他数据结构？

这其实不是因为JavaScript中不需要这些结构，而是因为很多数据结构只有在更高阶的开发场景中才会被显式使用——比如设计框架、编写底层库、优化核心算法的时候。甚至有些数据结构在JavaScript中根本就没有原生提供，需要我们自己从零去实现。

这也恰恰引出了我们这门课程的核心理念：我们不是要讲这些数据结构"怎么调用"——那是API程序员的思维方式，查一查文档就能搞定。我们要做的是从底层出发，搞清楚每一种数据结构是如何设计、如何实现的，在这个基础之上再去讨论如何使用。只有理解了内部的实现原理，你在使用它们时才不是盲目的，你的选择才有依据，你的优化才有方向。了解真相，你才能获得真正的自由。

1.5 什么是算法？

理解了数据结构之后，我们再来看另一半——算法。在第11章的排序算法文章中，我们可以感受面对同一组数据，冒泡排序、快速排序、归并排序的执行效率可以相差几个数量级。这说明在解决问题的过程中，不仅仅数据的存储和组织方式会影响效率，你选择用什么样的步骤和逻辑去处理这些数据，同样深刻地决定着最终的效率。而这里所说的"步骤和逻辑"，就是算法。

1.5.1 算法的定义

那么，算法到底是什么？从严格的定义来说，算法是一个有限的指令集合，它具备几个基本特征：首先，每条指令的描述不依赖于任何特定的编程语言，也就是说算法是一种抽象的逻辑过程，你可以用JavaScript实现它，也可以用Java、C++或者Python实现它，变化的是语法，不变的是逻辑本身；其次，算法可以接受一些输入，在某些情况下也可以没有输入，但它一定会产生输出——也就是说它必须要解决某个问题、给出某个结果；最后，也是非常关键的一点，算法必须在有限的步骤之后终止，一个永远不会停下来的过程不能被称为算法。

1.5.2 算法的示例

不过，如果觉得这个定义还是有些学术化，我们可以回到Algorithm这个单词本身来理解。它的本意其实非常朴素——就是解决问题的办法和步骤逻辑。电灯不工作的解决算法如图1-6所示，这就是一种解决问题的办法和步骤逻辑。

图1-6 电灯不工作的解决算法

1.6生活中的数据结构与算法

前面我们用图书馆的例子说明了数据的组织方式如何影响效率，但数据结构与算法的身影远不止于此，生活中到处都能找到它们的影子。我们再来看两个更加贴近日常的例子，帮助大家进一步建立直觉。

1.6.1 快递员的快递

第一个例子是取快递。大家平时都收过快递，现在很多快递通常不会直接送到家里，而是放在某个固定的代收点，让你自己去取。当你走到代收点，一般会遇到两种情况：

（1）自己动手在海量的快递包裹中翻找。

（2）快递员让你报出名字，由他来帮你找。

自己翻找本质上就是线性查找——从第一个包裹开始，一个一个挨着看，直到找到为止。

虽然我们人眼处理视觉信息的速度很快，眼观六路也许很快就能扫到，但这毕竟不是一种可靠且高效的方式，包裹一旦多起来就很痛苦。更好的方式应该是让快递员帮你找。而如果这个快递员稍微动动脑筋，他会提前对快递做一轮分类——比如按照收件人姓氏把包裹分成不同的区域。这样一来，你只需要报出名字，他就能根据姓氏立刻锁定到某一个小区域，再在这个小范围里快速找到你的包裹。你看，同样是"找快递"这件事，有没有对数据进行合理的组织，效率完全是两个量级。这就是数据结构思维在生活中最朴素的体现。

1.6.2 找出线缆出问题的地方

第二个例子更加直观地展示了算法优劣带来的效率差距。

假设上海和杭州之间有一条高架线缆，全长1,000,000米，某一天其中有一米的线段出现了故障，现在需要你想办法定位到这个故障点。最直觉的方式是线性查找：从上海这一端的起点开始，一米一米地排查过去，最终一定能找到故障位置。但如果故障恰好在杭州那一端呢？你就需要排查整整1,000,000次，这是最坏的情况；即便平均下来，也需要大约500,000次。

现在换一种思路——二分查找：先从线缆的中间位置开始检测，判断故障出在上海到中间点这一半，还是中间点到杭州这一半；确定之后，在故障所在的那一半中再取中间点继续检测，每一次都将排查范围缩小一半。用这种方式，最坏的情况下需要多少次才能定位到故障？答案是大约20次。这个数字是怎么来的呢？就是log₂(1,000,000) ≈ 20。从500,000次到20次，同一个问题，仅仅因为算法不同，效率就产生了如此天壤之别。

这两个生活中的小例子，一个侧重于数据结构，一个侧重于算法，但它们共同指向了同一个结论：解决问题的办法有很多，但好的数据组织方式配合好的算法，与差的方案之间的效率差距，往往不是百分之几十的优化，而是成千上万倍的量级碾压。那么，如何科学地衡量一个算法到底有多快、多慢？这就涉及到我们后续会专门讲解的大O表示法，这里先留一个悬念，后面再展开。