ArrayList or LinkedList

Question

Possible Duplicate:
ArrayList Vs LinkedList
ArrayList vs. LinkedList which one is better for sorting

Suppose we have 100 strings(names) and want to sort them, which one is preferred out of ArrayList and LinkedList And reason(s) for the preference is ?

With only 100 elements, it almost certainly doesn't make the blind bit of difference which one you choose. — skaffman, Mar 06 '12 at 14:51
@ skaffman..that is understood...but i was looking for the generic answer..and took 100 as a example only...might be i would have taken a million as example...thanks for inputs — lowLatency, Mar 06 '12 at 15:10

score 5 · Answer 1 · answered Mar 06 '12 at 14:59

Does not matter for sorting using the Collections API. If you take a look at the implementation of Collections.sort:

public static <T extends Comparable<? super T>> void sort(List<T> list) {
    Object[] a = list.toArray();
    Arrays.sort(a);
    ListIterator<T> i = list.listIterator();
    for (int j=0; j<a.length; j++) {
        i.next();
        i.set((T)a[j]);
    }
}

You can see that it does the following:

Create a copy of the list using List.toArray
Use the Arrays.sort method to sort the array
Update the list (eg copy back the array to the list)

even i thought the same...thanks for clearing the doubt!! – lowLatency Mar 06 '12 at 15:06 — lowLatency, Mar 06 '12 at 15:06

score 2 · Accepted Answer · answered Mar 06 '12 at 14:52

2

Depends what kind of sort.

ArrayLists are slow if you're going to be inserting/retrieving/removing at the beginning a lot. (big ripple)

LinkedLists are slow if you're going to be inserting/retrieving/removing at an index.

answered Mar 06 '12 at 14:52

varatis

14,494
23
71
114

thanks for the info..even this is also I am looking for – lowLatency Mar 06 '12 at 15:06
1

Unless you are going to waste your time implementing the sort algorithm from scratch, this info is not going to help you. Even if you do, you will probably get a more efficient sort by copying the list to an array and sorting the array. – Stephen C Mar 06 '12 at 15:45
@StephenC I'm not sure that implementing your own sort is a waste of time... – varatis Mar 06 '12 at 19:50
@varatis - there are some circumstances where it is not; e.g. if you are trying to learn about sorting. However, in the **vast majority of cases** where you are programming for real, you won't be able to do better than the standard Java sort implementation, or some well-known third-party library. Hence it is a waste of time. – Stephen C Mar 07 '12 at 01:30

score 1 · Answer 3 · edited May 23 '17 at 12:21

1

The implementation choice should be made based on the operations occurring.

See here.

edited May 23 '17 at 12:21

Community

1
1

answered Mar 06 '12 at 14:52

bvulaj

5,023
5
31
45

score 1 · Answer 4 · answered Mar 06 '12 at 14:55

http://commons.apache.org/collections/api-3.1/org/apache/commons/collections/list/TreeList.html

That gives you an idea of how fast the operations are for each type of list. Obviously depending on your data you may find that one operates better than the other(they each have their advantages and disadvantages).

ArrayList or LinkedList

4 Answers4