java - How does java implement the conversion of LinkedList to ArrayList in Java?

Question

I am implementing a public method that needs a data structure that needs to be able to handle insertion at two ends. Since ArrayList.add(0,key) will take O(N) time, I decide to use a LinkedList instead - the add and addFirst methods should both take O(1) time.

However, in order to work with existing API, my method needs to return an ArrayList. So I have two approaches:

(1) use LinkedList, do all the addition of N elements where N/2 will be added to the front and N/2 will be added to the end. Then convert this LinkedList to ArrayList by calling the ArrayList constructor: return new ArrayList<key>(myLinkedList);

(2) use ArrayList and call ArrayList.add(key) to add N/2 elements to the back and call ArrayList.add(0,key) to add N/2 elements to the front. Return this ArrayList.

Can anyone comment on which option is more optimized in terms of time complexity? I am not sure how Java implements the constructor of ArrayList - which is the key factor that decides which option is better.

thanks.

Answer 1

第一个方法遍历列表：

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/ArrayList.html#ArrayList(java.util.Collection)

按照集合的迭代器返回的顺序构造一个包含指定集合元素的列表。

您可以合理地推断，它使用了iterator接口。

第二种方法将在您每次添加到前面时移动元素（并且每隔一段时间调整一次大小）：

http://docs.oracle.com/javase/1.5.0/docs/api/java/util/ArrayList.html#add(int , E)

在此列表中的指定位置插入指定元素。将当前位于该位置的元素（如果有）和任何后续元素向右移动（将它们的索引加一）。

鉴于有关函数的官方假设，第一种方法更有效。

仅供参考：您可能会获得更多里程使用LinkedList.toArray

Answer 2

我建议您使用ArrayDeque比 a 更快的 aLinkedList在两端插入元素并消耗更少的内存。然后将其转换为ArrayList使用方法#1。