5. List 🆚 Set 🆚 Map
List, Set and Map are the interfaces which implements Collection interface. Here we will discuss difference between List Set and Map in Java.
Listrepresents an ordered sequence of values where some value may occur more than one time.
1. Duplicity
| Collection | Duplicity |
|---|---|
| List | ✔️ Elements can be duplicated without affecting other values and their indexes |
| Set | ❌ Every element should be unique |
| Map | ❌ Elements are stored as key/value pairs, duplicate keys are not allowed |
2. Null values
| Collection | Null Values |
|---|---|
| List | Allows any number of null values |
| Set | Allows a single null value at most |
| Map | Allows a single null key at most and any number of null values |
3. Order
| Collection | Order |
|---|---|
| List | Maintains the insertion order |
| Set | No order generally, some exceptions such as LinkedHashSet (insertion order) |
| Map | No order generally, some exceptions such as: TreeMap (ascending order of keys) LinkedHashMap (insertion order) |
4. When to use List, Set and Map in Java?
| Collection | Requirement |
|---|---|
| List | - Need for frequent search operations (based on index values) - Need to maintain order |
| Set | - No duplicates |
| Map | - Need to store key & value mappings - Performance for insert and retrieve a value is O(1) on average |
5. Commonly used structures
List implementations
| List implementation | Usage | Insertion | Search |
|---|---|---|---|
| ArrayList | A List implementation built atop an array, which is able to dynamically grow and shrink as you add/remove elements. Elements can be easily accessed by their indexes | O(n) | O(n) for unsorted array O(log n) for a sorted one |
| LinkedList | Doubly-linked list implementation of the List and Deque interfaces. Every element is a node, which keeps a reference to the next and previous ones. Insertion is faster, Search is slower. Memory usage higher | Faster than ArrayList | O(n) |
| Vector | The Vector class implements a growable array of objects. Like an array, it contains components that can beaccessed using an integer index. It isn't as good as an ArrayList performance-wise but is thread-safe/synchronized | ||
| Stack | For the new implementations, we should prefer a Deque interface and its implementations. Deque defines a more complete and consistent set of LIFO operations. LIFO (last in, first out) collection of objects allowing for pushing/popping elements in constant time |
Set implementations
| Set Implementation | Description |
|---|---|
| HashSet | - It stores unique elements and permits nulls - It's backed by a HashMap - It doesn't maintain insertion order - It's not thread-safe |
| TreeSet | - It stores unique elements - It doesn't preserve the insertion order of the elements - It sorts the elements in ascending order - It's not thread-safe |
Map implementations
| Map Implementation | Description |
|---|---|
| HashMap | Implemented as a hash table, there is no ordering on keys or values |
| TreeMap | TreeMap will iterate according to the "natural ordering" of the keys according to their compareTo() method (or an externally supplied Comparator). Additionally, it implements the SortedMap interface, which contains methods that depend on this sort order |
| LinkedHashMap | LinkedHashMap will iterate in the order in which the entries were put into the map |
| HashTable | Hashtable is synchronized in contrast to HashMap. |
| IdentityHashMap | Unlike other Map implementations (e.g. HashMap, Hashtable, WeakHashMap or EnumMap) it uses equality operator == instead of equals |
| WeakHashMap | Its keys are WeakReferences, which means both key and value becomes eligible to garbage collection if a key is no longer referenced from elsewhere in the program. |