2019-11-26 更新
文贺 · 知名电商Java技术专家
List 作为工作中最常见的集合类型,在面试过程中,也是经常会被问到各种各样的面试题,一般来说,只要你看过源码,心中对 List 的总体结构和细节有所了解的话,基本问题都不大。
很多面试官喜欢这样子开头,考察面试同学对 ArrayList 有没有总结经验,介于 ArrayList 内容很多,建议先回答总体架构,再从某个细节出发作为突破口,比如这样:
ArrayList 底层数据结构是个数组,其 API 都做了一层对数组底层访问的封装,比如说 add 方法的过程是……(这里可以引用我们在 ArrayList 源码解析中 add 的过程)。
一般面试官看你回答得井井有条,并且没啥漏洞的话,基本就不会深究了,这样面试的主动权就掌握在自己手里面了,如果你回答得支支吾吾,那么面试官可能就会开启自己面试的套路了。
说说你自己对 LinkedList 的理解也是同样套路。
答:此处数组的大小是 1,下一次扩容前最大可用大小是 10,因为 ArrayList 第一次扩容时,是有默认值的,默认值是 10,在第一次 add 一个值进去时,数组的可用大小被扩容到 10 了。
答:这里的考查点就是扩容的公式,当增加到 11 的时候,此时我们希望数组的大小为 11,但实际上数组的最大容量只有 10,不够了就需要扩容,扩容的公式是:oldCapacity + (oldCapacity>> 1),oldCapacity 表示数组现有大小,目前场景计算公式是:10 + 10 /2 = 15,然后我们发现 15 已经够用了,所以数组的大小会被扩容到 15。
答:第一题中我们已经计算出来数组在加入一个值后,实际大小是 1,最大可用大小是 10 ,现在需要一下子加入 15 个值,那我们期望数组的大小值就是 16,此时数组最大可用大小只有 10,明显不够,需要扩容,扩容后的大小是:10 + 10 /2 = 15,这时候发现扩容后的大小仍然不到我们期望的值 16,这时候源码中有一种策略如下:
// newCapacity 本次扩容的大小,minCapacity 我们期望的数组最小大小
// 如果扩容后的值 < 我们的期望值,我们的期望值就等于本次扩容的大小
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
所以最终数组扩容后的大小为 16。
答:因为原数组比较大,如果新建新数组的时候,不指定数组大小的话,就会频繁扩容,频繁扩容就会有大量拷贝的工作,造成拷贝的性能低下,所以回答说新建数组时,指定新数组的大小为 5k 即可。
答:扩容底层使用的是 System.arraycopy 方法,会把原数组的数据全部拷贝到新数组上,所以性能消耗比较严重。
答:有两点:
这两点在我们平时设计和写代码时都可以借鉴。
List<String> list = new ArrayList<String>() {{
add("2");
add("3");
add("3");
add("3");
add("4");
}};
for (int i = 0; i < list.size(); i++) {
if (list.get(i).equals("3")) {
list.remove(i);
}
}
答:不能删除干净,最终删除的结果是 2、3、4,有一个 3 删除不掉,原因我们看下图:
从图中我们可以看到,每次删除一个元素后,该元素后面的元素就会往前移动,而此时循环的 i 在不断地增长,最终会使每次删除 3 的后一个 3 被遗漏,导致删除不掉。
答:不可以,会报错。因为增强 for 循环过程其实调用的就是迭代器的 next () 方法,当你调用 list#remove () 方法进行删除时,modCount 的值会 +1,而这时候迭代器中的 expectedModCount 的值却没有变,导致在迭代器下次执行 next () 方法时,expectedModCount != modCount 就会报 ConcurrentModificationException 的错误。
答:可以的,因为 Iterator.remove () 方法在执行的过程中,会把最新的 modCount 赋值给 expectedModCount,这样在下次循环过程中,modCount 和 expectedModCount 两者就会相等。
答:是的,虽然 LinkedList 底层结构是双向链表,但对于上述三个问题,结果和 ArrayList 是一致的。
答:可以先从底层数据结构开始说起,然后以某一个方法为突破口深入,比如:最大的不同是两者底层的数据结构不同,ArrayList 底层是数组,LinkedList 底层是双向链表,两者的数据结构不同也导致了操作的 API 实现有所差异,拿新增实现来说,ArrayList 会先计算并决定是否扩容,然后把新增的数据直接赋值到数组上,而 LinkedList 仅仅只需要改变插入节点和其前后节点的指向位置关系即可。
答:ArrayList 更适合于快速的查找匹配,不适合频繁新增删除,像工作中经常会对元素进行匹配查询的场景比较合适,LinkedList 更适合于经常新增和删除,对查询反而很少的场景。
答:ArrayList 有最大容量的,为 Integer 的最大值,大于这个值 JVM 是不会为数组分配内存空间的,LinkedList 底层是双向链表,理论上可以无限大。但源码中,LinkedList 实际大小用的是 int 类型,这也说明了 LinkedList 不能超过 Integer 的最大值,不然会溢出。
答:ArrayList 允许 null 值新增,也允许 null 值删除。删除 null 值时,是从头开始,找到第一值是 null 的元素删除;LinkedList 新增删除时对 null 值没有特殊校验,是允许新增和删除的。
答:当两者作为非共享变量时,比如说仅仅是在方法里面的局部变量时,是没有线程安全问题的,只有当两者是共享变量时,才会有线程安全问题。主要的问题点在于多线程环境下,所有线程任何时刻都可对数组和链表进行操作,这会导致值被覆盖,甚至混乱的情况。
如果有线程安全问题,在迭代的过程中,会频繁报 ConcurrentModificationException 的错误,意思是在我当前循环的过程中,数组或链表的结构被其它线程修改了。
Java 源码中推荐使用 Collections#synchronizedList 进行解决,Collections#synchronizedList 的返回值是 List 的每个方法都加了 synchronized 锁,保证了在同一时刻,数组和链表只会被一个线程所修改,或者采用 CopyOnWriteArrayList 并发 List 来解决,这个类我们后面会说。
答:如果和面试官面对面沟通的话,你可以去画一下,可以把 《LinkedList 源码解析》中的 LinkedList 的结构画出来,如果是电话面试,可以这么描述:双向链表中双向的意思是说前后节点之间互相有引用,链表的节点我们称为 Node。Node 有三个属性组成:其前一个节点,本身节点的值,其下一个节点,假设 A、B 节点相邻,A 节点的下一个节点就是 B,B 节点的上一个节点就是 A,两者互相引用,在链表的头部节点,我们称为头节点。头节点的前一个节点是 null,尾部称为尾节点,尾节点的后一个节点是 null,如果链表数据为空的话,头尾节点是同一个节点,本身是 null,指向前后节点的值也是 null。
答:如果是面对面沟通,最好可以直接画图,如果是电话面试,可以这么描述:
新增:我们可以选择从链表头新增,也可以选择从链表尾新增,如果是从链表尾新增的话,直接把当前节点追加到尾节点之后,本身节点自动变为尾节点。
删除:把删除节点的后一个节点的 prev 指向其前一个节点,把删除节点的前一个节点的 next 指向其后一个节点,最后把删除的节点置为 null 即可。
List 在工作中经常遇到,熟读源码不仅仅是为了应对面试,也为了在工作中使用起来得心应手,如果想更深入了解 List,可以看一遍 ArrayList 源码之后,自己重新实现一个 List。这样的话,就会对 List 底层的数据结构和操作细节理解更深。
©版权归慕课网所有,未经许可不得转载
精选留言 写留言
新马冲老龙坝
2020-11-26 0 1
过客匆匆
2020-07-12 0 1
梦编猿
2020-04-10 3 7
小汤师爷
2020-04-02 0 5
慕妹7164721
2020-02-01 0 0
慕妹7164721
2020-02-01 5 1
阳坤92
2019-12-17 3 2
Aegon_Targaryen
2019-11-29 1 7
慕粉4318313
2019-10-28 1 0
威先森
2019-10-14 2 4
音殿
2019-10-11 1 1
buxingshi
2019-09-24 1 0
Seed2009
2019-09-22 1 0
licly
2019-09-20 1 1
ciggii
2019-09-19 3 3
温柔的微笑
2019-09-18 1 1
bb111323
2019-09-13 1 2
奶茶三兄弟d
2019-09-10 1 0
阳坤92
2019-09-10 2 0
鹏飞天下
2019-09-09 2 0
加载更多