关于Java Collections应知应会
翻译 By Long Luo
下面这些问题Stackoverflow上关于Java collections提问和讨论最多的问题。在你阅读这些问题之前,有必要先阅读下这篇文章3分钟速读:图解Java Collections的接口以及类层级关系。
1. 什么时候用LinkedList?什么时候用ArrayList?
ArrayList本质上是一个数组。它的元素可以直接通过索引值直接访问。但是如果数组已经满了,那么需要重新分配一个更大的数组并且将全部的元素移动到新的数组需要花费O(n)的时间。当然从现有的数组中增加或者删除一个元素都需要移动现有的元素。这个可能是使用ArrayList中最大的不便之处。
LinkedList是一个双端链表。正因为如此,如果要获取一个链表中间的元素,需要从链表的头部开始查找。另一方面,增加或者删除链表中的元素将会很快,因为只需要在本地修改即可。
下表总结了最快情况下的比较需要耗费时间:
Method | Arraylist | LinkedList |
---|---|---|
get(index) | O(1) | O(n) |
add(E) | O(n) | O(1) |
add(E, index) | O(n) | O(n) |
remove(index) | O(n) | O(n) |
Iterator.remove() | O(n) | O(1) |
Iterator.add(E) | O(n) | O(1) |
不管运行时间,当大型列表需要额外考虑内存占用。LinkedList每个node至少需要2个额外的指针用于连接前后2个node。而在ArrayList中只需要数组存储元素值即可。
2. 当遍历容器时,高效等价于移除元素的操作?
最正确的方式就是在遍历容器时用Iterator.remove()
去修改一个容器,如下代码所示:1
2
3
4
5Iterator<Integer> itr = list.iterator();
while(itr.hasNext()) {
// do something
itr.remove();
}
另外一个非常高频的使用但是不正确的代码是这样的:1
2
3for(Integer i: list) {
list.remove(i);
}
运行上面的代码时你会得到一个ConcurrentModificationException
。原因是因为一个迭代器自生成之后(在for循环中),用于横贯这个列表。与此同时,这个列表同时也被Iterator.remove()
修改了。在Java语言中,当一个线程在修改一个容器时而另外一个线程在遍历它是不允许的。
3. 如何将List转换成int[]?
最快捷的方式可能是用Apache Commons Lang库中的ArrayUtils。1
int[] array = ArrayUtils.toPrimitive(list.toArray(new Integer[0]));
在JDK中,没有快捷方式。请注意你不能使用List.toArray()
,因为那会将列表转换成Integer[]
。正确的方式应该是这样的:1
2
3
4int[] array = new int[list.size()];
for(int i=0; i < list.size(); i++) {
array[i] = list.get(i);
}