How does java implement the conversion of LinkedList to ArrayList in Java?
arraylist, big-o, java, linked-list, performance
Solution
The first method iterates across the list:
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.
which, you can reasonably infer, uses the `iterator` interface.
The second method will shift elements every time you add to the front (and resize every once in a while):
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).
Given the official assumptions regarding the functions, the first method is more efficient.
FYI: you may get more mileage using `LinkedList.toArray`
Problem
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.