java如何在Java中實現LinkedList到ArrayList的轉換？

我正在實現一個需要能夠處理兩端插入的數據結構的公共方法。由於ArrayList.add(0,key)將採取O（N）時間，我決定使用一個LinkedList代替 - 對add和addFirst方法都應該採取O（1）時間。java如何在Java中實現LinkedList到ArrayList的轉換？

但是，爲了使用現有的API，我的方法需要返回ArrayList。所以，我有兩種方法：

（1）使用LinkedList，做所有的加入其中N/2將被添加到前和N/2將被添加到所述Ñ元件結束。然後通過調用ArrayList構造轉換此LinkedList到ArrayList：

（2）使用ArrayList和呼叫ArrayList.add(key)到N/2元素添加到背面，並調用ArrayList.add(0,key)添加N/2元素前方。返回這個ArrayList。

任何人都可以評論哪個選項在時間複雜度方面更加優化？我不確定Java如何實現ArrayList的構造函數 - 這是決定哪個選項更好的關鍵因素。

謝謝。

來源

2013-08-01 Eric H.

您是否知道輸入方法時n的值？ – radai

源代碼可用..但是，基於O（N）迭代器的'ArrayList'的複製構造函數是安全的。 –

這是打開jdk實現ArrayList構造函數的鏈接，http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/ArrayList.java#ArrayList 。％3Cinit％3E％28java.util.Collection％29 – anoopelias

跨列表中的第一種方法進行迭代：

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）

插入在指定位置的指定的元素這個清單。將當前位置的元素（如果有的話）和任何後續元素移到右側（將其中的一個添加到它們的索引）。

鑑於有關函數的官方假設，第一種方法更高效。

FYI：您可以使用LinkedList.toArray

來源

2013-08-01 03:49:59 SheetJS

感謝您的鏈接。我認爲這是有道理的。 –

我會建議你使用ArrayDeque這比LinkedList更快地插入兩端元素和消耗更少的內存獲得更多的里程。然後使用方法＃1將其轉換爲ArrayList。

來源

2014-08-19 23:46:23 BladeCoder

java如何在Java中實現LinkedList到ArrayList的轉換？

回答

相關問題