Logo

Programming-Idioms

History of Idiom 119 > diff from v34 to v35

Edit summary for version 35 by programming-idioms.org:
[Java] Valid but not efficient

Version 34

2018-04-07, 10:26:14

Version 35

2018-04-08, 22:47:11

Idiom #119 Deduplicate list

Remove duplicates from list x.
Explain if original order is preserved.

Illustration

Idiom #119 Deduplicate list

Remove duplicates from list x.
Explain if original order is preserved.

Illustration
Extra Keywords
deduplicate dupe dupes redundant redundancy
Extra Keywords
deduplicate dupe dupes redundant redundancy
Imports
import java.util.HashSet;
import java.util.Set;
import java.util.Iterator;
Imports
import java.util.HashSet;
import java.util.Iterator;
Code
final HashSet<T> seen = new HashSet<T>();
final Iterator<T> listIt = x.iterator();
while (listIt.hasNext()) {
  final T curr = listIt.next();
  if (seen.contains(curr)) {
    listIt.remove();
  } else {
    seen.add(curr);
  }
}
Code
final HashSet<T> seen = new HashSet<T>();
final Iterator<T> listIt = x.iterator();
while (listIt.hasNext()) {
  final T curr = listIt.next();
  if (seen.contains(curr)) {
    listIt.remove();
  } else {
    seen.add(curr);
  }
}
Comments bubble
Preserves the order of the items.
Upon first occurrence, store item in seen; all future occurrences of the item are removed from the list efficiently via the iterator listIt, removing the last-returned item.
Requires extra memory for the hash-set.
Comments bubble
Preserves the order of the items.
Upon first occurrence, store item in seen; all future occurrences of the item are removed from the list via the iterator listIt, removing the last-returned item.
Requires extra memory for the hash-set.

Note that the runtime cost is O(n^2).
Doc URL
https://docs.oracle.com/javase/7/docs/api/java/util/Iterator.html
Doc URL
https://docs.oracle.com/javase/7/docs/api/java/util/Iterator.html