数据结构与算法之美 – 数组与链表

为什么要学数据结构和算法？

我们的目的是建立时间复杂度、空间复杂度意识，写出高质量的代码，能够设计基础架构，提升编程技能，训练逻辑思维，积攒人生经验，以此获得工作回报，实现你的价值，完善你的人生。

掌握了数据结构与算法，你看待问题的深度，解决问题的角度就会完全不一样。

学习数据结构和算法好处：

1. 直接好处是能够有写出性能更优的代码。
2. 算法，是一种解决问题的思路和方法，有机会应用到生活和事业的其他方面。
3. 长期来看，大脑思考能力是个人最重要的核心竞争力，而算法是为数不多的能够有效训练大脑思考能力的途径之一。

如何抓住重点，高效学习数据结构与算法

从广义上讲，数据结构就是指一组数据的存储结构。算法就是操作数据的一组方法。

从狭义上讲，是指某些著名的数据结构和算法，比如队列、栈、堆、二分查找、动态规划等。

数据结构和算法有什么关系呢?为什么大部分书都把这两个东西放到一块儿来讲呢?

这是因为，数据结构和算法是相辅相成的。数据结构是为算法服务的，算法要作用在特定的数据结构之上。 因此，我们无法孤立数据结构来讲算法，也无法孤立算法来讲数据结构。

比如，因为数组具有随机访问的特点，常用的二分查找算法需要用数组来存储数据。但如果我们选择链表这种数据结构，二分查找算法就无法工作了，因为链表并不支持随机访问。

学习重点

1. 复杂度分析，数据结构和算法解决的是如何更省、更快地存储和处理数据的问题，因此，我们就需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。可以这么说，它几乎占了数据结构和算法这门课的半壁江山，是数据结构和算法学习的精髓。
2. 10个数据结构：数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树。
3. 10个算法：递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
4. 学习它的来历、自身的特点、适合解决的问题、实际的应用场景

学习技巧

1. 边学边练，适度刷题
2. 多问、多思考、多互动
3. 打怪升级学习法，自我激励
4. 知识需要沉淀，不要想试图一下子掌握所有

复杂度分析

一、什么是复杂度分析

1. 数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。
2. 因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。
3. 分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。
4. 复杂度描述的是算法执行时间(或占用空间)与数据规模的增长关系。

二、为什么要进行复杂度分析

1. 和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。
2. 掌握复杂度分析，将能编写出性能更优的代码，有利于降低系统开发和维护成本。

三、如何进行复杂度分析

1. 大O表示法

1. 来源

算法的执行时间与每行代码的执行次数成正比，用T(n) = O(f(n))表示，其中T(n)表示算法执行总时间，f(n)表示每行代码执行总次数，而n往往表示数据的规模。 公式中的O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。

2. 特点

以时间复杂度为例，由于时间复杂度描述的是算法执行时间与数据规模的增长变化趋势，所以常量阶、低阶以及系数实际上对这种增长趋势不产决定性影响，所以在做时间复杂度分析时忽略这些项。

2. 复杂度分析法则

• 单段代码看高频：比如循环。
• 多段代码取最大：比如一段代码中有单循环和多重循环，那么取多重循环的复杂度。
• 嵌套代码求乘积：比如递归、多重循环等
• 多个规模求加法：比如方法有两个参数控制两个循环的次数，那么这时就取二者复杂度相加。

四、常用的复杂度级别

多项式阶

随着数据规模的增长，算法的执行时间和空间占用，按照多项式的比例增长。

• O(1)(常数阶)
• O(logn)(对数阶)
• O(n)(线性阶)
• O(nlogn)(线性对数阶)
• O($n^2$)(平方阶)

非多项式阶

随着数据规模的增长，算法的执行时间和空间占用暴增，这类算法性能极差。

• O($2^n$)(指数阶)
• O(n!)(阶乘阶)

数组

数组是一种线性表数据结构。它用一组连续的内存空间，来顺序存储一组具有相同类型的数据。

数组的特点：

• 数组中所有元素的类型都必须相同(都为int、double等)。
• 数组中的元素在内存中都是相连的。
• 数组支持顺序访问和随机访问，下标随机访问的时间复杂度为 O(1)
• 数组的读取速度很快，插入和删除比较困难。

为什么大多数编程语言中，数组要从 0 开始编号，而不是从 1 开始呢?

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移(offset)”。前面也讲到，如果用 a 来表示数组的首地址，a[0] 就是偏移为 0 的位置，也就是首地址，a[k] 就表示偏移 k 个 type_size的位置，所以计算 a[k] 的内存地址只需要用这个公式：

a[k]_address = base_address + k * type_size
复制代码

但是，如果数组从 1 开始计数，那我们计算数组元素 a[k] 的内存地址就会变为：

a[k]_address = base_address + (k-1)*type_size
复制代码

对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于CPU 来说，就是多了一次减法指令。

数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。

