排队收纳，数组和链表

紧挨着的储物柜，数组

前面我们学过，每个容器
都有自己的形状。
其中最简单的形状就是数组。
它是一排带编号的格子
紧挨着排成一行的储物柜。
0号、1号、2号，
每个格子都有自己的编号。
因为格子全挨在一起，
只要知道编号，就马上知道它在哪儿。

点一下编号，直接跳到那个格子。格子挨在一起,凭编号马上找到。

你一点编号，
那个格子马上就亮了。
因为格子并排挨着，
不管几号格子都一下就点到。
像这样凭编号马上取出，
叫做快速访问。
这是数组最大的长处。
可格子非得挨着放吗?
散开放不行吗?

散落的储物柜，链表

链表不把格子挨在一起。
格子散在各处。
那怎么把顺序连起来呢?
给每个格子贴一张纸条。
那张纸条上
写着下一个格子在哪儿的地址。
所以从第一个格子看纸条,
走到下一个格子，再看那张纸条，
走到再下一个格子。

点一下纸条，照着它走到下一个格子。格子虽散，纸条把顺序连起来。

照着纸条走，
散落的格子连成了一行。
和靠编号直接跳的数组不同，
链表得看纸条，
一格一格依次走。
看着是麻烦了点，
可这散落的结构
带来一个意想不到的长处。
那是什么,马上就会看到。

快速访问 vs 慢速访问

现在把两个比一比。
假设你想取第五个格子。
数组只报编号就行。
格子挨着,一下就跳过去。
链表做不到。
得从第一个格子照着纸条，
一格、两格、三格，
依次数着往前走。
所以越远，花的时间越久。

取出第五个。数组一步到位，链表从头一格一格走。比一比点击次数。

差别很清楚。
数组点一下就到，
链表点了好几下才到。
论取出东西，
靠编号直接跳的数组快得多。
那数组就一定更好吗?
不。看下个场景，
链表大放光彩的时刻就来了。
那就是往中间塞东西的时候。

往中间塞进去

这次我们往这行中间
塞进一个新格子。
链表非常容易。
把前一个格子的纸条所指的地方
改成新格子,
再让新格子的纸条
指向原来的下一个格子就行。
只改两张纸条,
其余格子原样不动，就完事了。

往中间插一个新格子。链表只改两张纸条，数组要把后面的格子全推开。比一比各要多少工夫。

数组怎么样?
要在中间腾出位置，
就得把后面的格子一个个全推开。
因为格子挨着，没有空位。
链表那边,两张纸条就完事了。
所以论常往中间插,
链表舒服得多。
快速访问归数组，
轻松插入归链表。
两者是彼此互换的关系。

来理一理

归成一句话，是这样。
数组是带编号、紧挨着的储物柜，
凭编号马上取出,快速访问。
链表是散落的储物柜,
每个挂着下一个格子地址的纸条，
往中间插入很容易。
取第五个时数组快，
往中间塞时链表舒服。
按你最常做什么来选。

依次点要点回顾一下。(紧挨着的储物柜数组 → 散落的储物柜链表 → 快速 vs 慢速访问 → 中间插入)

现在你知道，就算是同样的东西，
按怎么收纳的不同，
擅长的事也不一样。
数组和链表
是选容器形状的第一个岔路。
接下来我们要看的是
只在一端
放进取出的特别容器，
堆叠和排队，一起来看。