Posted on: January 18, 2025Posted by: rahulgiteComments: 0
The Java Collections Framework provides a set of classes and interfaces for managing groups of objects. It simplifies data handling by offering various data structures, algorithms, and utilities.
Ordered collection that allows duplicate elements.
Set
Unordered collection that does not allow duplicate elements.
Queue
Ordered collection that supports element processing in FIFO order.
Map
Collection of key-value pairs, where keys are unique.
Details of Each Collection with Examples, Functions, and Use Cases
1. List
Definition: An ordered collection that allows duplicates. Elements are accessible by index.
Functions:
add(E e): Adds an element to the list.
get(int index): Retrieves the element at the specified index.
remove(int index): Removes the element at the specified index.
set(int index, E element): Replaces the element at the specified position.
indexOf(Object o): Returns the index of the first occurrence of the specified element.
contains(Object o): Checks if the list contains the specified element.
Implementations:
ArrayList:
Use Case: Best suited for scenarios where read operations are more frequent than insertions or deletions.
Example:
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
System.out.println(arrayList);
LinkedList:
Use Case: Useful for frequent insertions or deletions as it uses a doubly linked list.
Example:
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.addFirst("B");
System.out.println(linkedList);
ArrayList, LinkedList, and Vector in Java
Java provides several implementations of the List interface, including ArrayList, LinkedList, and Vector. Each of these has unique characteristics and use cases.
Comparison Table
Feature
ArrayList
LinkedList
Vector
Underlying Structure
Dynamic array
Doubly-linked list
Dynamic array
Performance
Fast random access
Fast insertion/deletion
Synchronized (thread-safe)
Thread-Safety
Not thread-safe
Not thread-safe
Thread-safe
Iteration
Faster due to contiguous memory
Slower for random access
Slower due to synchronization
Growth Mechanism
Increases by 50%
N/A
Doubles size
Use Case
Frequent access operations
Frequent insert/delete operations
Thread-safe operations
Details and Examples
1. ArrayList
Description: An ArrayList uses a dynamic array to store elements. It is efficient for accessing elements by index but less so for insertions and deletions.
Example:
import java.util.ArrayList;
public class ArrayListExample {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<>();
list.add("Apple");
list.add("Banana");
list.add("Orange");
System.out.println(list); // Output: [Apple, Banana, Orange]
}
}
2. LinkedList
Description: A LinkedList uses a doubly-linked list internally, making it efficient for insertions and deletions but slower for random access.
Example:
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");
list.add("Orange");
System.out.println(list); // Output: [Apple, Banana, Orange]
}
}
3. Vector
Description: A Vector is similar to an ArrayList but is synchronized, making it thread-safe.
Example:
import java.util.Vector;
public class VectorExample {
public static void main(String[] args) {
Vector<String> vector = new Vector<>();
vector.add("Apple");
vector.add("Banana");
vector.add("Orange");
System.out.println(vector); // Output: [Apple, Banana, Orange]
}
}
Summary
Use ArrayList for scenarios requiring fast random access and where thread safety is not a concern.
Use LinkedList for frequent insertions and deletions.
Use Vector when thread safety is required.
2. Set
Definition: A collection that does not allow duplicate elements. Order depends on the implementation.
Functions:
add(E e): Adds an element to the set if it is not already present.
remove(Object o): Removes the specified element from the set.
contains(Object o): Returns true if the set contains the specified element.
size(): Returns the number of elements in the set.
Implementations:
HashSet:
Use Case: Fast lookups and ensuring uniqueness without caring about order.
Java provides several implementations of the Set interface, including HashSet, LinkedHashSet, and TreeSet. Each of these has distinct characteristics and use cases.
Comparison Table
Feature
HashSet
LinkedHashSet
TreeSet
Ordering
No ordering
Insertion order
Sorted (natural or custom)
Null Elements
Allows one null element
Allows one null element
Does not allow null elements
Performance
Best for frequent lookups
Slightly slower than HashSet
Slower than HashSet
Underlying Structure
Hash table
Hash table + Linked list
Red-Black tree
Duplicates
Not allowed
Not allowed
Not allowed
Iteration Order
Unpredictable
Predictable (insertion order)
Predictable (sorted order)
Use Case
Quick searches
Maintaining insertion order
Maintaining sorted order
Details and Examples
1. HashSet
Description: A HashSet uses a hash table to store elements. It offers constant-time performance for add, remove, and lookup operations.
Example:
import java.util.HashSet;
public class HashSetExample {
public static void main(String[] args) {
HashSet<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Orange");
System.out.println(set); // Output may vary
}
}
2. LinkedHashSet
Description: A LinkedHashSet extends HashSet but maintains a doubly-linked list to preserve the insertion order.
Example:
import java.util.LinkedHashSet;
public class LinkedHashSetExample {
public static void main(String[] args) {
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Orange");
System.out.println(set); // Output: [Apple, Banana, Orange]
}
}
3. TreeSet
Description: A TreeSet stores elements in a sorted order, based on their natural order or a custom comparator.
Example:
import java.util.TreeSet;
public class TreeSetExample {
public static void main(String[] args) {
TreeSet<String> set = new TreeSet<>();
set.add("Banana");
set.add("Apple");
set.add("Orange");
System.out.println(set); // Output: [Apple, Banana, Orange]
}
}
Summary
Use HashSet for quick operations without concern for order.
Use LinkedHashSet when you need to maintain insertion order.
Use TreeSet when sorted order is required.
3. Queue
Definition: Designed for holding elements prior to processing. Typically follows FIFO order.
Functions:
add(E e): Inserts the specified element into the queue.
poll(): Retrieves and removes the head of the queue, or returns null if the queue is empty.
peek(): Retrieves but does not remove the head of the queue, or returns null if the queue is empty.
size(): Returns the number of elements in the queue.
Implementations:
PriorityQueue:
Use Case: Tasks that need to process elements in a priority order.
Java provides several implementations of the Queue interface, including ArrayDeque, LinkedList, and PriorityQueue. Each of these has distinct characteristics and use cases.
Comparison Table
Feature
ArrayDeque
LinkedList
PriorityQueue
Underlying Structure
Resizable array
Doubly-linked list
Heap
Performance
Fast for adding/removing at both ends
Fast for insertion/deletion
Efficient for priority-based access
Ordering
Insertion order
Insertion order
Natural or custom priority
Null Elements
Not allowed
Allowed
Not allowed
Thread-Safety
Not thread-safe
Not thread-safe
Not thread-safe
Use Case
General-purpose deque/stack
General-purpose queue
Priority-based queue
Details and Examples
1. ArrayDeque
Description: An ArrayDeque is implemented using a resizable array. It is fast for adding and removing elements at both ends of the queue.
Example:
import java.util.ArrayDeque;
public class ArrayDequeExample {
public static void main(String[] args) {
ArrayDeque<String> deque = new ArrayDeque<>();
deque.add("Apple");
deque.add("Banana");
deque.add("Orange");
System.out.println(deque); // Output: [Apple, Banana, Orange]
}
}
2. LinkedList
Description: A LinkedList can be used as a Queue or a Deque. It provides fast insertion and deletion but slower access by index.
Example:
import java.util.LinkedList;
public class LinkedListQueueExample {
public static void main(String[] args) {
LinkedList<String> queue = new LinkedList<>();
queue.add("Apple");
queue.add("Banana");
queue.add("Orange");
System.out.println(queue); // Output: [Apple, Banana, Orange]
}
}
3. PriorityQueue
Description: A PriorityQueue orders its elements according to their natural ordering or a custom comparator. It does not allow null elements.
Example:
import java.util.PriorityQueue;
public class PriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(10);
priorityQueue.add(5);
priorityQueue.add(20);
while (!priorityQueue.isEmpty()) {
System.out.println(priorityQueue.poll()); // Output: 5, 10, 20
}
}
}
Summary
Use ArrayDeque for a general-purpose stack or queue implementation when null elements are not needed.
Use LinkedList for scenarios requiring a flexible doubly-linked list implementation.
Use PriorityQueue for priority-based processing of elements.
4. Map
Definition: A collection of key-value pairs where keys are unique.
Functions:
put(K key, V value): Associates the specified value with the specified key.
get(Object key): Returns the value to which the specified key is mapped.
remove(Object key): Removes the mapping for the specified key.
containsKey(Object key): Returns true if the map contains a mapping for the key.
size(): Returns the number of key-value mappings.
keySet(): Returns a set of the keys in the map.
values(): Returns a collection of the values in the map.
Java provides several implementations of the Map interface, including HashMap, LinkedHashMap, and TreeMap. Each of these has unique characteristics and use cases.
Comparison Table
Feature
HashMap
LinkedHashMap
TreeMap
Ordering
No ordering
Insertion order
Sorted (natural or custom)
Null Keys
Allows one null key
Allows one null key
Does not allow null keys
Null Values
Allows multiple null values
Allows multiple null values
Allows multiple null values
Performance
Best for frequent lookups
Slightly slower than HashMap
Slower due to sorting
Underlying Structure
Hash table
Hash table + Linked list
Red-Black tree
Thread-Safety
Not thread-safe
Not thread-safe
Not thread-safe
Use Case
General-purpose key-value
Maintaining insertion order
Maintaining sorted order
Details and Examples
1. HashMap
Description: A HashMap uses a hash table to store key-value pairs. It is efficient for quick lookups and updates but does not guarantee any specific order.
Example:
import java.util.HashMap;
public class HashMapExample {
public static void main(String[] args) {
HashMap<Integer, String> map = new HashMap<>();
map.put(1, "Apple");
map.put(2, "Banana");
map.put(3, "Orange");
System.out.println(map); // Output may vary
}
}
2. LinkedHashMap
Description: A LinkedHashMap extends HashMap but maintains a linked list to preserve the order of insertion.
Example:
import java.util.LinkedHashMap;
public class LinkedHashMapExample {
public static void main(String[] args) {
LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
map.put(1, "Apple");
map.put(2, "Banana");
map.put(3, "Orange");
System.out.println(map); // Output: {1=Apple, 2=Banana, 3=Orange}
}
}
3. TreeMap
Description: A TreeMap stores key-value pairs in sorted order based on the natural ordering of keys or a custom comparator.
Example:
import java.util.TreeMap;
public class TreeMapExample {
public static void main(String[] args) {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "Orange");
map.put(1, "Apple");
map.put(2, "Banana");
System.out.println(map); // Output: {1=Apple, 2=Banana, 3=Orange}
}
}
Summary
Use HashMap for quick key-value storage and retrieval when order is not important.
Use LinkedHashMap when you need to maintain the order of insertion.
Use TreeMap when sorted order of keys is required.
Complexity of Collections
Collection Type
Access
Search
Insertion
Deletion
ArrayList
O(1)
O(n)
O(n)
O(n)
LinkedList
O(n)
O(n)
O(1)
O(1)
HashSet
–
O(1)
O(1)
O(1)
TreeSet
–
O(log n)
O(log n)
O(log n)
HashMap
O(1)
O(1)
O(1)
O(1)
TreeMap
O(log n)
O(log n)
O(log n)
O(log n)
PriorityQueue
O(log n)
O(n)
O(log n)
O(log n)
Differences Between Collection Types
List vs Set
Feature
List
Set
Duplicates
Allowed
Not Allowed
Order
Maintained
Not Guaranteed (except LinkedHashSet)
Performance
Faster for indexed access
Faster for search operations
Set vs Map
Feature
Set
Map
Structure
Collection of unique elements
Key-Value pairs
Duplicates
Not Allowed
Keys: Not Allowed; Values: Allowed
Order
Depends on implementation
Depends on implementation
ArrayList vs LinkedList
Feature
ArrayList
LinkedList
Structure
Dynamic array
Doubly linked list
Access Time
O(1) for index-based access
O(n) for index-based access
Insertion/Deletion
Slow (requires shifting)
Fast (pointers updated)
HashMap vs TreeMap
Feature
HashMap
TreeMap
Order
No order maintained
Sorted order maintained
Performance
O(1) for most operations
O(log n) for all operations
Nulls
One null key allowed
No null keys allowed
1. Why Map Does Not Extend Collection Interface?
Reason: The Map interface is fundamentally different from the Collection interface in terms of structure and purpose.
Map is a key-value pair data structure, whereas Collection is designed to work with single elements.
The operations and behaviors of Map (e.g., put(), get()) are unrelated to those of Collection (e.g., add(), remove()).
If Map extended Collection, many methods in Collection would not make sense for Map.
Example:
add(E e) in Collection is not applicable to Map, as Map uses put(K key, V value) instead.
2. Fail-Fast vs Fail-Safe Iterators
Fail-Fast Iterators:
Fail-fast iterators throw a ConcurrentModificationException if the collection is modified while iterating.
Examples: ArrayList, HashSet, HashMap.
Fail-Safe Iterators:
Fail-safe iterators work on a copy of the collection, so they do not throw exceptions even if the collection is modified.
import java.util.*;
public class FailFastExample {
public static void main(String[] args) {
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
for (String item : list) {
list.add("D"); // Throws ConcurrentModificationException
}
}
}
Example: Fail-Safe Iterator
import java.util.concurrent.*;
public class FailSafeExample {
public static void main(String[] args) {
CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>(Arrays.asList("A", "B", "C"));
for (String item : list) {
list.add("D"); // No exception
}
System.out.println(list);
}
}
3. Blocking Queue
Definition: A BlockingQueue is a thread-safe queue that blocks operations when the queue is full (on addition) or empty (on removal).
Common Implementations:
ArrayBlockingQueue
LinkedBlockingQueue
PriorityBlockingQueue
Methods:
put(E e): Inserts an element, blocking if the queue is full.
take(): Retrieves and removes an element, blocking if the queue is empty.
Example: BlockingQueue
import java.util.concurrent.*;
public class BlockingQueueExample {
public static void main(String[] args) throws InterruptedException {
BlockingQueue<String> queue = new ArrayBlockingQueue<>(2);
// Producer thread
new Thread(() -> {
try {
queue.put("A");
queue.put("B");
System.out.println("Added two elements.");
queue.put("C"); // Blocks until space is available
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
// Consumer thread
new Thread(() -> {
try {
Thread.sleep(1000);
System.out.println("Removed: " + queue.take());
} catch (InterruptedException e) {
Thread.currentThread().interrupt();
}
}).start();
}
}
4. Synchronized vs Concurrent Collections
Synchronized Collections:
Wrapper classes in Collections make a collection synchronized (e.g., Collections.synchronizedList()).
Only one thread can access the collection at a time.
Example: Vector, Hashtable, synchronizedList().
Concurrent Collections:
Designed for high-concurrency scenarios.
Multiple threads can operate on different parts of the collection simultaneously.