Java Collection Cheat Sheet

The Collection interface is the root of the collection hierarchy and defines the most basic operations (like adding and removing) that all collections will have.

Key Features:

• Foundation for other interfaces like Set, List, and Queue.
• Basic operations include adding, removing, clearing, size, and iterator access.

Classes Implementing Collection:

• ArrayList, LinkedList, HashSet, LinkedHashSet, PriorityQueue, etc.

Example & Methods:

import java.util.*;

public class CollectionExample {
    public static void main(String[] args) {
        Collection<String> collection = new ArrayList<>();
        collection.add("Java");
        collection.add("Python");
        System.out.println(collection); // Output: [Java, Python]
    }
}

The List interface extends Collection and allows duplicate elements. Lists can contain elements in a specific sequence.

Characteristics:

• Allows positional access and insertion order is maintained.
• Allows duplicates and null elements.

Classes Implementing List:

• ArrayList and LinkedList.

Example with ArrayList & LinkedList:

List<String> arrayList = new ArrayList<>();
arrayList.add("Java");
arrayList.add("Python");

List<String> linkedList = new LinkedList<>();
linkedList.add("C++");
linkedList.add("JavaScript");

The Set interface extends Collection to handle sets, which must contain unique elements.

Set Properties:

• No duplicate elements.
• Order of elements is not guaranteed (except in LinkedHashSet or TreeSet).

Classes Implementing Set:

• HashSet, LinkedHashSet, and TreeSet.

Example with HashSet:

Set<String> hashSet = new HashSet<>();
hashSet.add("Java");
hashSet.add("Java"); // Duplicate, not added
System.out.println(hashSet); // Output: [Java]

The Queue interface extends Collection and is used for holding elements prior to processing, typically in a FIFO manner.

Queue Operations:

• add, offer (to add elements), remove, poll (to remove elements), element, peek (to examine elements).

Classes Implementing Queue:

• PriorityQueue and LinkedList.

Example with PriorityQueue:

Queue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.add(10);
priorityQueue.add(5);
System.out.println(priorityQueue.peek()); // Output: 5 (smallest element)

The Deque interface extends the Queue interface to support elements insertion and removal from both ends, making it a double-ended queue.

Classes Implementing Deque:

• ArrayDeque and LinkedList.

Example with ArrayDeque:

Deque<String> deque = new ArrayDeque<>();
deque.addFirst("Java");
deque.addLast("Python");
System.out.println(deque); // Output: [Java, Python]

The Map interface maps unique keys to values. A key is an object that you use to retrieve a value at a later date.

Characteristics:

• Contains unique keys.
• Each key maps to at least one value.

Classes Implementing Map:

• HashMap and TreeMap.

Example with HashMap:

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put("Java", 20);
hashMap.put("Python", 25);
System.out.println(hashMap.get("Java")); // Output: 20

An ArrayList in Java is a resizable array implementation of the List interface. It allows for dynamic arrays that can grow as needed. Standard Java arrays are of a fixed length, which means after arrays are created, they cannot grow or shrink. ArrayLists provide a solution to this by maintaining an array internally and resizing it when necessary.

Important Points and Features:

• Dynamic Array: Automatically resizes itself when elements are added or removed.
• Order Preservation: Maintains the insertion order of elements.
• Allow Duplicates and Nulls: Can contain duplicate elements and also allows null values.
• Random Access: Provides constant-time performance for the get and set methods because it uses an array internally.
• Not Synchronized: Means it is not thread-safe unless externally synchronized.

Methods Used:

• add(E e): Adds an element to the end of the list.
• get(int index): Returns the element at the specified position in the list.
• remove(int index): Removes the element at the specified position.
• size(): Returns the number of elements in the list.

Array List In Short

• Resizable array-based implementation of List.
• Fast random access, slow insertions/removals in the middle.
• Not synchronized (useful in single-threaded scenarios).
• Contain duplicate elements and Maintain insertion order.
• Manipulation is a little bit slower than the LinkedList.
• ArrayList cannot be created of the primitive data types.

Program Example:

import java.util.ArrayList;

public class Main {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("Hello");
        list.add("World");
        System.out.println(list.get(0)); // Prints "Hello"
        list.remove(1); // Removes "World"
        System.out.println(list.size()); // Prints 1
    }
}

A LinkedList in Java is a doubly-linked list implementation of the List and Deque interfaces. It allows for constant-time insertions or removals using iterators, but only provides sequential access of elements. In other words, you can traverse the list forwards or backwards, but finding a position takes time proportional to the size of the list.

