怎么工作 数组和链表 有什么区别

挨在一起的储物柜：数组

上一课我们看到，每种容器的形状都不一样。其中最简单的形状就是数组：可以把它想成一个储物柜，带编号的格子紧紧挨着排成一排。
格子的编号通常从 0 开始，像 0 号、1 号、2 号这样。所有格子大小一样、一个挨一个，所以从起点加上编号个格子的大小，就能马上算出那个格子在哪里。

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

一点编号，那个格子马上就亮了。格子并排挨着，几号格子都能一步到达。格子有十个也好，一百万个也好，花的时间都一样。
像这样凭编号马上取出，叫作快速访问，这是数组最大的长处。可是，格子一定要挨在一起吗？要是散开放，会怎么样？

散落的储物柜：链表

链表不把格子挨着放，格子散落在内存各处。那么，顺序怎么串起来呢？每个格子贴一张纸条，纸条上写着下一个格子在哪里。
于是从第一个格子看纸条走到下一个格子，再看那张纸条走到再下一个。格子靠纸条一个接一个连起来，所以这种形状叫链表。

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

照着纸条走，散落的格子连成了一串。和凭编号直接跳过去的数组不同，链表要一边读纸条，一边一格一格地往前走。
看起来有点麻烦，但这种散开的结构有个意想不到的长处。是什么，很快就会看到。

快速访问 vs 慢速访问

现在来比一比。假设要取出第五个格子。数组报出编号就完事了，格子挨着，一步就跳过去。
链表做不到。得从第一个格子开始照着纸条走，一格、两格、三格，一路数着往前。所以要找的格子越远，花的时间越长。

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

差别很明显。数组点一次就到了，链表点了好几次才勉强到。说到取出东西，凭编号直接跳的数组快得多。
那么，数组总是更好吗？不是的。下一个场景里，链表大显身手的时刻来了：往中间插东西的时候。

往中间插入

这次往一排的正中间插进一个新格子。对链表来说很容易：把前一个格子的纸条改成指向新格子，再让新格子的纸条指向原来的下一个格子就行。
只改写两张纸条，其余的格子一个都不用动。就算有一百万个格子，要改的纸条也只有两张。

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

数组怎么样？要在中间腾出位置，就得把后面的格子一个个全都往后推，因为格子挨着，没有空位。链表两张纸条就搞定了。
所以，经常往中间插入的事，用链表方便得多。快速访问归数组，轻松插入归链表：得到一样，就要让出另一样。

小结

用一句话概括：数组是带编号的格子紧挨着排成的储物柜，所以凭编号马上能取出。链表是散落的格子各自贴着写有下一个格子位置的纸条，所以往中间插入很容易。
取第五个时数组快，往中间插时链表方便。看自己最常做什么来挑。

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

现在你知道，同样的东西，装法不同，擅长的事也就不同。数组和链表是挑选容器形状的第一个岔路口。
下一课讲两种特别的容器：只在一头放进取出的栈，和只能按排队顺序取出的队列。