全国报名热线

15201841284

Java面试官:记一次有关ArrayList和LinkedList的面试

时间:2019-01-29 10:06:18   来源:上海尚学堂   阅读:

1、先来点鸡汤

前几年易中天可谓非常的火,接受过很多采访。他的情况比较特殊,在武汉读高中时期,恰逢“知识青年上山下乡”活动,就到新疆去了。在新疆生产建设兵团工作、生活了10年,而后在乌鲁木齐钢铁公司子弟中学任教。77年全国恢复高考后他没有去考大学,78年国家恢复研究生招生后他去考了,然后被武汉大学中文系录取。

当时主持人问他,为什么跳过本科直接考研究生呢?他的回答是:考场上的事谁能说的准呐,如果我和我的学生一起去参加高考,万一他考上了我没考上,这多丢人呢(还怎么好意思当人家的老师)。但是考研如果考不上,那在学生面前是不丢人的。

大名鼎鼎的教授当初都害怕考不上,看来考上考不上乃兵家常事。

面试也是一样的,我们应该正确对待。知道的就回答,不知道的就请教,似是而非的就探讨,开开心心的度过一个小时的交谈就行了。至于结果那要看缘分了,而且这是一个双向选择。

2、记一次面试

有位应聘者来面试,我和他坐到了小会议室里。他,很年轻,刚入行,应该还培训过,是不是计算机专业我已经记不清了。

但这不重要,照例还是从List问起。一是List可以说是最简单的,二是简单的问题更能考察一个人的思维表达能力。

我:做Java开发的,List肯定用过,你都用过哪些List的实现类呢?

他:一般都用ArrayList。

我:除了ArrayList,你还知道哪些List,没用过也行。

他:(有点紧张)不知道。

其实他的水平大概我也清楚了,完全可以再问两个问题草草把他打发走。但只要时间允许的情况下,我是不会这样做的。

一方面是不让面试者觉得自己因水平较差不受重视。

二是这部分人大都是转行培训刚入坑不久的新人,不想让他们的自信心受到打击。

三是面试的过程其实对面试官也是一种锻炼,也可以借机refresh自己的记忆。

最后说句良心话,面试者为了这个面试花在路上的时间估计都要一个小时,如果用5分钟就让人家走,感觉有点说不过去。

我:还有一个LinkedList,不知道你有没有见过。

他:知道,平时没用过,所以没什么印象。

我:一个叫ArrayList,一个叫LinkedList,根据名字你说下它们底层是怎么实现的?

他:应该一个是用数组实现的,一个是链表实现的。

我:那你能不能说一下数组和链表的主要区别是什么?

大概过了好几秒,他没有回答,也不说不知道。我觉得可能是我问的方式略微笼统,我就又具体了一些。

我:数组和链表是数据结构里的概念,这你应该知道。我的意思是从数据结构的角度,数组有什么特点,链表有什么特点,或者说它们在内存里大致是怎么分布的?

他:数据结构的东西不太会。

我觉得我的问题已经很清晰了,但凡是正常的开发者,多多少少都应该能说出点,可是,他没有。

看得出他有点紧张,所以我每次都是微笑着、用很柔和的声音和他说话,就害怕太强势了给他造成影响。

虽然这么简单的问题,他都不会,我还是很耐心地给他讲解,就当是锻炼自己了。

我:定义一个数组,只需指定一个长度即可。然后就可以通过变量名+索引(或者说下标)的形式访问数组元素了,下标不能超过数组长度,否则就会发生索引越界异常。

比如数组a,长度是10,那么第一个元素就是a[0],最后一个就是a[9]。想访问哪个元素只要指定下标就可以了。像这种可以随意访问任何元素的,有个专用名词叫做随机访问。

那我们来看下它在内存中是如何分布的,才支持随机访问。其实数组在内存中是一段连续的空间,你可以把它想象成一个梯子,一个格子紧挨着一个格子。

