Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

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

KENDOEVERTHING 2020-02-16 22:59:00 阅读数:29 评论数:0 点赞数:0 收藏数:0

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

内存的工作原理

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

image

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

image

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

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

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

数组

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

image

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

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

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

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

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

链表

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

image

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

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

索引

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

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

image

读取

数组-随机访问

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

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

image

链表-顺序访问

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

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

image

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

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

插入元素

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

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

image

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

image

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

删除

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

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

常见操作的运行时间

image

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

总结

数组

存储位置:顺序储存。

优点:支持随机访问,读取速度快。

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

链表

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

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

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

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

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

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


文章首发于公众号【KEN DO EVERTHING】
本公众号专注于java相关技术,但不限于java、mysql、python、面试技巧、生活感悟等。分享优质博文,技术干货,学习资源等优质内容。
欢迎关注,一起学习,共成长!

版权声明
本文为[KENDOEVERTHING]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/KEN-DO-EVERTHING/p/12319324.html