Important Points and Features:

• Doubly-Linked List: Each element (node) in the list contains links to both the previous and next element.
• Sequential Access: Faster in inserting and deleting in comparison to ArrayList when dealing with large data.
• Implements List and Deque: Can be used as a stack, queue, or double-ended queue.
• Allows Duplicates and Nulls.

Methods Used:

• add(E e): Appends the specified element to the end of this list.
• addFirst(E e): Inserts the specified element at the beginning of this list.
• addLast(E e): Appends the specified element to the end of this list.
• removeFirst(): Removes and returns the first element from this list.
• removeLast(): Removes and returns the last element from this list.

Linked List in Short

• Doubly-linked list implementation of List.
• Efficient for insertions/removals, slower random access.
• Not synchronized.
• Contain duplicate elements and Maintain insertion order.
• Manipulation is fast because no shifting needs to occur.
• Can be used as a list, stack and queue.

Program Example:

import java.util.LinkedList;

public class Main {
    public static void main(String[] args) {
        LinkedList<String> list = new LinkedList<>();
        list.add("Java");
        list.addFirst("Hello");
        list.addLast("World");
        System.out.println(list); // Prints "[Hello, Java, World]"
        list.removeFirst(); // Removes "Hello"
        System.out.println(list); // Prints "[Java, World]"
    }
}

A Vector in Java is similar to an ArrayList, but with two key differences: it is synchronized, and it contains many legacy methods that are not part of the collections framework. Vector implements a dynamic array that can grow or shrink in size as needed.

Important Points and Features:

• Synchronized: Every method is synchronized, which means it is thread-safe.
• Legacy Code: Part of the original version of Java, retained for compatibility reasons.
• Random Access: Like ArrayList, it provides constant-time performance for the get and set methods.
• Slower than ArrayList: Because it’s synchronized, operations on a Vector are slower compared to those on an ArrayList.

Methods Used:

• Similar to ArrayList, with additional legacy methods like addElement(E obj), removeElement(Object obj), and elementAt(int index).

Vector In Short

• Resizable array like ArrayList but synchronized.
• Slower than ArrayList in most cases.
• Less commonly used due to synchronization overhead.

Program Example:

import java.util.Vector;

public class Main {
    public static void main(String[] args) {
        Vector<String> vector = new Vector<>();
        vector.add("Hello");
        vector.addElement("World");
        System.out.println(vector.elementAt(1)); // Prints "World"
        vector.removeElement("Hello"); // Removes "Hello"
        System.out.println(vector.size()); // Prints 1
    }
}

A Stack in Java is a class that implements a last-in-first-out (LIFO) stack of objects. It extends Vector with five operations that allow a vector to be treated as a stack. The class includes methods for the typical stack operations, such as pushing, popping, and peeking.

Important Points and Features:

• LIFO (Last-In-First-Out): The last element added is the first one to be removed.
• Extends Vector: Inherits from Vector, making it synchronized and thus thread-safe.
• Legacy Class: Like Vector, it’s part of the original version of Java. For non-thread-safe or faster stack implementations, consider using ArrayDeque.

Methods Used:

• push(E item): Pushes an item onto the top of the stack.
• pop(): Removes and returns the top item of the stack.
• peek(): Looks at the top item of the stack without removing it.

Program Example:

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        stack.push("Hello");
        stack.push("World");
        System.out.println(stack.peek()); // Prints "World"
        stack.pop(); // Removes "World"
        System.out.println(stack.peek()); // Prints "Hello"
    }
}

A HashSet in Java is an implementation of the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees concerning the order of iteration; in other words, the order in which elements are inserted into the set is not necessarily the order in which they are iterated over. HashSet is designed for fast operations like adding, removing, and checking if an object is present in the collection.

Important Points and Features:

• Unordered Collection: Does not maintain the order of its elements.
• No Duplicates: Ensures that no two elements are identical, as per the equals() method.
• Allows Null Value: Can contain at most one null element.
• Not Synchronized: It’s not thread-safe unless externally synchronized.
• High Performance: Offers constant time performance for basic operations (add, remove, contains, and size), assuming the hash function disperses elements properly among the buckets.

Methods Used:

• add(E e): Adds the specified element to this set if it is not already present.
• remove(Object o): Removes the specified element from this set if it is present.
• contains(Object o): Returns true if this set contains the specified element.
• isEmpty(): Returns true if this set contains no elements.
• size(): Returns the number of elements in this set.

