If you do anything with a specified index, LinkedList scans from the
nearer end of the list to find the place. Finding the next element from
an iterator should be faster.

That sounds like an O(n*n) method for merging two lists, each containing
n elements, even if you use iterators.

Sort-and-merge is O(n log n). You only have to look at the head elements
of each list, move the smaller to the result, dropping any duplicates
from either list.

Dumping all the data into a HashSet is O(n). It is also VERY simple to
code, using addAll.

Patricia

   Are we talking about linked lists, or are we talking about Sun's class,
java.util.LinkedList? Inserting into java.util.LinkedList at an arbitrary
position is O(n), the implementation has to "seek" to that arbitrary
position. A different implementation of linked list might have different
asymptotic runtime performance.

   Given that you said the list are unsorted, how would you determine what
the "corresponding" position is?

   Yes, but using a HashSet will probably be faster.

   - Oliver

Can any of these support inserting a new element into the middle of the
ordering? Well, the first can't, and the third and fourth can if you do
the "BASIC line numbering trick" and give every item a position number,
where you leave gaps so you can fill in missing positions later. That's
a bit of a hack (but it can be done, e.g. using doubles and suggesting
the client code insert baz between foo and bar by setting
(foo.getPosition() + bar.getPosition())/2 as the position for baz.

Of course, once you are comparing stuff using a position number field
you set to suit, you're looking at a comparator that isn't consistent
with equals, which is going to bomb your TreeSet anyway. Now you need
the objects to use their position number to decide equality (and hash
code) too. You probably actually want to wrap them with a

public class PositionalHolder<T>
        implements Comparable<PositionalHolder<T>> {
    public double position;
    public T object;
    public PositionalHolder (T object, double position) {
        this.object = object;
        this.position = position;
    }
    @SuppressWarnings("unchecked")
    public void equals (Object x) {
        return (x == this)
            ||(x instanceof PositionalHolder
            && ((PositionalHolder)x).position
            == position);
    }
    public int hashCode () {
        return Double.valueOf(position).hashCode();
    }
    public int compareTo (PositionalHolder<T> other) {
        return (position < other.position)
            ?-1:((position > other.position)?1:0);
    }
    public void putBetween (PositionalHolder<T> x,
            PositionalHolder<T> y) {
        // Convenience method.
        position = (x.position + y.position)/2;
    }
}

Of course, Bad Things will likely happen if you a) use infs or nans as
positions, b) use the same position for multiple objects in the same
ordered collection, or c) change something's position while it's in one
rather than remove it, change its position, and then reinsert it. You
might want to prevent the last by making the PositionalHolder immutable
with a (x, object, y) "between" constructor, a just-an-object
constructor (position gets zero), a "before" constructor (object, y)
that uses y.position - 1, and an "after" constructor (x, object) that
uses x.position + 1. (This overload is clearly ambiguous if you try to
put a PositionalHolder inside another PositionalHolder but why the hell
would you?)