7. 数据结构与算法

1.前言

编程的本质，实际上就是在尽可能高效的存储、使用数据。

而数据结构便是数据在计算机中的存储方式，至于算法，就是如何去高效的利用数据。

对于计算机来说，由于其底层内存、硬盘的物理组成形式为一块内存挨着一块内存，最终操作系统用内存地址来标注内存的位置，因为其最基本的结构就是线性结构。

比如我们存一系列数据：1、2、3、4、5。将其存入到内存中，那么最直接的形式就是这五个数字挨个写入相邻地址的内存块中。

而读取的时候也能顺序的根据地址读取这五个数据。

这便是最基本的数据结构：数组。

至于其它类型的数据结构，都是在此之上进行组织的，本文会循序渐进、从整体上的对这些常见的数据结构、算法特性进行基本的介绍。

如果你想要更加详细的了解这方面的知识，那么可以参考：Hello 算法

2.数组

正如前面所说，数组是最基本的数据结构，同时也是内存物理结构的直观显示。

正因为连续，所以它可以非常方便的取数据，只要你知道了其中一个元素的位置，那么直接在该位置上加减数字就是该元素前面、或者后面的元素所在的位置，取元素的效率是非常高的。

但又因为它是连续的，这导致如果我们想要在其中间插入一个元素，就需要先将该位置之后的元素全部后移一位，然后才能插入，会导致插入数值的效率变得缓慢。

注意，这里的“后移”，实际上就是将所有元素向后一位进行复制。

所以对于数组来说，它适用于下面的场景：

1. 大多数只在尾部位置添加元素/甚至不需要插入数据
2. 需要经常随机位置取元素、或者遍历元素。

在C语言中，我们可以用malloc分配一块连续的内存作为数组使用，后续的C++中，存在现成的Vector库，这是官方封装好的数组实现，可以直接给我们使用。

同样的，其它高级语言都会有自己的官方库实现，所以大多数并不需要我们自己去实现这么一个数组结构，但在你前期的学习过程中，推荐你自己去实现一个方便好用的抽象数组结构，就能更好的理解其原理了。

3.链表

正因为上述数组的缺点，所以又出现一种叫做链表的结构，它解决了数组的缺陷，但又拥有了它自己的缺陷。

与数组相反，链表的每个元素并不是在内存中连续的，它靠在每个元素中记录上一个、下一个元素的地址，从逻辑上实现类似于数组的结构：

由于我们访问元素是通过地址实现的，所以列表的原理便是，每个元素存储上/下一个元素的地址。

此时如果我们想要获取第三个元素的值，那么我们就只能从第一个元素挨个找过去：第一个元素内存放第二个元素的地址，第二个元素内存放第三个元素的地址。

绝大多数情况下，我们只会在链表结构创建的时候，保存第一个元素、乃至最后一个元素的地址。

这便导致了，我们无法像数组那样，可以随机访问某个元素了，只能从头/尾挨个查过去。

但同样的，这种结构利于插入新的元素，此时无论你想要在哪个位置中插入新元素，都只需要新开辟一块内存，将前一个元素存放下一个元素的地址改为新内存，后一个元素存放前一个元素的地址改为新内存。

而我们新内存就需要存放前一个元素、后一个元素的地址。

此时你会发现，我们在任何一个位置插入元素，最多只会影响相邻的两个元素数组，而不会像前面数组那样，将所有后面的元素都进行后移复制。

因此，链表适用于以下场景：

1. 需要频繁插入数据
2. 不需要频繁的进行随机位置元素访问操作

链表也有单链表和双链表之分，上面我们介绍的都是双向链表，也就是你既可以从头到尾遍历，也可以从尾到头遍历。

而单向链表则是每个元素只保留它后一个元素的地址，不保留前一个元素的地址，这可以节省空间，但也导致只能从头到尾进行遍历。

4.栈

前两种是最基本、最底层的程序存储数据方式，而后面要介绍的便是相对抽象的概念。

第一种便是栈：