这次课程，我们来讲讲基础的数据结构，其中包含了链表，栈，队列等等。这些名词看起来枯燥 但实际上都能从日常生活中找到生动的例子，本文阅读大概需要15分钟。
链表
超市推车
超市里的推车，我们都有一个印象，一个连着一个。当我们取出推车的时候，只需要将连接前面车子的扣子断开即可。
在实际的计算机里面，有一个与此相似的数据结构。叫做链表。
链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。
所以当往链表里面添加数据的时候，只需要修改插入点的指针，删除也类似，请看下面示意图:
添加数据
删除数据
但是当我们在链表中检索某一条数据的时候，必须从头开始检索。
当然除了单项链表，还有较为复杂点的双向链表以及环形链表，用来提高查询速度。
栈
碟子
栈这种数据结构的显著特征是先进后出。比如上面的碟子。放置的时候，我们一个个往上堆，但是取的时候必须从最上面一个开始取。
如下所示：
出栈
入栈
是不是和叠盘子很像？
队列
排队
排队讲究的是先来后到，所以对于队列来说，它的特点就是，先进先出（First In First Out ：FIFO）
入队
出队
要删除数据C，必须要将C前面的A，B 删除完，才行。
队列的查询也和栈类似，不能直接访问中间的数据，必须通过出队将目标数据变成首位之后才能访问。
哈希表
小区的快递柜子
小区的快递柜，当我们收到到货通知的时候，我们会拿到一串六位的数字，但我们并不知道购买的东西是在几排几列的柜子中，当取物品的时候，我只需要输入这六位数字，柜门会自动弹开，最终拿到我们物品。
hash表
哈希表的存储，有两部分组成，分别是KEY 和 VALUE， 比如我们要存储姓名，Value存的是姓名，而Key是根据一定规则（hash函数）生成的hash值。
当我们查找的时候，只需要根据key，就可以检索到对应的value。由于hash表的数据存储不一定是连续的，所以只要你知道key，既可删除对应的value。
所以hash表的特征是存储的灵活性和数据查询的高效性。
但是细心的同学也会发现，如果这个key相同怎么办？
如果key相同，这叫哈希冲突。解决冲突的办法有很多，其中有一种办法叫开放地址法，当检测到冲突，立刻计算出一个候补地址，如果再有冲突，继续计算，直到没有冲突为止。
数组
健身房柜子
健身房的柜子与快递柜不同，我们需要记住柜子的位置。第几排第几列。
数组是线性的存储结构，且有固定的大小，比如数组的名字叫a, 那么数组的第一个位置a[0]，存储这value是4。
数组
数组的查找，我们可以随机访问，比如a[6]，即可以查到90的一个值。
是不是很方便，那数组的删除和添加呢？
添加数据
比如在a[3]之后添加一个99的数据，
第一步，将数组扩容；
第二步，将a[3]之后的数据全部往后挪一个位置；
第三步，在空出来的a[4]位置上放入99这个数据。
删除数据：
删除数据
比如删除a[4]的数据7，
第一步，将a[4]的数据7删除；
第二步，但是a[4]位置还在，故将a[5]之后的数据挨个往前填；
第三步，最后删除多余的空间。
所以数组的删除和添加是不是比较麻烦？主要往中间添加数据或者删除数据，都必须移动它后续的数据。除非你操作末尾的数据。
--------------------------分割线-------------------------------------
小结
数据结构，其实就是数据在内存中的存放方式（比如位置&顺序）。就好比一件东西在容器中的放置方式。不同的数据结构，决定了数据增删改查的效率。不同的数据结构也有不同的使用场景。
不同的数据结构，操作数据的操作对比
| 数据结构类型 | 访问/检索 | 添加/删除 |
|---|---|---|
| 链表 | 慢 | 快 |
| 数组 | 快 | 慢 |
| 哈希表 | 快 | 快 |
| 栈 | 慢 | 慢 |
| 队列 | 较快 | 较快 |
这个的对比是比较粗略的。衡量不同的数据结构优劣，其实有两个维度：时间和空间复杂度。而时间和空间复杂度，会有最坏和平均 两个值，这个后面还会涉及，这里大家只需了解，后续会详解。
参考：
https://zh.wikipedia.org/wiki/%E9%93%BE%E8%A1%A8
https://medium.com/omarelgabrys-blog/data-structures-a-quick-comparison-6689d725b3b0
网友评论