Remove duplicates from java list without using sets

Question

Java beginner, so please bear with possibly silly questions.

I have a list of Strings which contains multiple duplicates and I want to detect and remove these duplicates. I know there's an easy way to do this with HashSet, and I've actually got it to work like that. But originally I was trying to do it in another way, also quite simple, in which there's something wrong and I don't understand what it is.

Given an array of strings with one duplicate, say {"A", "B", "C", "A"}, I can detect and replace the duplicate ("A" here). But if I have an array of strings with multiple duplicates, say {"A", "B", "C", "A", "E", "A"}, something goes wrong in the loop inside my method "replaceDuplicate()".

I need help to understand where the problem is in the following code:

public class TryTask_B2_Vector {

public static void main(String[] args) {

    // Create array of strings for all the 'Gars':
    String[] garList = new String[] {"A", "B", "C", "A", "E", "A"};


    // Display the original "ArrayList" of 'Gars':
    System.out.println("Original list of Gars: " + garList);
    System.out.println();

    bruteForce(garList);
    System.out.println(bruteForce(garList));
    System.out.println();

    replaceDuplicate(garList);
    System.out.println();

    bruteForce(garList);
    System.out.println(bruteForce(garList));
    System.out.println();

    System.out.println("New list of Gars: " + garList); 

}    


    public static boolean bruteForce(String[] input){

    for(int i=0; i < input.length; i++){
        for(int j=0; j < input.length; j++){
            if(input[i].equals(input[j]) && i != j){
                return true;
            }
        }
    }
    return false;
}


    public static String[] replaceDuplicate(String[] input){

        for(int i=0; i < input.length; i++){
            for(int j=0; j < input.length; j++){
                if(input[i].equals(input[j]) && i != j){
                    input[j] = input[j].replace(input[j], "null");
                    System.out.println(input[j]);
                }
            }
        }    
        return input;
    }        
}

"something goes wrong in the loop" - Since we don't have a crystal ball, can you expand what you're expecting to see and what actually happens? — Paolo, Jul 21 '14 at 10:17
On each element of array you need to traverse this array checking if current element is equal to some other element in array. And if so you take current element and replace it. — Volodymyr Levytskyi, Jul 21 '14 at 10:21
In the case of a single duplicate, {"A", "B", "C", "A"}, the result of the loop in method replaceDuplicate() is only one "null" (the replacement for the single duplicate "A"), as expected. With multiple duplicates, the result of the same loop is multiple "null" printouts. and the number of these "null" replacements corresponds neither to the number of duplicates nor to the number of original elements in the list... — user3729787, Jul 21 '14 at 10:23
What does it mean "to traverse the array"? could you show me an example? As I said in my question, I'm a Java beginner! — user3729787, Jul 21 '14 at 10:25
why not initialize the array's duplicates elements with `null` instead of `"null"` — Shailesh Aswal, Jul 21 '14 at 10:37
@user3729787 maybe you can use one of the solutions from this thread http://stackoverflow.com/questions/2435156/java-removing-duplicates-in-an-arraylist/2484165. Similar questions were already asked http://stackoverflow.com/search?q=java+list+remove+duplicates and http://stackoverflow.com/search?q=java+list+remove+dupes. Cheers — SubOptimal, Jul 21 '14 at 10:42

Syam S · Answer 1 · 2014-07-21T11:00:07.060

The program works fine and it replaces the duplicates with the String "null". So the output of { "A", "B", "C", "A", "E", "A" } would be [A, B, C, null, E, null]. There are two confusing bits in the print out statements. One the second bruteForce() method still returns true stating there are still duplicates. Actually this duplicate value is the string "null". Second the multiple null print outs. In the replaceDuplicate() you are first setting value to "null" and then do the printing which will always print null.

Another point. The inner loop for j need not start from 0. We just need to look ahaead for duplicates. So it could start from (i+1) for (int j = i+1; j < input.length; j++). Saves some additional looping and you could avoid i != j check.

Modify your program like

