When do you know when to use a TreeSet or LinkedList?

Question

What are the advantages of each structure?

In my program I will be performing these steps and I was wondering which data structure above I should be using:

1. Taking in an unsorted array and adding them to a sorted structure1.
2. Traversing through sorted data and removing the right one
3. Adding data (never removing) and returning that structure as an array

Answer 1

The genuine power and advantage of TreeSet lies in interface it realizes - NavigableSet

Why is it so powerfull and in which case?

Navigable Set interface add for example these 3 nice methods:

    headSet(E toElement, boolean inclusive) 
    tailSet(E fromElement, boolean inclusive)
    subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)  

These methods allow to organize effective search algorithm(very fast).

Example: we need to find all the names which start with Milla and end with Wladimir:

    TreeSet<String> authors = new TreeSet<String>();
    authors.add("Andreas Gryphius");
    authors.add("Fjodor Michailowitsch Dostojewski");
    authors.add("Alexander Puschkin");
    authors.add("Ruslana Lyzhichko");
    authors.add("Wladimir Klitschko");
    authors.add("Andrij Schewtschenko");
    authors.add("Wayne Gretzky");
    authors.add("Johann Jakob Christoffel");
    authors.add("Milla Jovovich");
    authors.add("Taras Schewtschenko");
    System.out.println(authors.subSet("Milla", "Wladimir"));

output:

    [Milla Jovovich, Ruslana Lyzhichko, Taras Schewtschenko, Wayne Gretzky] 

TreeSet doesn't go over all the elements, it finds first and last elemenets and returns a new Collection with all the elements in the range.

Answer 2

When do you know when to use a TreeSet or LinkedList? What are the advantages of each structure?

In general, you decide on a collection type based on the structural and performance properties that you need it to have. For instance, a TreeSet is a Set, and therefore does not allow duplicates and does not preserve insertion order of elements. By contrast a LinkedList is a List and therefore does allow duplicates and does preserve insertion order. On the performance side, TreeSet gives you O(logN) insertion and deletion, whereas LinkedList gives O(1) insertion at the beginning or end, and O(N) insertion at a selected position or deletion.

The details are all spelled out in the respective class and interface javadocs, but a useful summary may be found in the Java Collections Cheatsheet.

In practice though, the choice of collection type is intimately connected to algorithm design. The two need to be done in parallel. (It is no good deciding that your algorithm requires a collection with properties X, Y and Z, and then discovering that no such collection type exists.)

In your use-case, it looks like TreeSet would be a better fit. There is no efficient way (i.e. better than O(N^2)) to sort a large LinkedList that doesn't involve turning it into some other data structure to do the sorting. There is no efficient way (i.e. better than O(N)) to insert an element into the correct position in a previously sorted LinkedList. The third part (copying to an array) works equally well with a LinkedList or TreeSet; it is an O(N) operation in both cases.

[I'm assuming that the collections are large enough that the big O complexity predicts the actual performance accurately ... ]