Hashset In short

• Hash table based implementation of Set.
• No duplicate elements.
• Fast insertion and retrieval.
• Not ordered, means not maintain insertion order.
• Use Hashing mechanism to store element.
• Not Synchronized.
• Default capacity of HashSet is 16, and the load factor is 0.75.
• Best option to perform fast search.

Program Example:

import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("Java");
        set.add("Python");
        set.add("Java"); // Duplicate, not added
        System.out.println(set.contains("Python")); // Prints true
        set.remove("Python");
        System.out.println(set.size()); // Prints 1
    }
}

A LinkedHashSet in Java is a hash table and linked list implementation of the Set interface, with predictable iteration order. It inherits from HashSet but also maintains a doubly-linked list across all elements. This linked list defines the iteration ordering, which is normally the order in which elements were inserted into the set (insertion-order).

Important Points and Features:

• Ordered: Maintains elements in insertion order.
• No Duplicates: Like HashSet, it does not allow duplicate elements.
• Allows Null Value: Can include at most one null element.
• Not Synchronized: Not thread-safe unless externally synchronized.
• Slightly Lower Performance than HashSet: Due to the added expense of maintaining the linked list, the performance is slightly lower than that of a HashSet.

Methods Used:

• Uses the same methods as HashSet, with the iteration order guaranteed to be in the order in which the elements were inserted.

Program Example:

import java.util.LinkedHashSet;

public class Main {
    public static void main(String[] args) {
        LinkedHashSet<String> set = new LinkedHashSet<>();
        set.add("Java");
        set.add("Python");
        set.add("C++");
        set.forEach(System.out::println); // Iterates in insertion order
    }
}

A TreeSet in Java is a NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time. This implementation provides guaranteed log(n) time cost for the basic operations (add, remove, and contains).

Important Points and Features:

• Ordered and Sorted: Elements are sorted according to their natural ordering or by a specified comparator.
• No Duplicates: Cannot contain duplicate elements.
• No Null Values: If natural ordering is used, TreeSet does not permit null elements. If using a comparator, nulls are permitted only if the comparator can handle them.
• Not Synchronized: It is not thread-safe unless externally synchronized.
• NavigableSet Interface: Provides methods for returning specific subsets of the set and for navigation purposes.

Methods Used:

• add(E e): Adds the specified element to this set if it is not already present.
• first(): Returns the first (lowest) element currently in this set.
• last(): Returns the last (highest) element currently in this set.
• headSet(E toElement): Returns a view of the portion of this set whose elements are strictly less than toElement.
• tailSet(E fromElement): Returns a view of the portion of this set whose elements are greater than or equal to fromElement.

Treeset In Short

• Sorted set using Red-Black tree in ascending order.
• Elements are ordered (natural order or custom Comparator).
• It doesn’t allow null element.
• Not Synchronized.
• No Duplicates Allow

Program Example:

import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<String> set = new TreeSet<>();
        set.add("Python");
        set.add("Java");
        set.add("C++");
        System.out.println("First: " + set.first()); // Prints "C++"
        System.out.println("Last: " + set.last()); // Prints "Python"
        set.forEach(System.out::println); // Iterates in natural order
    }
}

A PriorityQueue in Java is a queue data structure implementation in which elements are ordered according to their natural ordering, or by a Comparator provided at queue construction time. Elements of the priority queue are ordered either according to their natural ordering, or according to a Comparator provided at the queue construction time, depending on which constructor is used. A priority queue does not permit null elements.

Important Points and Features:

• Ordering: Elements are ordered either by their natural ordering (i.e., according to the Comparable interface) or according to a Comparator.
• Head of the Queue: The head of the queue is the least element with respect to the specified ordering. If multiple elements are tied for least value, the head is one of those elements — ties are broken arbitrarily.
• Polling Order: The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
• Not Thread-Safe: PriorityQueue is not thread-safe. Multiple threads should not access a PriorityQueue instance concurrently if any of the threads modifies the queue.
• Performance: The time complexity for the insertion and removal methods (offer, poll, remove(), and add) is O(log(n)).

Methods Used:

• offer(E e): Inserts the specified element into this priority queue.
• poll(): Retrieves and removes the head of this queue, or returns null if this queue is empty.
• peek(): Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
• size(): Returns the number of elements in this collection.

