【从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),因为需要通过顺序遍历再删除。
总结
数组
存储位置:顺序储存。
优点:支持随机访问,读取速度快。
缺点:插入和删除数据较慢,需要移动元素。
链表
存储位置:分开储存,每个元素都存储了下一个元素的地址。
优点:插入和删除数据快,无需移动元素,只需修改它前面元素的指向地址即可。
缺点:只支持顺序访问,读取速度较慢。
读取多,插入少,用数组。
读取少,插入多,用链表。
但在实际应用中,数组用的更多一,因为它支持随机读取。
文章首发于公众号【KEN DO EVERTHING】
本公众号专注于java相关技术,但不限于java、mysql、python、面试技巧、生活感悟等。分享优质博文,技术干货,学习资源等优质内容。
欢迎关注,一起学习,共成长!