Removing duplicates in an ArrayList using Generics

Question

I was asked to write a small program to remove the duplicates from a list and make a new list without the duplicates. We had to do this using Generics in Java. This is what I have so far:

All help is greatly appreciated!!!

import java.util.ArrayList;

public class Assignment13 {


public static void main(String[] args) {
    ArrayList<String> list = new ArrayList<String>();
    list.add("one");
    list.add("one");
    list.add("two");
    list.add("three");
    list.add("three");


    System.out.println("Prior to removal: " + list);
    System.out.println("after: " + list2);


}

public static <E> ArrayList<E> removeDuplicates(ArrayList<E> list) {

    ArrayList<E> list2 = new ArrayList<E>();

    for (int i = 1; i < list2.size(); i++) {
        String a1 = list2.get(i);
        String a2 = list2.get(i-1);
        if (a1.equals(a2)) {
            list2.remove(a1);
        }
    }


    return list2;

 }

}

You initialize an empty `list2` then try to iterate over it. Do you see a problem here? — k_g, Apr 01 '15 at 18:25
There is a variety of answers to similar problems on SO. Check [this](http://stackoverflow.com/a/203992/4235784) for a brief yet elegant solution. — altocumulus, Apr 01 '15 at 18:35

Anderson Vieira · Answer 1 · 2015-04-01T21:06:56.440

From your question it seems that there is no guarantee that duplicated elements in the original list must appear in sequence. This means that checking if two adjacent elements are equal is not sufficient to remove all duplicates.

Checking adjacent elements would work if the list was sorted. But since you need to use generics, I suppose you are not allowed to make assumptions about the nature of the elements. This means you cannot sort the list, because you would need to know that the elements were Comparable.

So you can do it like this:

1. Create a new empty list
2. For each element in the original list
    2.1 If the element is not in the new list, add it
    2.2 Else, ignore it

If you are allowed to use Java 8, this is much easier:

static <E> List<E> removeDuplicates(List<E> list) {
    return list.stream().distinct().collect(Collectors.toList());
}

score 0 · Answer 2 · answered Apr 01 '15 at 18:33

0

This is the algorithm:

public static <E> ArrayList<E> removeDuplicates(ArrayList<E> list) {

    ArrayList<E> list2 = new ArrayList<E>();

    for (E elem : list) 
        if (!list2.contains(elem))
            list2.add(elem);

    return list2;

 }

answered Apr 01 '15 at 18:33

Héctor

24,444
35
132
243

score 0 · Answer 3 · answered Apr 01 '15 at 18:35

You can achieve this with a loop and a condition:

public static <E> ArrayList<E> removeDuplicates(ArrayList<E> list) {
    ArrayList<E> list2 = new ArrayList<E>();

    for(E item : list) {
        if(!list2.contains(item)) {
            list2.add(item);
        }
    }

    return list2;
}

score 0 · Answer 4 · answered Apr 01 '15 at 18:42

Using a Set (if allowed in your assignment) is more efficient than checking list.contains on each item. Ex:

public static <E> ArrayList<E> removeDuplicates(ArrayList<E> list) {
    Set<E> uniques = new HashSet<E>();
    uniques.addAll(list);
    return new ArrayList<E>(uniques);
}

Luis Casillas · Answer 5 · 2015-04-01T18:54:52.590

The general strategy here is that you want to maintain a context as you traverse the list, and at each step, you use that piece of context to answer the question of whether the current item should be kept or thrown out. In pseudo-code:

public static <A> List<A> removeDuplicates(List<? extends A> original) {
    List<A> result = new ArrayList<A>();

    /* initialize context */        

    for (A item : original) {
        if ( /* context says item is not a duplicate */ ) {
            result.add(item);
        }
        /* update context to incorporate the current `item` */
    }
    return result;
}

Some people have brought up the question of whether you mean consecutive duplicates or non-consecutive ones. In reality, the difference in the solutions is small:

For consecutive duplicates the context is the most recently seen item.
For non-consecutive it's the Set<A> of all items seen up to that point.

I'll let you fill in the pattern for those cases.

Kevin Mee · Answer 6 · 2015-04-01T18:39:04.303

-1

Updated for your question

 ArrayList<E> list2 = new ArrayList<E>();


    for (int i = 1; i < list.size(); i++) {
        String a1 = list2.get(i);
        if (!list2.contains(a1)) {
            list2.add(a1);
        }
    }

edited Apr 01 '15 at 18:39

answered Apr 01 '15 at 18:28

Kevin Mee

539
3
14

It does solve the initial problem, but does not solve the main question at hand – Saif Asif Apr 01 '15 at 18:30
I tried to do that but it did not work. For some reason my for loop is not taking out the duplicates. – Alex Garcia Apr 01 '15 at 18:31
a) you didn't return list2, b) you made list2 a reference to list instead of copying the elements (therefore you will modify list by side effect). – spudone Apr 01 '15 at 18:38
@spudone i accidentally left list2 = list from before edit.. i have removed it – Kevin Mee Apr 01 '15 at 18:39
1) `a1` is not a `String`, but a `E` 2) You are getting a object from a list and then are checking if the same list contains it. – Héctor Apr 01 '15 at 18:40

Removing duplicates in an ArrayList using Generics

6 Answers6