【从0到1学算法】 数组和链表

今天讲最基本的数据结构，数组和链表。如果你已经滚瓜烂熟，可以跳过本文或选择查缺补漏。

内存的工作原理

假设你正要去超市，需要寄存两样东西。这个超市的寄存柜，一个抽屉只能放一个东西，所以你需要两个抽屉。

将东西分别放到了1号和2号抽屉里。

服务员将号码牌给你后，就可以去shopping了，购物完，凭号码牌拿东西即可。这大致就是计算机内存的工作原理，计算机内存就像很多抽屉，各个抽屉都有地址，根据地址存储和访问数据。

存储单项数据时，只需要计算机提供一个存储地址即可。当需要存储多项数据时，会用到两种基本方式---数组和链表

假设你要编写一个管理待办事项的应用，需要将这些待办事项存储到内存中，用数组还是链表？

数组

使用数组，就意味着所有待办事项在内存中都是相连的。

如果你现在想添加第4个待办事项，但后面那个抽屉放着别人的东西，这就难办了。这种情况只能请求计算机重新分配内存（可容纳4个待办事项），再将所有事项移到那里。

这里还有个权宜之计“预留位置”：预先申请10个连续位置，以防需要添加待办事项。这样，只要不超过10个，就无需转移。但它有两个缺点:

1.请求额外内存可能用不上，导致浪费；

2.超过10个后，还是得转移。

这是一个不错的措施，但不是完美的方案。对于这种问题，我们可以用链表解决。

链表

使用链表，元素则可以存储在内存的任何位置。

每个元素都会存储下一个元素的内存地址。比如，"吃午饭"存储下一个元素“玩滚地球”的内存地址13，而“玩滚地球”会存储下一个元素“喝茶”的地址22，这样便能将这几项数据串在一块了。

使用链表，根本不需要移动元素，元素随便放哪都行。添加新元素时，也不需要”预留位置“，只要内存足够，就能为链表分配内存。

索引

使用数组和链表存储数据，我们都会给元素编号，编号从0开始，这些元素的编号位置成为索引。

例如，下面的数组，元素20在索引1处

读取

数组-随机访问

正因为数组是顺序存储的，当知道起始地址，便能知道数组中所有元素的地址，支持随机访问（可随机读取任意索引位置的值）

假设有一个数组，包含5个元素，起始地址为00，那么我们便能简单推算出第5个元素的地址是04

链表-顺序访问

而链表呢?元素是分开存储的，无法推算出任意位置元素的地址，不支持随机访问，只能顺序访问（从第一个元素开始逐个读取元素）。

假设有一个链表，存储数值和位置如下，知道起始地址为01，但无法直接知道第5个元素的位置，因为不是顺序存储且每个元素只存储了下一个元素的地址。

必须从头遍历，直到找到第5个位置的元素01>03>05>07>08。

所以，当需要随机访问，数组是更好的选择。

插入元素

数组插入数据，必须将后面的元素后移（保持顺序存储），且有可能出现连续内存不足，这就得将整个数组复制到其他地方

例如，插入“卖茶叶”到第3个位置

使用链表时，插入元素很简单，只需修改它前一个元素的指向地址即可。

所以，当需要频繁插入元素，链表是更好的选择。

删除

删除元素呢？链表是更好的选，因为只需修改它前一个元素的指向地址即可。

而使用数组时，删除元素后，必须将后面的元素都向前移（保持顺序存储）。

常见操作的运行时间

需要注意的是，链表删除元素时，当能够立即删除元素时，运行时间才为O(1), 因为通常我们都记录了链表的第一个和最后一个元素。其他情况均为O(n)，因为需要通过顺序遍历再删除。

总结

数组

存储位置：顺序储存。

优点：支持随机访问，读取速度快。

缺点：插入和删除数据较慢，需要移动元素。

链表

存储位置：分开储存，每个元素都存储了下一个元素的地址。

优点：插入和删除数据快，无需移动元素，只需修改它前面元素的指向地址即可。

缺点：只支持顺序访问，读取速度较慢。

读取多，插入少，用数组。

读取少，插入多，用链表。

但在实际应用中，数组用的更多一，因为它支持随机读取。