List, Set and Map interfaces
A set is an Interface that provides an un-ordered collection of unique objects (does not contain duplicate values). In provides three general purpose implementations in Java.
HashSet stores its elements in a HashTable and does not guarantee of any type of ordering in iteration.
TreeSet orders its elements on the basis of their values.
It orders its elements on the basis of order in which they were inserted in the set.
A List is an ordered and indexed collection that can contain duplicate values. List allows null elements. It provides three general purpose implementations.
ArrayList is more general purpose and provides random access with index.
ArrayList is an expendable array of values or objects. If you need to access elements frequently by using index, ArrayList provides faster access if you know index. ArrayList represents an automatic re-sizeable array and used in place of array.
LinkedList is more suitable for frequently adding and removing elements from List. LinkedList also implements Deque interface, which provides first in first out operations.
Vector is synchronized and thread safe in nature.
A Map interface provides key-value pairs. Maps can not contain duplicate keys and one key can be mapped to atmost one element. In Java Map interface provides three general purpose implementations.
HashMap does not guarantee that the order of the objects will remain the same over the time.
List vs Set
1) Fundamental difference between List and Set in Java is allowing duplicate elements.
List in Java allows duplicates while Set doesn't allow any duplicate.
If you insert duplicate in Set it will replace the older value. Any implementation of Set in Java will only contains unique elements.
2) Another significant difference between List and Set in Java is order.
List is an Ordered Collection while Set is an unordered Collection.
LinkedList vs ArrayList
1) Since Array is an index based data-structure searching or getting element from Array with index is pretty fast.
Array provides O(1) performance for get(index) method but remove is costly in ArrayList as you need to rearrange all elements.
On the Other hand LinkedList doesn't provide Random or index based access and you need to iterate over linked list to retrieve any element which is of order O(n).
2) Insertions are easy and fast in LinkedList as compared to ArrayList because there is no risk of resizing array and copying content to new array if array gets full which makes adding into ArrayList of O(n) in worst case, while adding is O(1) operation in LinkedList in Java.
ArrayList also needs to update its index if you insert something anywhere except at the end of array.
3) Removal is like insertions better in LinkedList than ArrayList.
4) LinkedList has more memory overhead than ArrayList because in ArrayList each index only holds actual object (data) but in case of LinkedList each node holds both data and address of next and previous node.
List, Set and Map
1) If you need to access elements frequently by using index, than List is a way to go. Its implementation e.g. ArrayList provides faster access if you know index.
2) If you want to store elements and want them to maintain an order on which they are inserted into collection then go for List again, as List is an ordered collection and maintain insertion order.
3) If you want to create collection of unique elements and don't want any duplicate than choose any Set implementation e.g. HashSet, LinkedHashSet or TreeSet.
4) If you store data in form of key and value than Map is the way to go. You can choose from Hashtable, HashMap, TreeMap based upon your subsequent need.
You can remove duplicates or repeated elements from ArrayList in Java by converting ArrayList into HashSet in Java. But before doing that just keep in mind that Set doesn't preserver insertion order which is guaranteed by List, in fact that’s the main difference between List and Set in Java. So when you convert ArrayList to HashSet all duplicates elements will be removed but insertion order will be lost.
Program to delete duplicates from ArrayList
//ArrayList with duplicates String List duplicateList = (List) Arrays.asList("Android", "Android", "iOS", "Windows mobile"); System.out.println("size of Arraylist with duplicates: " + duplicateList.size()); //should print 4 becaues of duplicates Android System.out.println(duplicateList); //Converting ArrayList to HashSet to remove duplicates HashSet listToSet = new HashSet(duplicateList); //Creating Arraylist without duplicate values List listWithoutDuplicates = new ArrayList(listToSet); System.out.println("size of ArrayList without duplicates: " + listToSet.size()); //should print 3 becaues of duplicates Android removed System.out.println(listWithoutDuplicates);
size of Arraylist with duplicates: 4 [Android, Android, iOS, Windows mobile] size of ArrayList without duplicates: 3 [Android, Windows mobile, iOS]
Duplicate entry "Android" has been removed from ArrayList but order of ArrayList is not same.
Since we have converted ArrayList to HashSet we have lost insertion order of elements. There is another way of removing duplicates from ArrayList without losing order of elements, for that instead of HashSet we need to use LinkedHashSet, Which guarantees insertion order.
//Converting ArrayList to HashSet to remove duplicates LinkedHashSet listToSet = new LinkedHashSet(duplicateList);
Checking Array for duplicate elements Java
1) brute force method which compares each element of Array to all other elements and return true if it founds duplicates. Though this is not an efficient choice it is the one which first comes in mind.
2) Another quick way of checking if a Java array contains duplicates or not is to convert that array into Set. Since Set doesn’t allow duplicates size of corresponding Set will be smaller than original Array if Array contains duplicates otherwise size of both Array and Set will be same.
3) One more way to detect duplication in java array is adding every element of array into HashSet which is a Set implementation. Since add(Object obj) method of Set returns false if Set already contains element to be added, it can be used to find out if array contains duplicates in Java or not.