数组名,也就是这个a,指向了这个空间的起始处地址,也就是数组的第一个元素的地址,所以其实和a[0]指向的是同一个地方。但a和a[0]的含义不一样,a表示内存地址,a[0]表示这个地址上存的元素。

这里的下标0其实指的是相对于起始处地址的偏移量。0表示没有偏移,所以就是起始处地址的那个元素,也即第一个元素。

a[1]表示相对于起始处地址偏移量为1的那个元素,实际可以认为底层执行的是*(a + 1)。a+1表示从起始地址开始向后偏移1个之后的地址,那么*(星号)的意思就是取出那个地址上存储的元素。因为向后偏移了1个,其实就是第二个,所以a[1]叫取出数组的第二个元素。

因数组在内存中是一段连续的空间,所以不管访问哪个元素都是这两步,加上偏移量,然后取数据。这就是它支持随机访问的原因。说白了就是所有元素按顺序挨在了一起。

也可以看出来,不管数组的长度是多长,访问元素的方式都是这两步,都在常量的时间内完成。所以按索引访问数组元素的时间复杂度就是O(1)。

ArrayList只不过是对数组的包装,因为数组在内存中分配时必须指定长度,且一旦分配好后便无法再增加长度,即不可能在原数组后面再接上一段的。

ArrayList之所以可以一直往里添加,是因为它内部做了处理。当底层数组填满后,它会再分配一个更大的新的数组,把原数组里的元素拷贝过来,然后把原数组抛弃掉。使用新的数组作为底层数组来继续存储。

他:你讲的非常好,我完全听懂了,比我当时那个培训班的老师讲的好多了。

我:LinkedList也实现了List接口,也可以按索引访问元素,表面上用起来感觉差不多,但是其底层却有天壤之别。

与数组一下子分配好指定长度的空间备用不同,链表不会预先分配空间。而是在每次添加一个元素时临时专门为它自己分配一个空间。

因为内存空间的分配是由操作系统完成的,可以说每次分配的位置都是随机的,并没有确定的规律。所以说链表的每个元素都在完全不同的内存地址上,那我们该如何找到它们呢?

唯一的做法就是把每个元素的内存地址都要保存起来。怎么保存呢?那就让上一个元素除了存储具体的数据之外,也存储一份下一个元素在内存中的地址。

整个就像前后按顺序依次相连的一条链,我们只要保存第一个元素的内存地址,就可以顺藤摸瓜找到所有的元素。

这其实就像一个挖宝藏游戏,假设共10步,告诉你第一步去哪里挖。然后挖出一个字条,上面写着第二步去哪里挖。依次这样挖下去。第九步挖出字条后才知道宝藏的位置,然后第十步就把它挖出来了。

可见为了得到宝藏必须这样一步一步挖下去。中间的任何一步都不能跳过,因为第十步宝藏的位置在第九步里放着呢,第九步的位置在第八步里放着呢,依次倒着下来就到了第一步的位置,而第一步的位置已经告诉你了。

所以数组更像是康庄大道、四平八稳。链表更像是曲径通幽、人迹罕至。一个像探险,步步为营。一个像回家,轻车熟路。

可见按索引访问链表元素时,必须从头一个个遍历,而且链表越长,位置越靠后,所需花费的时间就越长。所以按索引访问链表元素的时间复杂度就是O(n),n为链表的长度。

也说明了链表不支持随机访问。所以ArrayList就实现了RandomAccess(随机访问)接口,而LInkedList就没有。

他:你讲的真好。

3、后记

后来这个应聘者给我司前台打电话,说他自己水平太差,无法到我司来。但是叮嘱前台一定要转达对我的感谢。

说面试时他内心非常紧张,但面试官总是面带微笑很温和地跟他说话。遇到不懂的地方,总是非常有耐心地给他讲解,旁征博引,举一反三。最后他都听懂了,而且也不紧张了。

我感觉这是我收到的对我最高的评价,不是吗?

PS:由于文章有点长了,线性表的插入和删除会以源码解析的形式讲解。



分享:0