恍然大悟,数组和链表的区别

图片

积千里跬步,汇万里江河.每天进步一点点,终有一天将成大佬

文前发言

  在Java中,很多地方都使用了数组和链表,还有两种组合的叫数组链表结构,就是常说的哈希表,HashMap底层的数据结构就是哈希表.远了,远了,这里不讲HashMap,这里讲数组和链表;

图片

数组

数组是我们平时用的最多的数据结构,它的特点是查询数据快,插入数据慢,查询的时间复杂度是O(1),插入的时间复杂度是O(n).

牛*一族去学校读书,学校有四人寝和五人寝,大牛,二牛,三牛,四牛一同住进了四人寝里,每天都五缺一;有一天,他们在游戏里认识了小牛,得知小牛也是他们学校的,于是邀请小牛和他们一起住,可是他们们寝室只能住四个人,这个怎么办呢?于是他们向学校(系统)申请,要求学校给他们一个新的六人寝(新的内存空间),于是学校就给了他们新的六人寝,于是他们全部都搬去了六人寝里,小牛也办了进去,之后每天五黑,好不快活;

图片

之后有其他学生看到牛*他们的做法,于是也通通向学校申请;最后学校发现了一个问题:就是学生们为了住进新寝室,花费了大量的时间在从旧寝室到新寝室的路上(插入数据慢)

有的人会说,那一开始就安排大牛,二牛,三牛,四牛住5人寝不就好了吗?这样他们就不用搬了(这就相当于我们初始化数组时,给数组指定了一个大小);这样的想法是好的,但是如果他们没有没有认识小牛,小牛也不会搬进去,这样他们四个人就一直住着5人寝,就造成了空间资源浪费;

有一天,老师去找进入新寝室的小牛谈话,一看得知小牛在4号床,一下就找到了小牛(查询数据快),问他在这个寝室住的习不习惯,小牛心想,每天都五黑,你说我习不习惯!!

图片

链表

链表我们平时用的比较少,它的特点是:插入数据快,查询数据慢,查询的时间复杂度是:O(n),插入的时间复杂度是:O(1),它的特点是和数组相反的;

  经过无数日夜的奋战,牛*一寝人觉得是时候该出去玩玩了,自从小牛搬过来后,就一直没日没夜的五黑,都快不知道外面的世界长什么样子了;他们一行人准备去游乐园转转.

  来到游乐园后,一群人像刚放出来的一样,对一切都充满了新鲜感,到处转悠.就在转悠的时候,细心的大牛发现了地上有一张纸条,打开一看,上面写着:"少年,你渴望力量吗?想获得力量就来海盗船找我!",大牛赶紧找来其他小伙伴,一同前往;到了海盗船的地方,发现船上写着:"力量源自摩天轮,请前往摩天轮",于是一群人就又前往摩天轮,在那里,终于过得了神秘力量---毒鸡汤:你的内心有多强大,你的力量就有多强大;小牛他们为了寻找这个力量,可谓费尽九牛二虎之力啊(查询数据慢);

图片

可以发现,每个元素存着下个元素的地址,所以如果要查找其中某个元素,就必须要从头开始,才能找到.这就比较慢了.但是,他们添加元素很快,元素可以随机出现在游乐园的某个地方,只要在新添加元素的前一个元素指明新元素的地址在哪里就可以了;

发个对比表格吧

时间复杂度对比表

数组链表
插入O(n) 慢O(1) 快
删除O(n) 慢O(1) 快
查询O(1) 快O(n) 慢