Program Example:

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(10);
        pq.offer(20);
        pq.offer(15);

        System.out.println(pq.peek()); // Prints the head of the queue, i.e., 10
        System.out.println(pq.poll()); // Removes and returns the head, i.e., 10
        System.out.println(pq.peek()); // Now the head is 15
    }
}

An ArrayDeque is a resizable array implementation of the Deque interface. It has no capacity restrictions and it provides a way to insert, remove, and examine elements from both ends of the deque. ArrayDeque can be used as a stack (LIFO) or a queue (FIFO).

Important Points and Features:

• Resizable Array: Can grow as needed to support usage.
• Null Elements: Does not allow the insertion of null elements.
• Faster than Stack and LinkedList: It is generally faster than Stack when used as a stack, and faster than LinkedList when used as a queue.
• Not Thread-Safe: Like PriorityQueue, it is not thread-safe.
• Iteration Order: Elements are ordered by their insertion order, which is the order in which iterators return elements.

Methods Used:

• addFirst(E e): Inserts the specified element at the front of this deque.
• addLast(E e): Inserts the specified element at the end of this deque.
• pollFirst(): Retrieves and removes the first element of this deque, or returns null if this deque is empty.
• pollLast(): Retrieves and removes the last element of this deque, or returns null if this deque is empty.
• peekFirst(): Retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty.
• peekLast(): Retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty.

Program Example:

import java.util.ArrayDeque;

public class Main {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        deque.addFirst("First");
        deque.addLast("Last");

        System.out.println(deque.peekFirst()); // Prints "First"
        System.out.println(deque.pollLast()); // Removes and prints "Last"
        System.out.println(deque.peekFirst()); // Now only "First" is left
    }
}

A HashMap in Java is part of the Java Collections Framework and implements the Map interface, providing key-value storage. It allows for the retrieval of stored values based on their key. HashMap is known for its efficiency in performing basic operations like adding, removing, and locating elements.

Important Points and Features:

• Key-Value Pairs: Stores elements as key-value pairs.
• Ordering: Does not guarantee any specific order of the entries in the map.
• Null Values: Allows one null key and multiple null values.
• Not Synchronized: It is not thread-safe without external synchronization.
• Performance: Offers constant-time performance for get and put methods under the ideal hashing distribution.

Methods Used:

• put(K key, V value): Adds a key-value pair to the map.
• get(Object key): Retrieves the value associated with the specified key.
• remove(Object key): Removes the entry for the specified key.
• containsKey(Object key): Checks if the map contains the specified key.

HashMap In Short

• Hash table-based implementation of Map.
• Key-value pairs with unique keys.
• Fast insertion and retrieval.
• Not ordered.
• Not Synchronized.
• Not maintain the insertion order.
• Default capacity of Java HashMap class is 16 with a load factor of 0.75.

Program Example:

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        HashMap<Integer, String> map = new HashMap<>();
        map.put(1, "Java");
        map.put(2, "Python");
        map.put(3, "C++");

        System.out.println(map.get(1)); // Prints "Java"
        map.remove(2);
        System.out.println(map.containsKey(2)); // Prints false
    }
}

A LinkedHashMap is an extension of HashMap that maintains a linked list of the entries in the map, in the order in which they were inserted. This allows for iteration over the map’s entries in their insertion order or in the order in which they were last accessed, depending on the constructor used.

Important Points and Features:

• Order Maintenance: Maintains a doubly-linked list running through all its entries.
• Access-Order or Insertion-Order: The iteration order can be the order in which keys were inserted, or the order in which keys were last accessed.
• Performance: Slightly lower performance than HashMap due to the added expense of maintaining the linked list.

Methods Used:

• Inherits methods from HashMap, with behavior modified to maintain order.

LinkedHashMap In Short

• Hash table-based implementation of Map with predictable order.
• Maintain the insertion order.
• Slower than HashMap but maintains order.
• Have one null key and multiple null values.
• Not synchronized.
• Default capacity of Java HashMap class is 16 with a load factor of 0.75.

Program Example:

import java.util.LinkedHashMap;

public class Main {
    public static void main(String[] args) {
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1, "Java");
        map.put(2, "Python");
        map.put(3, "C++");

        map.forEach((key, value) -> System.out.println(key + ": " + value));
        // Iterates in insertion order
    }
}

A TreeMap is a map implementation that is based on a red-black tree. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time.

Important Points and Features:

