Java面试：集合框架体系

一、ArrayList

1.数组（Array）

是一种用连续的内存空间存储相同数据类型数据的线性数据结构

数组如何获取其他元素的地址值？

寻址公式：a[i] = baseAddress + i * dataTypeSize

• baseAddress：数组的首地址
• dataTypeSize：代表数组中元素类型的大小，例如int型，dataTypeSize = 4个字节

面试题1：为什么数组索引从0开始呢？假如从1开始不行吗？

• 在根据数组索引获取元素的时候，会用索引和寻址公式来计算内存所对应的元素数据，寻址公式是：数组的首地址+索引 * 存储数据的类型大小
• 如果数组的索引从1开始，寻址公式中就需要增加一次减法操作，对于CPU来说就多了一次指令，影响性能

面试题2：操作数组的时间复杂度

• 查找：随机查询（根据索引查询） O(1)
• 查找：未知索引查询 O(n)
• 查找：未知索引查询（将数组排序后）  二分查找O(log n)
• 插入/删除：O(n)

2.ArrayList源码分析

（1）成员变量

（2）构造方法

（3）添加和扩容操作

面试题1：ArrayList底层的实现原理是什么？

面试题2：ArrayList list = new ArrayList（10）中的list扩容几次？

• 该语句只是声明和实例了一个ArrayList，指定了容量为10，未扩容

面试题3：如何实现数组和List之间的转换？

• 数组转List，使用JDK中java.util.Arrays工具类的asList方法
• List转数组，使用List的toArray方法。无参toArray方法返回Object数组，传入初始化长度的数组对象，返回该对象数组

追问：用Arrays.asList转List后，如果修改了数组内容，list受影响吗？List用toArray转数组后，如果修改了List内容，数组受影响吗？

二、LinkedList

1.链表

链表操作数据的时间复杂度

	查询	新增删除
单向链表	头O(1)，其他O(n)	头O(1)，其他O(n)
双向链表	头尾O(1)，其他O(n)， 给定节点O(1)	头尾O(1)，其他O(n)， 给定节点O(1)

2.LinkedList源码分析

面试题1：ArrayList和LinkedList的区别是什么？