How can I delete repeated elements in an indexed list?

Question

I have this method:

static <E> IndexedList<E> deleteRepeated(IndexedList<E> l)

and USING:

IndexedList<E> list = new ArrayIndexedList<E>();

By the moment the code I have is this, but it doesn't work

   for (int i = 0; i < l.size(); i++) {
    int repeated = 0;
    if (l.contains(l.get(i))) {
        repeated++;
        if (repeated < 1) {
            list.add(l.get(i));
        }
    }
}
return list;

}

Answer 1

While perhaps not the best performing solution, I'd just create a LinkedHashSet that will remove duplicates (while retaining the original order of the first appearances of every element) and then convert it back to a List:

private List<String> removeRepeated(List<String> originalValues) {
    return new ArrayList<>(new LinkedHashSet<>(originalValues));
}

Answer 2

Java 8: list.stream().distinct().collect(Collectors.toList());

Stream Documentation: https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html

Answer 3

The first thing to note is that your check:

    if (l.contains(l.get(i)))

will always return true, since you're checking if the list has an element that is obtained from that list. You need to check instead if the new list already has that element. And there's no need for the repeated variable.

Here's how to do it for short lists (up to about 100 elements):

    for (int i = 0; i < l.size(); i++) {
    if (!list.contains(l.get(i))) {
        list.add(l.get(i));
    }
    return list;

The problem with using the above for larger lists is that it can get very slow. Every time you check an element, you are traversing the list (that's what list.contains does internally). To make it faster, use a HashSet to check for duplicates:

    Set<E> uniqueValues = new HashSet<>();
    for (int i = 0; i < l.size(); i++) {
    if (uniqueValues.add(l.get(i))) {
        list.add(l.get(i));
    }
    return list;

By the way, I assume this to be an exercise in algorithm design. We don't write code like this in the real world, but instead we use already existing facilities provided by the standard Java API.

Answer 4

As others have mentioned previously, IndexedList doesn't belong to the standard Java API. In my case, it belongs to a provided library for Algorithms exercises, that I'm currently using. I don't know if it shares the same methods as the ones OP used. My approach to that code is similar to the ideas of the other contributors, but I'll post it in case it helps anyone else:

public static <E> IndexedList<E> deleteRepeated (IndexedList<E> list)
{
    //Boolean to check if the current element has already been copied to newList, in order to avoid duplicates
    boolean copied = false;
    //Create new IndexedList to store the result
    IndexedList<E> newList = new ArrayIndexedList<E>();
    //If an empty list is provided, just return newList
    if (list.size() == 0)
    {
        return newList;
    }
    //Iterate over all the elements of list
    for (int i = 0; i <= list.size() - 1; i++)
    {
        //If newList is empty, simply insert the first element of list
        if (newList.isEmpty())
        {
            //First value represents the position of the IndexedList, and second value represents the element you want to add
            newList.add(0, list.get(0));
        }
        else
        {
            //Reset boolean variable
            copied = false;
            //Now iterate over the newList, and check if the current element has been previously copied or not
            for (int j = 0; j <= newList.size() - 1 && !copied; j++)
            {
                if (list.get(i).equals(newList.get(j)))
                {
                    copied = true;
                }
            }
            //Finally check the value of the boolean, to see if there are any previous appearances of the current element
            //If not, then add it to the end of newList. Else, we move on to next element of list
            if (!copied)
            {
                newList.add(newList.size(), list.get(i));
            }
        }
    }
    //Return the IndexedList (newList), without the duplicate elements in the same order.
    return newList;
}