金山WPS Android面试题及参考答案

 说说你所知道的所有集合？并阐述其内部实现。

在 Android 开发（Java 语言基础上）中有多种集合。

首先是 List 集合，主要包括 ArrayList 和 LinkedList。

ArrayList 是基于数组实现的动态数组。它的内部有一个数组来存储元素，当添加元素时，如果数组容量不够，会进行扩容操作。例如，初始容量可能是 10，当添加第 11 个元素时，它会创建一个新的、更大的数组（通常是原来容量的 1.5 倍左右），然后将原来数组中的元素复制到新数组中，再添加新元素。这种方式使得它在随机访问元素时效率很高，时间复杂度是 O (1)，因为可以通过数组下标直接定位元素。但是在插入和删除元素（非末尾位置）时效率较低，因为需要移动后面的元素来保持数组的连续性，插入和删除的时间复杂度是 O (n)。

LinkedList 是基于链表实现的集合。它的每个节点包含数据和指向下一个节点（以及上一个节点，双向链表的情况下）的引用。在插入和删除元素时，只需要改变节点之间的引用关系，所以在插入和删除操作上效率较高，时间复杂度是 O (1)（如果知道插入位置）。不过，在随机访问元素时，需要从链表头开始遍历&#