Data Structure: Uniqueness in lists

i have 2 lists,one list l1 contains n1 elements and another list l2 contains n2 elements.Both lists are not the sam开发者_如何学Ce length and contain duplicate elements.I want to create another list which has unique elements from both l1 and l2.How can i do this efficiently and what would be the performance of this solution?

P.S : i want a solution which does not make use of any other data structures.

---

If you can't use a Set, I think the best solution is to do a merge-sort with no duplicates. This SO question might help: How do I use merge sort to delete duplicates?

---

If you have to use only lists, and you have the possibility of duplicates both within each list AND across lists, then you need to create a new list, l3 (to hold the union of l1 and l2 elements) and iterate through each list, doing an insert of each element e item if a call to l3.contains(e) returns false.

As others have mentioned, using a Set is definitely the easiest way to remove duplicate items of a list, and a List can be created from the Set to return to the caller.

The performance is linear and based on the number of elements in l1 + l2.

---

A solution that's O(nlogn) would be to sort each list, then walk through both lists together, finding duplicates. You would increment the position of one list or the other list (or both) depending on which list has the "smallest" value of the current element (or if they're the same). There's a reasonable bit of overhead, so some O(n^2) algorithms could actually could be faster depending on the size/distribution of the data.

---

Create a new Set and add elements from both the Lists l1 and l2. The final set will be the one that contains no duplicates. But make sure you have implemented the equals() and hashCode() correctly.

Below is my sample (not perfect) for doing the same. Posting it here it to validate my logic ;-) or to see if there are better ways of optimizing this

Lit unique=...


if(l1.size==l2.size())
{
    //o(n)
    copyToUnique(l1, l2, unique)
}
else if(l1.size>l2.size())
{
    //o(n) + num of extra elements
    copyToUnique(l1, l2, unique)
    unique.addAll(l1.subList(l2.size(),l1.size());
}
else if(l1.size<l2.size())
{
    //o(n) + num of extra elements
    copyToUnique(l2, l1, unique)
    unique.addAll(l2.subList(l1.size(),l2.size());
}

public void copyToUnique(List l1, List l2, List unique)
{
    for(Object element:l1)
    {
        if(!l2.contains(element))
        {
            unique.add(element);
        }
    }
unique.addAll(l2);
}