How does Java implement LinkedList to ArrayList to Java conversion?

Question

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

However, to work with the existing API, my method must return an ArrayList . Therefore, I have two approaches:

(1) use LinkedList , do all adding N elements where N / 2 will be added to the beginning 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 in the opposite direction and call ArrayList.add(0,key) to add N / 2 elements. front. Return this ArrayList value.

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

thanks.

Answer 1

The first method iterates through the list:

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

Creates a list containing the elements of the specified collection in the order in which they are returned by the collection iterator.

which you can reasonably conclude, uses the iterator interface.

The second method will move the elements every time you add a front (and resize it 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 item at the specified position in this list. Shifts the element at the moment (if any) and any subsequent elements to the right (adds one to their indices).

Given the official assumptions regarding functions, the first method is more efficient.

FYI: you can get more mileage using LinkedList.toArray

Answer 2

I would suggest that you use ArrayDeque , which is faster than LinkedList , to insert elements from two ends and consumes less memory. Then convert it to ArrayList using method # 1.