Remove List<String> duplicates using equals

Question

I'm fairly new to Java and I've been trying to solve the following problem unsuccessfully.

Write a Java method that will remove duplicates from a given list.

Assuming:

1. Method accepts type List
2. Return type is void
3. Duplicates are determined using equals()

Main:

1. Creates an instant of List and loads it with duplicate String values
2. Invoke removeDuplicates(), pass in this list
3. Outputs modified list to the console.

I can solve the problem by passing in my list to a new HashSet and copy it back. But the problem is:

1. Question is asking me to solve it using equals()...
2. If the return type is void, how can i output it in the main ?

import java.util.*; public class Question1 {

    public static void main(String[] args) {
String[] words = {"good","better", "best", "best", "first" , "last", "last", "last", "good"};  
        List<String> list = new ArrayList<String>();  
        for (String s : words) {  
            list.add(s);  
        }  
        removeDuplicates(list);
    }
    static void removeDuplicates(List<String> array){
        HashSet<String> hs = new HashSet<>();
        hs.addAll(array);
        array.clear();
        array.addAll(hs);
        for (String x : array){ 
            System.out.println(x);
        }
    }
}

EDIT: well, this one works, but as you can see i'm not using equals() and i'm printing out from my static method, not from main. Also, is there any way I can populate the List faster than using String[] ?

Answer 1

import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) {
        List<String> list = new ArrayList<String>();
        list.add("good");
        list.add("better");
        list.add("best");
        list.add("best");
        list.add("first");
        list.add("last");
        list.add("last");
        list.add("last");
        list.add("good");
        removeDuplicates(list);
        System.out.println(list.toString());
    }

    public static void removeDuplicates(List<String> list) {
        if (list != null) {
            for (int i = 0; i < list.size(); i++) {
                ListIterator<String> listIterator = list.listIterator();

                while (listIterator.hasNext()) {
                    int nextIndex = listIterator.nextIndex();
                    String nextElement = listIterator.next();
                    if (list.get(i).equals(nextElement) && i != nextIndex)
                        listIterator.remove();

                }

            }
        }

    }

}

Answer 2

The probably easiest way would be to use a Set in the first place, which by definition does not allow duplicates.

For your actual problem, you can do several approaches:

• The easy but slow approach: compare each element A with each other element N in the list. If A.equals(N) remove N. Hint: you only need to compare A to each further element, as you have already checked each element before A.

• The faster approach: sort the list using the natural comperator. Now you no longer need to compare each element A vs N, but only A vs the next few elements. To be exact: until you find the first element that is not equal to A. In this case you can assume that there is no further duplicate of A (thanks to the sorting) and continue with this next element as A.

• The Map approach (fast but takes more memory): for each element put into the list, put the same element into a Map with any Object as value. Now you can just look-up whether or not that element is already in the map, and if it is, it is a duplicate.

The best way would be the 2nd approach as the sorting is very fast, you only need to get each element once, and there is no 2nd list necessary.

Edit: The 2nd approach in code:

static void removeDuplicates(List<String> array) {
  if (array.size() <= 1) {
    return;
  }
  Collections.sort(array);
  final Iterator<String> it = array.iterator();
  String a = it.next(), n;
  while (it.hasNext()) {
    n = it.next();
    if (((a == null) && (n != null))
            || ((a != null) && (a.equals(n) == false))) {
      a = n;
    } else {
      it.remove();
    }
  }
}

Answer 3

Here's how you would do the same thing without using a Set and just using equals() (also to somewhat answer your "EDIT" question about initializing a List) :

  public static void main(String[] args) {
    List<String> list = new ArrayList<String>(Arrays.asList(new String[] {
        "good", "better", "best", "best", "first", "last", "last", "last",
        "good"}));
    removeDuplicates(list);
    for (String x : list) {
      System.out.println(x);
    }
  }

  static void removeDuplicates(List<String> array) {
    for (int i = 0; i < array.size(); i++) {
      String next = array.get(i);

      // check if this has already appeared before
      for (int j = 0; j < i; j++) {
        // if it has, stop the search and remove it
        if (next.equals(array.get(j))) {
          array.remove(i);
          // decrement i since we just removed the i'th element
          i--;
          // stop the search
          break;
        }
      }
    }
  }

That said, using HashSet is a better idea since as has already been pointed out it is more efficient.

If you want the efficiency of HashSet but still preserve the order of the List you could do something like this :

  static void removeDuplicates(List<String> array) {
    Set<String> set = new HashSet<String>();

    for (int i = 0; i < array.size(); i++) {
      String next = array.get(i);

      // check if this has already appeared before
      if (!set.add(next)) {
        // if it has then remove it
        array.remove(i);
        // decrement i since we just removed the i'th element
        i--;
      }
    }
  }

Answer 4

1. removeDuplicates creates a set, then iterates over the input list. If it encounters an element in the input list, that is also in the set, removeDuplicates removes the element from the input list, otherwise it adds the element to the set.
2. Java is a call-by-reference language (sort of). This means, the method removeDuplicates can modify the List<String> array that it receives and the caller will see that modified list after the call to removeDuplicates returned.

Answer 5

java.util.HashSet uses Object.equals(Object) in its implementation of Set.add(Object) to determine that the element being inserted is unique (as defined by not being equal to another element). HashSet also has the advantage of allowing you to do the de-duping process in O(n) time vs a more naive approach of comparing every element to every other element in O(n^2) time.

The code in main will see the modified list, because the List object is mutable. When a method changes the state of a passed in argument the calling code will see those changes.