• Sorted Map: The keys are ordered using their natural ordering, or by a comparator.
• Null Keys: Cannot contain null keys if using natural ordering, but can contain multiple null values.
• Performance: Provides guaranteed log(n) time cost for the containsKey, get, put, and remove operations.
• NavigableMap Interface: Offers methods that allow for the navigation of the map.

Methods Used:

• put(K key, V value): Adds a key-value pair to the map.
• get(Object key): Retrieves the value associated with the specified key.
• firstKey(): Returns the first (lowest) key currently in the map.
• lastKey(): Returns the last (highest) key currently in the map.

TreeMap In Short

• Sorted map using Red-Black tree.
• Keys are ordered (natural order or custom Comparator).
• Slower insertion/removal compared to HashMap.
• Implements the NavigableMap interface and extends AbstractMap class.
• Contains only unique elements.
• TreeMap maintains ascending order.
• TreeMap is non synchronized.

Program Example:

import java.util.TreeMap;

public class Main {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(3, "C++");
        map.put(1, "Java");
        map.put(2, "Python");

        System.out.println("First Key: " + map.firstKey()); // Prints 1
        System.out.println("Last Key: " + map.lastKey()); // Prints 3
        // Iterates in natural order of keys
        map.forEach((key, value) -> System.out.println(key + ": " + value));
    }
}

Note: legacy, not part of the Collections Framework but often used alongside it

Hashtable is a legacy data structure that is similar to HashMap but with a few differences. It is synchronized, meaning it is thread-safe. Unlike HashMap, it does not allow null keys or null values. It is part of the original version of Java but has been superseded in most cases by the ConcurrentHashMap for thread-safe implementations.

Important Points and Features:

• Synchronized: Every method call is synchronized, making it thread-safe.
• No Null Keys or Values: Does not permit nulls for either keys or values.
• Performance: Because it is synchronized, it may have lower performance than HashMap in scenarios where high concurrency is not required.
• Legacy: Considered legacy code; ConcurrentHashMap or Collections.synchronizedMap are usually better options for thread-safe maps.

Methods Used:

• Similar to HashMap, with methods like put, get, remove, and containsKey.

Program Example:

import java.util.Hashtable;

public class Main {
    public static void main(String[] args) {
        Hashtable<Integer, String> table = new Hashtable<>();
        table.put(1, "Java");
        table.put(2, "Python");
        table.put(3, "C++");

        System.out.println(table.get(2)); // Prints "Python"
        table.remove(3);
        System.out.println(table.contains("Java")); // Prints true
    }
}

These map implementations offer a range of behaviors and performance characteristics, making them suitable for different scenarios. HashMap and LinkedHashMap offer fast access and insertion, with LinkedHashMap also maintaining insertion order. TreeMap provides sorted order and Hashtable offers thread-safe operations, though at a potential performance cost compared to non-synchronized structures.

CopyOnWriteArrayList is a thread-safe variant of ArrayList in which all mutative operations (add, set, remove, etc.) are implemented by making a fresh copy of the underlying array. This ensures that no concurrency issues arise when the list is accessed by multiple threads, even during iteration.

Important Points and Features:

• Thread-Safe Iteration: Iterators of CopyOnWriteArrayList do not throw ConcurrentModificationException, making it safe for concurrent iteration.
• Memory Overhead: Due to its copy-on-write nature, it can be memory intensive for lists that are frequently modified.
• Best Use Case: Ideal for scenarios where the list is mostly read-only operations but still requires thread-safe writes.

Methods Used:

• add(E e): Adds an element to the end of the list.
• set(int index, E element): Replaces the element at the specified position.
• remove(Object o): Removes the first occurrence of the specified element.

Program Example:

import java.util.concurrent.CopyOnWriteArrayList;

public class Main {
    public static void main(String[] args) {
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
        list.add("Java");
        list.add("Python");
        
        for (String language : list) {
            System.out.println(language);
        }
        // Outputs:
        // Java
        // Python
    }
}

CopyOnWriteArraySet is a thread-safe variant of Set backed by a CopyOnWriteArrayList. Like its list counterpart, all mutative operations are implemented by making a fresh copy of the underlying array.

Important Points and Features:

• Write Performance: Mutative operations (add, remove, etc.) are slow because they involve copying the entire underlying array.
• Iterator Safety: Iterators do not support the mutative remove operation and do not throw ConcurrentModificationException.
• Memory Cost: Can be memory intensive if the set is subject to frequent modifications.

Methods Used:

