How to convert List<String> to an ArrayList<String>

Question

This API call returns a potentially large List<String>, which is not sorted. I need to sort it, search it, and access random elements. Currently the List is implemented by an ArrayList (I checked the source), but at some unknown point in the future the API developers may choose to switch to a LinkedList implementation (without changing the interface).

Sorting, searching, accessing a potentially large LinkedList would be extremely slow and unacceptable for my program. Therefore I need to convert the List to an ArrayList to ensure the practical efficiency of my program. However, since the List is most likely an ArrayList already, it would be inefficient to needlessly create a new ArrayList copy of the List.

Given these constraints, I have come up with the following method to convert a List into an ArrayList:

private static <T> ArrayList<T> asArrayList(List<T> list) {
  if (list instanceof ArrayList) {
    return (ArrayList<T>) (list);
  } else {
    return new ArrayList<T>(list);
  }
}

My question is this: Is this the most efficient way to work with a List with an unknown implementation? Is there a better way to convert a List to an ArrayList? Is there a better option than converting the List into an ArrayList?

Do you have an idea of how large it could be (size)? Unless it can be really big and causes performance issue, I would just use the copy constructor. — assylias
– assylias, Commented Jun 1, 2012 at 14:58
Probably between 5,000 and 50,000, and the method would be called tens of thousands of times. — dln385
– dln385, Commented Jun 1, 2012 at 15:01
Using the copy constructor on a list with 100,000 items takes less than 0.5ms on my desktop pc (after JIT has kicked in). Now the cast is about 1,000x faster ;-) — assylias
– assylias, Commented Jun 1, 2012 at 15:05

Mac · Accepted Answer · 2012-06-01 15:02:21Z

4

You can't really get much simpler than what you've got - looks about as efficient as it could possibly be to me.

That said, this sounds very much like premature optimisation - you should only really need to worry about this if and when the author of the API you're using changes to a LinkedList. If you worry about it now, you are likely to spend a lot of time and effort planning for a future scenario that may not even come to pass - this is time that might be better spent finding other issues to fix. Presumably the only time you'll be changing versions of the API is between versions of your own application - handle the issue at that point, if at all.

answered Jun 1, 2012 at 15:02

Mac

14.8k11 gold badges65 silver badges83 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

biziclop · Accepted Answer · 2012-06-01 15:40:09Z

2

As you can see yourself, the code is simple and it is efficient inasmuch as it only creates a copy if it is necessary.

So the answer is that there is no significantly better option, save for a completely different type of solution, something that sorts your list as well, for example.

(Bear in mind that this level of optimisation is rarely required, so it's not a very frequent problem.)

Update: Just an afterthoughtL as a general rule, well-written APIs don't return data types that are inappropriate for the amount of data they are likely to contain. That is not to say you should trust them blindly, but it's not a completely unreasonable assumption.

edited Jun 1, 2012 at 15:40

answered Jun 1, 2012 at 15:00

biziclop

50k12 gold badges80 silver badges108 bronze badges

Comments

Stephen C · Accepted Answer · 2012-06-01 15:17:43Z

1

Sorting, searching, accessing a potentially large LinkedList would be extremely slow and unacceptable for my program.

Actually, it is not as bad as that. IIRC, the Collections.sort methods copy the list to a temporary array, sort the array, clear() the original list and copy the array back to it. For large enough lists, the O(NlogN) sorting phase will dominate the O(N) copying phases.

answered Jun 1, 2012 at 15:17

Stephen C

723k95 gold badges849 silver badges1.3k bronze badges

Comments

Wormbo · Accepted Answer · 2012-06-01 15:17:42Z

0

Java collections that support efficient random access implement the RandomAccess marker interface. For such a list you could just run Collections.sort on the list directly. For lists without random access you should probably dump the list to an array using one of its toArray methods, sort that array, then wrap it into a random-access List.

T[] array = (T[])list.toArray(); // just suppress the warning if the compiler worries about unsafe cast
Arrays.sort(array);
List<T> sortedList = Arrays.asList(array);

I think Arrays.asList actually creates an ArrayList, so you could try casting its result, if you like.

Collections.sort is efficient for all List implementations, as long as they provide an efficient ListIterator. The method dumps the list into an array, sorts that, then uses the ListIterator to copy the values back into the list in O(n).

answered Jun 1, 2012 at 15:17

Wormbo

5,0102 gold badges23 silver badges43 bronze badges

3 Comments

biziclop Over a year ago

Arrays.asList() doesn't create an arraylist (well, it sort of does, as it returns an Arrays.ArrayList inner class type. :)) but a list that is backed by the actual array.

Wormbo Over a year ago

Ah ok. That's why naming your classes matters. Two classes with the same name in the same package, one being a public top-level class and the other being an inner class, is just confusing. :)

biziclop Over a year ago

Ask me how I found this out :)

Collectives™ on Stack Overflow

How to convert List<String> to an ArrayList<String>

4 Answers 4

Comments

Comments

Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related