CODEWITHSUNDEEP
javaarraysarraylistset
nits.kk
nits.kk

Reputation: 5336

Why we use ArrayList when we could have used Set for adding unique values?

I found an efficient code for adding unique items using the below approach:

int[] values = { -5, -3, -1, 0, 3, 6 };

List<Integer> list=new ArrayList<Integer>();

for(int val : values)

{

   if(!list.contains(val))

   list.add(val);

}

I could have done the same work using a HashSet instead of using an ArrayList. That would have helped me by not worring to check if the value already existed in the list. Why is using a Hashset not an efficient approach?

Upvotes: 2

Views: 5271

Answers (3)

Andreas Dolk
Andreas Dolk

Reputation: 114847

A HashSet does not implement the List interface. And the values in a Set are not indexed. We can't get value from a Set.

So if you just need a storage for unique values, then you can safely use a Set implementation. If you need to keep insertion order or if you need any other functionality of List implementations and uniqueness, then use the method from your question: decorate an existing List implementation and add functionality to reject duplicates.

You asked about efficiency: ArrayList is backed by an array and pretty fast. But the time complexity for contains() is O(n) - to iterate we have look at each and every element in worst case.

HashSet is more or less a decorator of a full blown HashMap, somewhat heavier compared to an array. But the time complexity for contains is O(1) - the check is done in constant time, regardless how many items are inside the map.

If you just want to iterate - a specialized List implementation should be slightly faster - both have a time complexity of O(n) for the iteration (no surprise) but reading from an array is easier then reading from a Map.

Upvotes: 4

Stefan Kendall
Stefan Kendall

Reputation: 67892

It is. The premise to your question is flawed.

Use guava and it's easier:

Set set = Sets.newTreeSet( values ); //or HashSet

Upvotes: 1

C. K. Young
C. K. Young

Reputation: 223213

Actually, HashSet is a much better approach than ArrayList. Your code runs in O(n) for HashSet, and O(n²) for ArrayList.

But, one thing to keep in mind: elements in HashSet are not kept in any particular order. If you want to keep order and have fast lookups, use LinkedHashSet. (Everything has a cost, though; in this case, LinkedHashSet uses more memory than HashSet.)

Upvotes: 3

Related Questions