ArrayList Duplicate Removal

Question

Here's my code:

public static void deleteDuplicates(ArrayList<String> list){
    ArrayList<String> newList = new ArrayList<String>();
    HashSet<String> set = new HashSet<String>();

    for(int i = 0; i < list.size(); i++){
        set.add(list.get(i));
    }

    newList.addAll(set);
    return newList;
}

My input for this is the following:

1, 2, 2, 3, 4, 3, 1, 5, 5, 4, 1, 4, 5

And the output I'm getting is:

3, 2, 4, 1, 5

Can anyone explain why this is out of order?

Set data structure does not maintain order. But if you want sorted then you can use Tree Set. — Shivam, Feb 19 '13 at 03:12
@ShivamKalra you mean `HashSet`, because [`LinkedHashSet`](http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashSet.html) does. — Luiggi Mendoza, Feb 19 '13 at 03:16
@LuiggiMendoza No, I mean any set data structure. Linked Hashset keeps a Linked List internally to keep order. — Shivam, Feb 19 '13 at 03:18
Ah, I figured it out. Thanks I didn't know that about HashSets. — Matthew Brzezinski, Feb 19 '13 at 03:18
LinkedHashSet maintains the order the elements were inserted in. TreeSet order the elements according to their natural order. — Cyrille Ka, Feb 19 '13 at 03:18
@ShivamKalra `Set` is the interface, and `HashSet` is an implementation. Next time choose the right words :). — Luiggi Mendoza, Feb 19 '13 at 03:19
Coincidentally, both would give `1, 2, 3, 4, 5` here because of the input order. — Cyrille Ka, Feb 19 '13 at 03:19
@LuiggiMendoza In computer science `Set` is a data structure. — Shivam, Feb 19 '13 at 03:21
@ShivamKalra yes, but this is Java, so you can't say *`Set` data structure does not maintain order.* when there is a `Set` implementation that does it. — Luiggi Mendoza, Feb 19 '13 at 03:23

score 5 · Accepted Answer · edited May 23 '17 at 12:25

5

Change HashSet for LinkedHashSet:

Hash table and linked list implementation of the Set interface, with predictable iteration order.

Also, remember to always program to an interface:

public static void deleteDuplicates(List<String> list){
    List<String> newList = new ArrayList<String>();
    Set<String> set = new LinkedHashSet<String>();
    //rest of your code
}

edited May 23 '17 at 12:25

Community

1
1

answered Feb 19 '13 at 03:17

Luiggi Mendoza

85,076
16
154
332

1

@user1327636 don't forget to program interface oriented, not to class implementations (check the link provided in my answer). – Luiggi Mendoza Feb 19 '13 at 03:19

score 1 · Answer 2 · answered Feb 19 '13 at 03:19

1

Quoting from the HashSet class documentation:

It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time.

answered Feb 19 '13 at 03:19

christianhs

81
1
4

score 1 · Answer 3 · answered Feb 19 '13 at 03:20

I'm sure there's a more effecient way but here's an idea for an n^2 algorithm for removal

public static void deleteDuplicates(ArrayList<String> list){
ArrayList<String> newList = new ArrayList<String>();

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

boolean exists = false;
String str = list.get(i);
for (int j = 0; j < newList.size(); j++){
if (newList.get(j).compareTo(str)==0){
exists = true;
break;
}
}
if (!exists) newList.add(str);
}
return newList;
}

ArrayList Duplicate Removal

3 Answers3