import java.util.Arrays;

public class TryTask_B2_Vector {

    public static void main(String[] args) {

        // Create array of strings for all the 'Gars':
        String[] garList = new String[] { "A", "B", "C", "A", "E", "A" };

        // Display the original "ArrayList" of 'Gars':
        System.out.println("Original list of Gars: " + Arrays.toString(garList));
        System.out.println();

        bruteForce(garList);
        System.out.println("Has duplicates : " + bruteForce(garList));
        System.out.println();

        replaceDuplicate(garList);
        System.out.println();

        bruteForce(garList);
        System.out.println("Has duplicates : " + bruteForce(garList));
        System.out.println();

        System.out.println("New list of Gars: " + Arrays.toString(garList));

    }

    public static boolean bruteForce(String[] input) {

        for (int i = 0; i < input.length; i++) {
            for (int j = i+1; j < input.length; j++) {
                if (!"null".equals(input[i]) && input[i].equals(input[j])) {
                    return true;
                }
            }
        }
        return false;
    }

    public static String[] replaceDuplicate(String[] input) {

        for (int i = 0; i < input.length; i++) {
            for (int j = i+1; j < input.length; j++) {
                if (!"null".equals(input[i]) && input[i].equals(input[j])) {
                    System.out.println("Duplicate found : " + input[j]);
                    input[j] = input[j].replace(input[j], "null");
                }
            }
        }
        return input;
    }
}

score 1 · Answer 2 · answered Jul 21 '14 at 10:33

The problem is in your bruteforce method. You are expecting it to return false after you have removed all the duplicates, but this is not the case. Your replace method is working ok and putting the String null where the duplicates A appeared. It is putting in more than one String null (one for each extra 'A' ) and because of this your bruteforce method still sees duplicates and still returns true. Just add

if(!input[i].equals("null"))

To your bruteforce method and it should be fine

score 1 · Accepted Answer · answered Jul 21 '14 at 10:56

Probably need some modifications but:

@Test
public void test(){
    String[] garList = new String[] {"A", "B", "C", "A", "E", "A"};

    //remove duplicates 
    String[] noDup = new String[garList.length];
    for(int i =0; i<garList.length; i++){
        if(!contains(noDup, garList[i])){
            noDup[i] = garList[i];
        }
    }
    System.out.println(Arrays.toString(noDup));
    // move nulls to the end
    String[] tailNull = new String[garList.length];
    int j = 0;
    for (int i = 0; i < noDup.length; i++) {
        if(noDup[i]!=null){
            tailNull[j] = noDup[i];
            j++;
        }
    }
    System.out.println(Arrays.toString(tailNull) + "/" + j);
    // copy range of not null elements 
    String[] noNull = new String[j];
    System.arraycopy(tailNull, 0, noNull, 0, j);
    System.out.println(Arrays.toString(noNull));
}

boolean contains(String[] array, String o){
    for (int i = 0; i < array.length; i++) {
        if(o.equals(array[i]))
            return true;
    }
    return false;
}

remove duplicates and duplicated nulls.

score 0 · Answer 4 · answered Dec 08 '15 at 04:32

by using the 2 ways we can remove the duplicate elements from list object in java..i.e 1. by using for each 2. by using iterator ex. using for each

ArrayList<String> wordDulicate = new ArrayList<String>();
ArrayList<String> tempList= new ArrayList<String>();

wordDulicate.add("Tom");
wordDulicate.add("Jones");
wordDulicate.add("Sam");


for (String dupWord : wordDulicate) {
    if (!tempList.contains(dupWord)) {
        tempList.add(dupWord);
    }
}

2. by using iterator

ArrayList l1 = new ArrayList();
ArrayList l2 = new ArrayList();

Iterator iterator = l1.iterator();

    while (iterator.hasNext())
    {
        YourClass o = (YourClass) iterador.next();
        if(!l2.contains(o)) l2.add(o);
    }

hit like if you like the answer...

Remove duplicates from java list without using sets

4 Answers4