Removing duplicates from an array list of characters using a loop?

Question

public static ArrayList<Character> removeDuplicates (ArrayList<Character> data) {
    ArrayList<Character> newList = new ArrayList<Character>();

    for (int i = 0; i < data.size() - 1; i++) {
      if (!newList.contains(data.get(i))) 
         newList.add(0,(data.get(i)));
    }
    return newList;
  }

Here is my code so far. I'm not understanding how this is not working

This is a very inefficient implementation, but it should work — Dici, Sep 10 '15 at 20:47
I think you're always adding the the number to index 0, so it will just overwrite 0. Just use add(data.get(i)) to add it to the end of the list — jackie, Sep 10 '15 at 20:49
@Dici thanks for the correction. I should have read the documentation further. "Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices)." — jackie, Sep 10 '15 at 20:58

score 2 · Answer 1 · answered Sep 10 '15 at 21:00

2

You can use a Set. A Set is a Collection that doesn't let duplicates of Objects.

I'm not sure what Object type your List is of, but let's say your were using String:

//replace all instances of 'String' with whatever Object type you are using
Set<String> mySet = new HashSet<>();
for(String s : data){ 
  mySet.add(s);
}

Then if you want to send the data to a List, do:

ArrayList newList = new ArrayList(mySet);

answered Sep 10 '15 at 21:00

cbender

2,231
1
14
18

1

Using a set is good, but you don't need to populate it manually. You could just do `new ArrayList<>(new HashSet<>(data))`, but I guess this breaks the problem too easily – Dici Sep 10 '15 at 21:22

Ben M. · Accepted Answer · 2015-09-11T13:09:11.587

1

There are 2 problems with your implementation.

You're not counting all of the items in the array. You should do either i <= data.size() - 1 or i < data.size(). Right now you're missing the last item.
You're not adding items to the end of the list. Instead, you're repeatedly overwriting the zeroth (first) value. EDIT: Sorry, that was incorrect. You're inserting at the beginning of the list, which will work but is inefficient for the most commonly used lists (e.g. ArrayList).

Here is the fixed version. The problem areas are commented out with /* */.

List<Object> newList = new ArrayList<Object>();

for (int i = 0; i < data.size() /* - 1 */ ; i++) {
    if (!newList.contains(data.get(i)))
        newList.add( /* 0, */ (data.get(i)));
}

return newList;

EDIT: Using contains(...) on a list is slow. You can optimize and simplify this by using a Set. A set is a collection which has unique values. Adding the same value twice has no effect. We can take it a step further and use a LinkedHashSet as the implementation class, which will maintain the same ordering as was in the original list.

return new ArrayList<Object>(new LinkedHashSet<Object>(data));

edited Sep 11 '15 at 13:09

answered Sep 10 '15 at 20:57

Ben M.

2,370
1
15
23

1

As @Dici points out, #2 is incorrect. See javadocs: public void add(int index, E element) Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices). – jackie Sep 10 '15 at 20:59
1

@jackie Thanks, you're right. I updated my answer. – Ben M. Sep 10 '15 at 21:12
1

Actually the real good solution is using a `Set`, but I +1 the answer since it fixes the OP's code – Dici Sep 10 '15 at 21:20
@Dici Yes, you're absolutely right. I added an improved solution that uses a `LinkedHashSet`, which will also maintain the original list ordering. – Ben M. Sep 10 '15 at 21:23

Removing duplicates from an array list of characters using a loop?

2 Answers2