• add(E e): Adds the specified element to the set if it is not already present.
• remove(Object o): Removes the specified element from this set if it is present.

Program Example:

import java.util.concurrent.CopyOnWriteArraySet;

public class Main {
    public static void main(String[] args) {
        CopyOnWriteArraySet<String> set = new CopyOnWriteArraySet<>();
        set.add("Java");
        set.add("Python");
        
        for (String language : set) {
            System.out.println(language);
        }
        // Outputs:
        // Java
        // Python (order is not guaranteed)
    }
}

ConcurrentLinkedQueue is a thread-safe, unbounded FIFO (first in, first out) queue based on linked nodes. It supports an efficient lock-free algorithm for concurrent appenders and removers.

Important Points and Features:

• High Concurrency: Offers high throughput under concurrent access.
• Scalability: Performs well in scalable applications with high concurrency.
• Iterator Weak Consistency: Iterators are weakly consistent and reflect the state of the queue at some point at or since the creation of the iterator.

Methods Used:

• offer(E e): Inserts the specified element into this queue.
• poll(): Retrieves and removes the head of this queue, or returns null if this queue is empty.
• peek(): Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

Program Example:

import java.util.concurrent.ConcurrentLinkedQueue;

public class Main {
    public static void main(String[] args) {
        ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();
        queue.offer("Java");
        queue.offer("Python");
        
        System.out.println(queue.poll()); // Outputs: Java
        System.out.println(queue.peek()); // Outputs: Python
    }
}

ConcurrentLinkedDeque is a thread-safe, unbounded deque (double-ended queue) based on linked nodes. It allows concurrent insertion, removal, and access operations at both ends.

Important Points and Features:

• Concurrent Double-Ended Operations: Supports insertion, removal, and access at both ends, allowing it to be used as a stack or queue.
• Scalability and Concurrency: Designed for high throughput in concurrent scenarios.
• Iterator Weak Consistency: Iterators are weakly consistent.

Methods Used:

• offerFirst(E e) and offerLast(E e): Inserts the specified element at the beginning and the end of the deque, respectively.
• pollFirst() and pollLast(): Retrieves and removes the first and last elements of the deque, respectively.
• peekFirst() and peekLast(): Retrieves, but does not remove, the first and last elements of the deque, respectively.

Program Example:

import java.util.concurrent.ConcurrentLinkedDeque;

public class Main {
    public static void main(String[] args) {
        ConcurrentLinkedDeque<String> deque = new ConcurrentLinkedDeque<>();
        deque.offerFirst("Java");
        deque.offerLast("Python");
        
        System.out.println(deque.pollFirst()); // Outputs: Java
        System.out.println(deque.peekLast()); // Outputs: Python
    }
}

A BlockingQueue is an interface in the Java Concurrent package (java.util.concurrent) that represents a queue which supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available in the queue when storing an element. It is primarily used in producer-consumer scenarios where you have threads producing elements to the queue and consumer threads taking elements from the queue.

Important Points and Features:

• Thread-Safe: Designed to be used in concurrent scenarios without external synchronization.
• Blocking Operations: Includes methods that wait for the queue to become non-empty when retrieving an element and wait for space to become available when storing an element.
• Several Implementations: Including ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue, DelayQueue, and SynchronousQueue.

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

BlockingQueue<String> queue = new ArrayBlockingQueue<>(3);
queue.put("Java");
queue.put("Python");
System.out.println(queue.take()); // Outputs "Java"

import java.util.concurrent.LinkedBlockingQueue;
import java.util.concurrent.BlockingQueue;

BlockingQueue<String> queue = new LinkedBlockingQueue<>();
queue.put("C++");
queue.put("JavaScript");
System.out.println(queue.take()); // Outputs "C++"

import java.util.concurrent.PriorityBlockingQueue;

PriorityBlockingQueue<Integer> queue = new PriorityBlockingQueue<>();
queue.put(10);
queue.put(1);
System.out.println(queue.take()); // Outputs "1" since it has higher priority (lower value)

import java.util.concurrent.DelayQueue;
import java.util.concurrent.Delayed;
import java.util.concurrent.TimeUnit;

DelayQueue<DelayedElement> queue = new DelayQueue<>();
queue.put(new DelayedElement("Task", 1000)); // Delay of 1 second
System.out.println(queue.take().getElement()); // Waits at least 1 second before printing "Task"

import java.util.concurrent.SynchronousQueue;
import java.util.concurrent.BlockingQueue;