不过我觉得，最主要的还是历史原因，C 语言设计者用 0 开始计数数组下标，之后的高级语言都效仿 C 语言，因此继续沿用了从 0 开始计数的习惯。

链表

链表是一种在物理内存上不连续的数据结构。链表通过指针将一组零散的内存块串联在一起。

链表的特点：

• 链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。
• 在链表中添加元素很容易:只需将其放入内存，并将其地址存储到前一个元素中。
• 链表只支持顺序访问。
• 链表的插入和删除速度很快。
• 链表的查询速度很慢，因为必须要一个元素一个元素顺序查找。
• 相比数组只存储元素，链表的元素还要存储其它元素的地址，内存开销相对增大。

常见数组和链表操作的运行时间

	数组	链表
读取	O(1)	O(n)
插入	O(n)	O(1)
删除	O(n)	O(1)

单链表

当链表的每个结点只包含一个指针域时，我们称此链表为单链表。单链表的尾结点指针指向空地址。

常见术语：

• 头指针：指向第一个节点的指针(这个节点可能是头结点，也可能是头元素)。链表中可以没有头结点，但不能没有头指针。
• 头结点：有时候我们会在单链表的第一个元素节点(头元素)之前附设一个节点，称之为头结点。头结点数据域可以不存储任何信息，也可以存储如链表长度等附加信息。
• 头元素：链表中第一个包含有效元素的节点。

循环链表

循环链表是一种特殊的单链表。循环链表的尾结点指针指向链表的头结点，由此，从表中任一结点出发均可找到表中其他结点。

当要处理的数据具有环型结构特点时，就特别适合采用循环链表。

双向链表

双向链表支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点。

双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。

双向链表相比于单链表的优点：

从结构上来看，双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。

在实际的软件开发中，从链表中删除一个数据无外乎这两种情况:

• 删除链表中“值等于某个给定值”的结点;
• 删除给定指针指向的结点。

第一种情况，不管是单链表还是双向链表，为了查找到值等于给定值的结点，都需要从头结点 开始一个一个依次遍历对比，直到找到值等于给定值的结点，然后再通过我前面讲的指针操作将其删除。尽管单纯的删除操作时间复杂度是 O(1)，但遍历查找的时间是主要的耗时点，对应的时间复杂度为 O(n)。总时间复杂度为 O(n)。

第二种情况，我们已经找到了要删除的结点，但是删除某个结点 q 需要知道其前驱结点，而单链表并不支持直接获取前驱结点，所以，为了找到前驱结点，我们还是要从头结点开始遍历链表，直到 p->next=q，说明 p 是 q 的前驱结点。

但是对于双向链表来说，这种情况就比较有优势了。因为双向链表中的结点已经保存了前驱结点的指针，不需要像单链表那样遍历。所以，针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度内就搞定了!

同理，如果我们希望在链表的某个指定结点前面插入一个结点，双向链表比单链表有很大的优势。双向链表可以在 O(1) 时间复杂度搞定，而单向链表需要 O(n) 的时间复杂度。

除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。

如何用链表来实现 LRU 缓存淘汰策略

缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非常广泛的应用，比如常见的 CPU 缓存、数据库缓存、浏览器缓存等等。

缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留?这就需要缓存淘汰策略来决定。常见的策略有三种：先进先出策略 FIFO(First In，First Out)、最少使用策略 LFU(Least Frequently Used)、最近最少使用策略 LRU(Least Recently Used)。

实现思路：

我们维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中，又可以分为两种情况：如果此时缓存未满，则将此结点直接插入到链表的头部；如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。

这样我们就用链表实现了一个 LRU 缓存，是不是很简单?

现在我们来看下该缓存访问的时间复杂度是多少。因为不管缓存有没有满，我们都需要遍历一遍链 表，所以这种基于链表的实现思路，缓存访问的时间复杂度为 O(n)。

时间空间互换思想

缓存实际上就是利用了空间换时间的设计思想。如果我们把数据存储在硬盘上，会比较节省内存，但每次查找数据都要询问一次硬盘，会比较慢。但如果我们通过缓存技术，事先将数据加载在内存中，虽然会比较耗费内存空间，但是每次数据查询的速度就大大提高了。

当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。

如何轻松写出正确的链表代码

1. 理解指针或引用的含义

   将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

2. 警惕指针丢失和内存泄漏

3. 利用哨兵(头结点)简化实现难度

4. 重点留意边界条件处理

   • 如果链表为空时，代码是否能正常工作
   • 如果链表只包含一个结点时，代码是否能正常工作
   • 如果链表只包含两个结点时，代码是否能正常工作
   • 代码逻辑在处理头结点和尾结点的时候，是否能正常工作

5. 举例画图，辅助思考

6. 多写多练，没有捷径

5个常见的链表操作

• 单链表反转
• 链表中环的检测
• 两个有序的链表合并
• 删除链表倒数第 n 个结点
• 求链表的中间结点