【从0到1学算法】 数组和链表
KENDOEVERTHING 人气:3今天讲最基本的数据结构，数组和链表。如果你已经滚瓜烂熟，可以跳过本文或选择查缺补漏。
内存的工作原理
假设你正要去超市，需要寄存两样东西。这个超市的寄存柜，一个抽屉只能放一个东西，所以你需要两个抽屉。
将东西分别放到了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)，因为需要通过顺序遍历再删除。
总结
数组
存储位置：顺序储存。
优点：支持随机访问，读取速度快。
缺点：插入和删除数据较慢，需要移动元素。
链表
存储位置：分开储存，每个元素都存储了下一个元素的地址。
优点：插入和删除数据快，无需移动元素，只需修改它前面元素的指向地址即可。
缺点：只支持顺序访问，读取速度较慢。
读取多，插入少，用数组。
读取少，插入多，用链表。
但在实际应用中，数组用的更多一，因为它支持随机读取。
文章首发于公众号【KEN DO EVERTHING】
本公众号专注于java相关技术,但不限于java、mysql、python、面试技巧、生活感悟等。分享优质博文,技术干货，学习资源等优质内容。
欢迎关注，一起学习，共成长！
加载全部内容