Map家族前来踢馆(一)

标签:先后   内存   长度   位置   mamicode   访问   情况   地址   元素   

List家族PK争遗产的结局虽然有点意料之外,但也在情理之中。再次告诉世人很多事情是可遇不可求的。

这件事情已闹得满城wind rain,不过还是无法改变ArrayList和LinkedList满脸心灰意冷且带有些许无奈的落寞。

老Map带着一行家眷推门而入,向老List表明来意后,老List并没有回答,而是从屋子里拿出一面大镜子。

老Map一脸懵逼,心想这啥情况?老List看出了它的疑惑,说到:“好好看看,我们长得都不一样,不属于同一种类,不具有可比性”。

老Map说到:“勿以相貌论短长”。我们都生活在计算机里,所以,one world,one dream,we are family。

老List在心理暗暗骂道,你DY的family。

为了能使这场类似于男子足球PK女子篮球的比赛顺利进行,采用新的规则。由一方进行陈述,另一方对不明白之处进行提问,然后再挑刺儿。

老List清了清嗓子,整理下思绪,从悠长悠长的memory中娓娓道来。List家族来自于古老而又遥远的数据结构王国,王国里的每个家族都有自己的十八般武艺。

我们家族的武艺就是线性表,从宏观上看,就相当于一个一维表格,只具有先后顺序,可以根据序号(位置或索引)进行访问。

最常见的一种是基于数组的实现,由于数组在内存中是一段连续空间,可以根据数组的地址和偏移量,瞬间定位到任意元素的位置,进行读或写。

Map家族前来踢馆(一)

王国有个专门的术语来描述这种情况,叫做随机访问。由于访问每个元素花的时间都是一样的,所有又叫常量时间访问。我的子孙ArrayList就是这样来的。

还有一种基于链表的实现,链表就像一个铁锁链一样,由很多单个的环接在一起形成一个链,所以这条链本身并不是一个整体,而是逐个逐个的环组合起来的,而且可以在任何地方加上一个环或去掉一个环。

Map家族前来踢馆(一)

链表在内存中的形态与铁锁链非常相似,每个节点按需动态创建,随机分配一个位置,节点间按顺序通过指针相连,整个串起来就是一条链,只要能握住这条链的第一个节点(头部),就可以依次往后找到所有节点。
Map家族前来踢馆(一)

只持有链表的头部,如果按序号访问,由于不知道其对应的节点在哪里,只能从头部依次往后查找。显然,序号越靠前,找到的越快,反之越慢。

可见访问每个元素的时间都不一样,且随着链表的长度增加(序号的增加)而递增。它们之间是一个正比例关系,由于正比例函数的图像是一条直线,这种关系也叫线性关系。因此这种访问也叫线性时间访问。我的子孙LinkedList就是这样来的。

Map家族前来踢馆(一)

由于这是老List的家族历史,所以它的陈述可谓声情并茂,好在终于结束了。

老Map及其家眷也长出一口气,这是它们首次这么认真地听一个外族人讲故事。但它也有颇多的疑问,想要迫不及待地大声说出来。

(完)

Map家族前来踢馆(一)

标签:先后   内存   长度   位置   mamicode   访问   情况   地址   元素   

原文地址:https://blog.51cto.com/15049788/2562568

版权声明:完美者 发表于 2020-12-16 12:19:42。
转载请注明:Map家族前来踢馆(一) | 完美导航

暂无评论

暂无评论...