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

i implementing public method needs data structure needs able handle insertion @ 2 ends. since arraylist.add(0,key) take o(n) time, decide use linkedlist instead - add , addfirst methods should both take o(1) time.

however, in order work existing api, method needs return arraylist. have 2 approaches:

(1) use linkedlist, addition of n elements n/2 added front , n/2 added end. convert linkedlist arraylist calling arraylist constructor: return new arraylist<key>(mylinkedlist);

(2) use arraylist , call arraylist.add(key) add n/2 elements , call arraylist.add(0,key) add n/2 elements front. return arraylist.

can comment on option more optimized in terms of time complexity? not sure how java implements constructor of arraylist - key factor decides option better.

thanks.

the first method iterates across list:

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

constructs list containing elements of specified collection, in order returned collection's iterator.

which, can reasonably infer, uses iterator interface.

the second method shift elements every time add front (and resize every once in while):

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

inserts specified element @ specified position in list. shifts element @ position (if any) , subsequent elements right (adds 1 indices).

given official assumptions regarding functions, first method more efficient.

fyi: may more mileage using linkedlist.toarray