List Only

Removing duplicate items in an array list (java)?

Hi. The example problem I am looking at is asking us to make an ArrayList and remove all of the duplicates from it. The example tells us not to use a HashSet (or anything with the word hash in it.) The code I have doesn't work properly.. as it removes some of the duplicates, but it removes "Greg", which isn't a duplicate. I feel like the method I have with the embedded loop is almost right, but I am missing one command. Code ~ import java.util.ArrayList; public class ArrayPrac5 { public static ArrayList deleteDuplicates (ArrayList <String> list) { String str = ""; for (int i = 0; i < list.size(); i++) { str = list.get(i); for (int k = 0; k < list.size(); k++) { if (list.get(k) == str) { list.remove(k); } } } return list; } public static void main (String [] args) { ArrayList <String> list = new ArrayList(); list.add("Chris"); list.add("Chris"); list.add("Greg"); list.add("Greg"); list.add("Chris"); list.add("Bob"); ArrayList <String> list2 = ArrayPrac5.deleteDuplicates(list); for (int i = 0; i < list2.size(); i++) { System.out.println("" + list2.get(i)); } } }

Public Comments

1. Oops, my bad. The following would be a really easy way to do it. List<String> mySet = new ArrayList<String>(); for(String listEntry : list){ if(mySet.contains(listEntry)==false){ mySet.add(listEntry); } } Another funky way would be to do the following: List<String> myListSet = new ArrayList<String>(){ public void add(Object entry){ if(false == this.contains(entry)){ super.add(entry); } } } So duplicates can't get added to the list in the first place :-) edit: In practice you would always use a Set where you wouldn't want duplicates. And if memory constraints were an issue. For example large prime number calculation on limited infrastructure i'd use object arrays as opposed to lists. Or in J2ME careful use of Object pointers so you canbe assured of garbage collection. In every workplace I have ever been in what costs you more is rewriting code which isn't clear or has low or poor test coverage. So if another developer cannot tell what your code is doing on initial inspection, you've probably written it wrong... edit2: it's worth pointing out that in lists if you hold concrete objects then it is the memory pointer which is shared across multiple lists. And therefore this object is not duplicated across lists. In this way using a secondary list to check for duplicates is not an expensive process.
2. In the inner loop you're not checking whether i is different than k. list[i] == list[k] always, when i = k, so you're essentially removing all elements. You could just add the check: if (list.get(k) == str && i!=k) .... In terms of efficiency though, it's terrible. How important that is only matters on how it's marked. You could create a new object and use contains(), just as another answer. Or use lastIndexOf() for (int i = 0; i < list.size(); i++) { if(list.lastIndexOf( list.get(i) ) != i) list.remove(i); } The version above will save a little bit of ram and run a tad quicker (depending on the number of duplicates).