Removing duplicates in array with arraylist fails

Question

I wanted to remove duplicates from an array, by using an array list. The code seems to work fine for all cases except when String[]array contains three copies of an element. Why does this problem happen and how to fix it ?

Test input - 
array = {"D22", "D22", "D22"};

Output = 
D22
D22

Expected output = 
D22

public static String[] removeDuplicates(String [] array){
    String [] noDups = null;
    ArrayList<String> copy = new ArrayList<String>();
    String first = "";
    String next = "";

    for(String s: array){
        copy.add(s.trim());//Trimming
    }

    for(int i = 0; i < copy.size(); i++){

        for(int j = i + 1; j < copy.size(); j++){

            first = copy.get(i);
            next = copy.get(j);

            if(first.equals(next)){
                copy.remove(j);
            }

        }


    }

    noDups = copy.toArray(new String[copy.size()]);

    for(String s: noDups){
        System.out.println(s);

    }

    return noDups;
}

I know that could use a set instead. Btw, i prefer to use an arraylist for now. — Trojan.ZBOT
– Trojan.ZBOT, Commented Nov 25, 2013 at 5:37

Masudul · Accepted Answer · 2013-11-25 07:29:40Z

4

Try this, it is most simpler:

public static String[] removeDuplicates(String[] array) {
    ArrayList<String> res = new ArrayList<String>();

    for (String str : array) {
        if (!res.contains(str)) {
            res.add(str);
        }
    }
    return res.toArray(new String[res.size()]);
}

public static void main(String[] args) {
    String[] arr = {"D22", "D22", "D22"};
    String[] res = removeDuplicates(arr);
    for (String string : res) {
        System.out.println(string);
    }
}

Output: D22

edited Nov 25, 2013 at 7:29

answered Nov 25, 2013 at 5:58

Masudul

22k5 gold badges45 silver badges60 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Radiodef Over a year ago

This is also much safer though as an answer could do with an explanation of the OP's problem.

Masudul Over a year ago

@Trojan.ZBOT, How you print your value. I have posted full code with output. Now try again. No reason to print duplicate value.

Trojan.ZBOT Over a year ago

@Masud - Thanks. My mistake. I kept the code separately and it worked. Must be some error in the other code which I added.

vandale · Accepted Answer · 2013-11-25 05:40:22Z

2

It is because when you call remove, your counter is also incrementented, resulting in it skipping over an element. Something like

if(first.equals(next)){
  copy.remove(j);
  j--;
}

should fix this

answered Nov 25, 2013 at 5:40

vandale

3,6703 gold badges26 silver badges39 bronze badges

3 Comments

user949300 Over a year ago

A slightly simpler option is to have your loops count backwards.

Radiodef Over a year ago

This is why you aren't supposed to modify a list while looping over it. The while(Iterator#hasNext()) idiom is intended for this.

Radiodef Over a year ago

@Trojan.ZBOT Yes because your loop goes from 0 to list.size() and the control variable is used as an array index. It's bad because you modify the size and indexes while you are looping. There is actually an exception (ConcurrentModificationException) specifically about this. Pulling the list's Iterator and looping over that (typically with the above while condition) is safer because the iterator will take the removals in to account.

Vitruvie · Accepted Answer · 2013-11-25 05:48:03Z

1

When you remove an element from an array, each following element moves one space to the left. This causes you to effectively skip an element. Demonstration:

Initial state
Index:   0 1 2
Element: A B C
i: 0
j: 1
A=B, therefore A is removed
Index:   0 1
Element: B C
j: 2 (You increment it regardless of whether an element was removed)
j>=size(), therefore go to outer loop
i: 1
There is nothing after element C, therefore you're done.

answered Nov 25, 2013 at 5:48

Vitruvie

2,33519 silver badges25 bronze badges

Comments

Ankur Shanbhag · Accepted Answer · 2013-11-25 05:46:45Z

0

If you look at the for loop closely for(int j = i + 1; j < copy.size(); j++){ the value of copy.size() gets computed every time you iterate over the list. As you are removing the values from the copy list the size is diminished by one.

You are iterating as well as modifying the same list (by using copy.remove(j);) which is causing the issue.

Couple of alternatives to this:

Use Set instead of List. It will automatically remove duplicates.
Or when your are iterating over the copy list, add non-duplicate value to some other list list instead of modifying the copy list.

edited Nov 25, 2013 at 5:46

answered Nov 25, 2013 at 5:41

Ankur Shanbhag

7,8042 gold badges31 silver badges38 bronze badges

2 Comments

Trojan.ZBOT Over a year ago

I don't want to use a set for now.

Ankur Shanbhag Over a year ago

You can go with the second approach in that case.

Collectives™ on Stack Overflow

Removing duplicates in array with arraylist fails

4 Answers 4

3 Comments

3 Comments

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

3 Comments

3 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related