java - java是如何在Java中实现LinkedList到ArrayList的转换的？

Question

我正在实现一个公共(public)方法，该方法需要一个能够处理两端插入的数据结构。自 ArrayList.add(0,key)将花费 O(N) 时间，我决定使用 LinkedList相反 - add和 addFirst方法都应该花费 O(1) 时间。

但是，为了使用现有的 API，我的方法需要返回一个 ArrayList .所以我有两种方法:

(1) 使用LinkedList ,执行所有 N 元素的添加，其中 N/2 将添加到前面，N/2 将添加到末尾。然后转换这个LinkedList至 ArrayList通过调用 ArrayList构造函数: return new ArrayList<key>(myLinkedList);

(2) 使用ArrayList并调用ArrayList.add(key)在后面添加 N/2 元素并调用 ArrayList.add(0,key)在前面添加 N/2 元素。返回此 ArrayList .

谁能评论一下哪个选项在时间复杂度方面更优化？我不确定 Java 如何实现 ArrayList 的构造函数- 这是决定哪个选项更好的关键因素。

谢谢。

Answer 1

第一个方法遍历列表:

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

Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

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

第二种方法将在每次添加到前面时移动元素(并每隔一段时间调整一次大小):

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

Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

鉴于官方对功能的假设，第一种方法更有效。

仅供引用:您可以使用 LinkedList.toArray

获得更多里程