BlockingQueue<String> queue = new SynchronousQueue<>();

Thread producer = new Thread(() -> {
    try {
        queue.put("Hello, World!");
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
});

Thread consumer = new Thread(() -> {
    try {
        System.out.println(queue.take());
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
});

producer.start();
consumer.start();

A BlockingDeque is an interface in the Java Concurrent package (java.util.concurrent) that represents a double-ended queue which supports blocking retrieval operations. This means that threads can insert elements at both ends of the queue and can also block while waiting to take elements from the queue. A BlockingDeque is particularly useful in scenarios where you need more flexibility than a standard BlockingQueue, as it allows for LIFO (Last-In-First-Out) operations like a stack, as well as FIFO (First-In-First-Out) operations like a queue.

Important Points and Features:

• Thread-Safe: Provides a thread-safe way to access and modify the deque.
• Blocking Operations: Methods are available to wait for the deque to become non-empty when retrieving an element, and to wait for space to become available in the deque when storing an element.
• Two-Ended Access: Allows insertion and removal of elements from both ends of the deque.

import java.util.concurrent.BlockingDeque;
import java.util.concurrent.LinkedBlockingDeque;
import java.util.concurrent.TimeUnit;

public class Main {
    public static void main(String[] args) throws InterruptedException {
        BlockingDeque<String> deque = new LinkedBlockingDeque<>();

        deque.putFirst("1 - Java");
        deque.putLast("2 - Python");

        System.out.println(deque.takeFirst()); // Outputs "1 - Java"
        System.out.println(deque.takeLast()); // Outputs "2 - Python"

        // Demonstrating timed offer and poll operations
        boolean offered = deque.offerLast("3 - C++", 2, TimeUnit.SECONDS);
        if (offered) {
            String retrieved = deque.pollFirst(2, TimeUnit.SECONDS);
            System.out.println(retrieved); // Outputs "3 - C++"
        }
    }
}

The ConcurrentMap interface in Java represents a key-value mapping that supports thread-safe concurrent access and modifications. It extends the Map interface and defines atomic operations that are safe to use by multiple threads without external synchronization.

Important Points and Features:

• Atomic Operations: Provides methods for atomic operations such as putIfAbsent, remove, and replace, which help prevent common mistakes when a map is accessed by multiple threads.
• Thread Safety: Designed to handle concurrent access and modifications efficiently.
• Memory Consistency: Ensures that changes in the map’s contents are visible across all threads in a consistent manner.

Methods Used:

• putIfAbsent(K key, V value): If the specified key is not already associated with a value, associate it with the given value.
• remove(Object key, Object value): Removes the entry for a key only if it is currently mapped to a given value.
• replace(K key, V oldValue, V newValue): Replaces the entry for a key only if currently mapped to a specified value.
• replace(K key, V value): Replaces the entry for a key only if it is currently mapped to some value.

import java.util.concurrent.ConcurrentHashMap;

public class Main {
    public static void main(String[] args) {
        ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
        map.put("key1", "value1");
        map.put("key2", "value2");

        map.computeIfAbsent("key3", key -> "value3");
        map.computeIfPresent("key2", (key, value) -> value + " modified");

        System.out.println(map); // Output: {key1=value1, key2=value2 modified, key3=value3}
    }
}

• List: Use a List (ArrayList, LinkedList) when you need ordered collection that can contain duplicates. Lists are ideal for scenarios where elements are accessed sequentially or indexed.
• Set: Opt for a Set (HashSet, TreeSet) when you need to store unique elements. Sets are beneficial when the primary operation is to check for the presence of items.
• Map: A Map (HashMap, TreeMap) is key-value pairs storage. It’s useful when you need to retrieve values based on a key. Maps excel in lookups and are essential for associating pairs of elements.

• ArrayList vs. LinkedList: ArrayList provides faster access times for indexed elements but can be slower at inserting and removing elements, especially in the middle of the list. LinkedList, on the other hand, offers quicker insertions and deletions but slower random access times.
• HashSet vs. TreeSet: HashSet offers constant-time performance for basic operations, assuming the hash function disperses elements properly. TreeSet provides guaranteed log(n) time cost for the same operations but maintains elements in a sorted order, which is beneficial for ordered traversal or range searches.
• HashMap vs. TreeMap: HashMap is generally faster for insertions and retrievals as it provides constant-time performance. However, it doesn’t guarantee any order. TreeMap keeps its keys in sorted order, which is useful for range searches and ordered iteration, but operations have log(n) time complexity.

The Iterator interface provides a way to access elements of a collection sequentially and includes methods for checking the next element (hasNext), retrieving the next element (next), and removing the current element (remove). It’s widely used due to its simplicity and the ability to modify the collection during iteration by removing elements.

Example with a List

List<String> languages = new ArrayList<>(Arrays.asList("Java", "Python", "C++"));
Iterator<String> iterator = languages.iterator();
while (iterator.hasNext()) {
    String language = iterator.next();
    if (language.equals("Python")) {
        iterator.remove(); // Remove element safely during iteration
    }
}
System.out.println(languages); // Output: [Java, C++]

The ListIterator is specific to lists and extends Iterator with more functionality, including bidirectional traversal (hasPrevious, previous), obtaining the index of the next or previous element (nextIndex, previousIndex), and modifying the list during iteration (set, add).

Example with a List

List<String> languages = new ArrayList<>(Arrays.asList("Java", "Python", "C++"));
ListIterator<String> listIterator = languages.listIterator();
while (listIterator.hasNext()) {
    String language = listIterator.next();
    if (language.equals("Python")) {
        listIterator.set("JavaScript"); // Replace element
    }
}
System.out.println(languages); // Output: [Java, JavaScript, C++]

The for-each loop, introduced in Java 5, is the simplest way to iterate over the elements of any Collection or array. It hides the iterator usage but does not allow removing or modifying elements during iteration.

Example with a Set

Set<String> languages = new HashSet<>(Arrays.asList("Java", "Python", "C++"));
for (String language : languages) {
    System.out.println(language);
    // Attempting to modify the set here would cause a ConcurrentModificationException
}

Maps require a slightly different approach since they store key-value pairs. You can iterate over the key set, the entry set (key-value pairs), or the values collection.

Example iterating over a Map’s entry set

Map<String, Integer> languageRanks = new HashMap<>();
languageRanks.put("Java", 1);
languageRanks.put("Python", 2);
languageRanks.put("C++", 3);

for (Map.Entry<String, Integer> entry : languageRanks.entrySet()) {
    System.out.println(entry.getKey() + " rank: " + entry.getValue());
}

Method: Collections.sort(List<T> list) or Collections.sort(List<T> list, Comparator<? super T> c)

Internal Algorithm: Java’s Collections Framework uses a modified version of TimSort, which is a hybrid sorting algorithm derived from merge sort and insertion sort. For small arrays, it performs an insertion sort, but for larger datasets, it breaks the dataset into smaller pieces to sort them individually (like merge sort) and then merges the sorted pieces together. This approach is highly efficient for partially sorted arrays and ensures stable sorting with a time complexity of O(n log n) in the worst case.

Example:

List<String> fruits = Arrays.asList("Orange", "Apple", "Banana", "Kiwi");
Collections.sort(fruits);
System.out.println("Sorted: " + fruits);

Method: Collections.shuffle(List<?> list) or Collections.shuffle(List<?> list, Random rnd)

Internal Algorithm:

The Collections.shuffle() method randomly permutes the specified list using a default source of randomness. Internally, it employs the Fisher-Yates shuffle algorithm, also known as the Knuth shuffle. This algorithm runs in linear time, ensuring that each permutation is equally likely.

Example:

Collections.shuffle(fruits);
System.out.println("Shuffled: " + fruits);

Method: Collections.reverse(List<?> list)

Internal Algorithm: The Collections.reverse() method reverses the order of elements in a list. This method is straightforward; it swaps elements from one end of the list with those from the other end, moving towards the center of the list, which results in the list being reversed. The operation is performed in linear time complexity, O(n), where n is the number of elements in the list.

Example:

Collections.reverse(fruits);
System.out.println("Reversed: " + fruits);

Methods: Collections.max(Collection<? extends T> coll) and Collections.min(Collection<? extends T> coll) or their versions with a Comparator

Internal Algorithm:

The Collections.max() and Collections.min() methods find the maximum and minimum elements in a collection, respectively. By default, these methods compare elements using their natural ordering, but a custom Comparator can also be provided. Internally, both methods iterate through the collection linearly, comparing each element with the current maximum or minimum to find the overall maximum or minimum. The time complexity of these methods is O(n).

Example:

String maxFruit = Collections.max(fruits);
String minFruit = Collections.min(fruits);
System.out.println("Max: " + maxFruit + ", Min: " + minFruit);