算法+数据结构（第05篇）走下神坛吧！算法

阅读本文需要5分钟

引言

在本系列第一篇文章《走下神坛吧！算法》中提到了：

1. 算法的作用对象是数据结构
2. 数据结构的来源既有硬件维度也有软件维度

把项目或者工程看作是大楼的话，那么算法就是建造大楼的具体施工流程和方法，数据结构就是砖块等原材料。

常言道：“工欲善其事必先利其器”，既然要研究算法，那么首先就要把它操作的“原材料”一一搞清楚。从本篇文章起，将逐一来讲解各“原材料”的历史来源、使用方法与应用场景。

1. 数组就是带电梯的小高层

数组的形式：<数据类型> 数组名 [数组长度]

形象地讲，数组就是带电梯的小高层。每一个楼层就是数组的一个元素。数组元素的下标，就相当于楼层号然后按电梯楼层号。

1.1 访问数组元素

你按下楼层号（输入下标），电梯就直接把你送到对应的楼层（访问对应的数组元素），就这么简单！

从这里可以看出数组的一个最大优势：随机访问相当简单、相当爽！

1.2 添加数组元素

想想竣工的大楼，如果你要加楼层，怎么加？当然是在顶楼上继续加喽！

顶楼就是数组的末尾元素，所以向数组中添加元素，就是在数组的尾巴上添加该元素。

当然楼层是要占据物理空间的，对应到计算机语言，就是要分配内存。

看到这里，也许调皮的同学会问了：那能不能不在尾巴上添加，而在中间添加呢？

你见过竣工的大楼，在中间加楼层的吗？：）

变通的办法，还是在顶楼加，然后让从欲插入的楼层开始的住户依次往上一楼层搬家，腾出当前层给你这个调皮的同学住！：）

1.3 删除数组元素

你见过竣工的大楼，在中间“炸掉”某楼层的吗？：）

结果肯定是楼塌啦！

正确的做法：

从这里可以看出数组的一个最大弱点：添加与删除元素有点烦！

2. 链表就是单入口小火车

链表分为单向链表与双向链表。两者的区别：

单向链表从当前节点只能访问它的下一个节点，而双向链表可以从当前节点同时访问它的前一个节点和后一个节点。

2.1 访问链表节点

先来看看单向链表的“小火车”：

每节车厢就相当于链表的一个节点。

如果要到3号车厢，先进入1号车厢（入口车厢），再从1号车厢的后向挂钩到达2号车厢，最后从2号车厢的后向挂钩到达3号车厢。

因为没有前向挂钩，所以从3号车厢无法到达2号车厢；同理，从2号车厢也无法到达1号车厢。

从这里可以看出链表的一个最大弱点：随机访问元素有点烦！

再来看看双向链表的“小火车”：

因为有前向挂钩，所以从3号车厢可以到达2号车厢；同理，从2号车厢也可以到达1号车厢。

2.2 添加链表节点

先来看看单向链表的“小火车”如何添加新“车厢“（链表节点）：

有两种情况：

1. 将新“车厢”加到火车尾巴上

2. 将新“车厢”插入到车节中间

第一步：“系住”后节车厢

为啥要“系住”呢？因为车厢脱钩之后就失控了啊：）

第二步：分离

第三步：与前一节车厢挂钩

第四步：与后一节车厢挂钩

在这一步其实可以真正看出第一步中“系住”的目的：）

不就是为了让4号车厢的前向挂钩找到3号车厢和2号车厢吗？：）

如果不提前“系住”，那么一旦2号车厢与3号车厢分离，我们就再也没有有效办法到达3号车厢了。

那么如何实现“系住”呢？用变量保存要“系住”的“车厢”（链表节点）位置。

对于3号车厢：用一个变量保存3号车厢的位置即可。

看到这里，相信对于单向链表的节点添加操作你再也不会忘记了：）

双向链表的节点添加操作与上类似，无非就是多了一个前向挂钩的处理。

2.3 删除链表节点

假如现在要去掉3号车厢，那么怎么做呢？

第一步：“系住”前节车厢

第二步：前向分离

第三步：“系住”后节车厢

第四步： 后向分离

第五步：前后节车厢挂接

双向链表的节点删除操作与上类似，无非就是多了一个前向挂钩的处理。

从这里可以看出链表的最大优点：增删元素相对于数组容易！

END