Java, Collections

Harsh Mishra - Jun 29 - - Dev Community

Collections in Java

In Java, the term "Collections" refers to a framework that provides an architecture to store and manipulate groups of objects. Unlike arrays, which have a fixed size, collections in Java can dynamically grow and shrink as elements are added or removed. The Java Collections Framework (JCF) includes interfaces, implementations, and algorithms that allow developers to work with collections efficiently.

Key Interfaces

  1. Collection<E>: Represents a group of objects known as elements. It is the root interface in the collection hierarchy.

  2. List<E>: Represents an ordered collection (sequence) of elements where each element has an index. Duplicates are allowed.

  3. Set<E>: Represents a collection that cannot contain duplicate elements. It ensures no two elements are equal.

  4. Map<K, V>: Represents a mapping between keys and values. Each key is unique, and each key maps to one value.

  5. Queue<E>: Represents a collection designed for holding elements before processing. It typically follows a FIFO (First-In-First-Out) order.

  6. Deque<E>: Represents a linear collection that supports element insertion and removal at both ends. It stands for "double-ended queue."

Key Implementations

  1. ArrayList<E>: Implements List<E> and uses a dynamic array to store elements. It allows fast random access and is resizable.

  2. LinkedList<E>: Implements List<E> and Deque<E>. It uses a doubly-linked list internally, providing efficient insertion and deletion.

  3. HashSet<E>: Implements Set<E> and uses a hash table for storage. It does not guarantee the order of elements.

  4. TreeSet<E>: Implements Set<E> and stores elements in a sorted tree structure (red-black tree). It maintains elements in sorted order.

  5. HashMap<K, V>: Implements Map<K, V> and uses a hash table for storage. It provides quick retrieval and insertion of key-value pairs.

  6. TreeMap<K, V>: Implements Map<K, V> and stores key-value pairs in a sorted tree structure (red-black tree). It maintains keys in sorted order.

Utility Classes

  1. Collections: Provides static methods for operations on collections such as sorting, searching, and synchronizing.

  2. Arrays: Provides static methods for manipulating arrays (e.g., sorting, searching) and converting arrays to collections and vice versa.

Collection Interface in Java

The Collection interface in Java serves as the root interface for all collections in the Java Collections Framework (JCF). It defines the basic operations that all concrete collection classes must support, facilitating uniformity and interoperability among different collection types.

Overview

The Collection interface represents a group of objects known as elements. It provides methods to add, remove, query, and manipulate elements within the collection. Collections can vary in their behavior (e.g., allowing duplicates or not) depending on the specific implementation of the interface.

Key Methods

  1. boolean add(E element):

    • Adds the specified element to the collection if it is not already present.
    • Returns true if the collection changes as a result of the call (i.e., if the element was added).
  2. boolean remove(Object object):

    • Removes a single instance of the specified element from the collection, if it is present.
    • Returns true if the collection contained the specified element.
  3. boolean contains(Object object):

    • Returns true if the collection contains the specified element.
  4. int size():

    • Returns the number of elements in the collection.
  5. boolean isEmpty():

    • Returns true if the collection contains no elements.
  6. void clear():

    • Removes all elements from the collection.
  7. Iterator<E> iterator():

    • Returns an iterator over the elements in the collection.
  8. Object[] toArray():

    • Returns an array containing all the elements in the collection.

List Interface in Java

The List interface in Java extends the Collection interface and represents an ordered collection of elements where each element has an index. Unlike sets, lists typically allow duplicate elements. The Java Collections Framework (JCF) provides several implementations of the List interface, each with unique characteristics suited for different use cases.

Overview

The List interface maintains elements in a sequential order and allows positional access to elements using index-based methods. It provides operations for adding, removing, querying, and manipulating elements within the list. Implementations of List differ in their underlying data structures, which impact their performance characteristics.

Key Methods

  1. void add(int index, E element):

    • Inserts the specified element at the specified position in the list.
    • Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
  2. E get(int index):

    • Returns the element at the specified position in the list.
  3. E set(int index, E element):

    • Replaces the element at the specified position in the list with the specified element.
  4. boolean remove(Object object):

    • Removes the first occurrence of the specified element from the list, if it is present.
  5. int indexOf(Object object):

    • Returns the index of the first occurrence of the specified element in the list, or -1 if the element is not found.
  6. int lastIndexOf(Object object):

    • Returns the index of the last occurrence of the specified element in the list, or -1 if the element is not found.
  7. List<E> subList(int fromIndex, int toIndex):

    • Returns a view of the portion of the list between the specified fromIndex (inclusive) and toIndex (exclusive).
  8. void sort(Comparator<? super E> c):

    • Sorts the elements of the list according to the order induced by the specified comparator.

Common Implementations

  1. ArrayList<E>:

    • Implements List using a dynamic array.
    • Provides fast random access and efficient element insertion/deletion at the end of the list.
    • Resizes dynamically as elements are added or removed.
  2. LinkedList<E>:

    • Implements List using a doubly linked list.
    • Provides efficient element insertion/deletion at both ends of the list.
    • Supports sequential access to elements.

ArrayList in Java

ArrayList in Java is a part of the Java Collections Framework and implements the List interface. It provides a resizable array-based implementation of the List interface, allowing dynamic resizing of the underlying array as elements are added or removed. ArrayList is widely used due to its flexibility, efficiency in accessing elements by index, and support for dynamic data storage.

Overview

  • Dynamic Array: Internally uses a dynamic array to store elements.
  • Indexed Access: Supports fast random access to elements using index-based operations.
  • Resizable: Automatically grows as elements are added, reallocating the internal array when its capacity is exceeded.

Creation

  1. Default Constructor: Constructs an empty list with an initial capacity of 10.
   ArrayList<String> list = new ArrayList<>();
Enter fullscreen mode Exit fullscreen mode
  1. Specified Capacity: Constructs an empty list with the specified initial capacity.
   ArrayList<Integer> numbers = new ArrayList<>(20);
Enter fullscreen mode Exit fullscreen mode
  1. Initialization from Collection: Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
   Set<String> set = new HashSet<>();
   // add elements to set
   ArrayList<String> list = new ArrayList<>(set);
Enter fullscreen mode Exit fullscreen mode

Key Methods

  1. add(E element):
    • Appends the specified element to the end of the list.
   list.add("apple");
Enter fullscreen mode Exit fullscreen mode
  1. add(int index, E element):
    • Inserts the specified element at the specified position in the list.
    • Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
   list.add(1, "banana");
Enter fullscreen mode Exit fullscreen mode
  1. get(int index):
    • Returns the element at the specified position in the list.
   String fruit = list.get(0);
Enter fullscreen mode Exit fullscreen mode
  1. set(int index, E element):
    • Replaces the element at the specified position in the list with the specified element.
   list.set(0, "orange");
Enter fullscreen mode Exit fullscreen mode
  1. remove(Object object):
    • Removes the first occurrence of the specified element from the list, if it is present.
   list.remove("apple");
Enter fullscreen mode Exit fullscreen mode
  1. size():
    • Returns the number of elements in the list.
   int size = list.size();
Enter fullscreen mode Exit fullscreen mode
  1. isEmpty():
    • Returns true if the list contains no elements.
   boolean empty = list.isEmpty();
Enter fullscreen mode Exit fullscreen mode
  1. clear():
    • Removes all elements from the list.
   list.clear();
Enter fullscreen mode Exit fullscreen mode
  1. contains(Object object):
    • Returns true if the list contains the specified element.
   boolean contains = list.contains("banana");
Enter fullscreen mode Exit fullscreen mode
  1. indexOf(Object object):

    • Returns the index of the first occurrence of the specified element in the list, or -1 if the element is not found.
    int index = list.indexOf("banana");
    
  2. toArray():

    • Returns an array containing all of the elements in the list.
    Object[] array = list.toArray();
    

LinkedList in Java [List Interface]

LinkedList in Java is an implementation of the List interface that uses a doubly linked list to store elements. Unlike ArrayList, which uses a dynamic array, LinkedList provides efficient insertion and deletion operations at both ends of the list. It also supports sequential access and is particularly useful when frequent insertion and deletion operations are required.

Overview

  • Doubly Linked List: Uses a doubly linked list structure where each element is stored in a node containing references to the next and previous elements.
  • Flexible Size: Grows dynamically as elements are added and shrinks when elements are removed.
  • Efficient Insertions and Deletions: Provides O(1) time complexity for adding or removing elements at the beginning or end of the list.

Creation

  1. Default Constructor: Constructs an empty list.
   LinkedList<String> list = new LinkedList<>();
Enter fullscreen mode Exit fullscreen mode
  1. Initialization from Collection: Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
   Set<Integer> set = new HashSet<>();
   // add elements to set
   LinkedList<Integer> list = new LinkedList<>(set);
Enter fullscreen mode Exit fullscreen mode

Key Methods

  1. add(E element):
    • Appends the specified element to the end of the list.
   list.add("apple");
Enter fullscreen mode Exit fullscreen mode
  1. add(int index, E element):
    • Inserts the specified element at the specified position in the list.
   list.add(1, "banana");
Enter fullscreen mode Exit fullscreen mode
  1. get(int index):
    • Returns the element at the specified position in the list.
   String fruit = list.get(0);
Enter fullscreen mode Exit fullscreen mode
  1. set(int index, E element):
    • Replaces the element at the specified position in the list with the specified element.
   list.set(0, "orange");
Enter fullscreen mode Exit fullscreen mode
  1. remove(Object object):
    • Removes the first occurrence of the specified element from the list, if it is present.
   list.remove("apple");
Enter fullscreen mode Exit fullscreen mode
  1. size():
    • Returns the number of elements in the list.
   int size = list.size();
Enter fullscreen mode Exit fullscreen mode
  1. isEmpty():
    • Returns true if the list contains no elements.
   boolean empty = list.isEmpty();
Enter fullscreen mode Exit fullscreen mode
  1. clear():
    • Removes all elements from the list.
   list.clear();
Enter fullscreen mode Exit fullscreen mode
  1. contains(Object object):
    • Returns true if the list contains the specified element.
   boolean contains = list.contains("banana");
Enter fullscreen mode Exit fullscreen mode
  1. indexOf(Object object):

    • Returns the index of the first occurrence of the specified element in the list, or -1 if the element is not found.
    int index = list.indexOf("banana");
    
  2. toArray():

    • Returns an array containing all of the elements in the list.
    Object[] array = list.toArray();
    

Queue Interface in Java

The Queue interface in Java represents a collection designed for holding elements before processing, following the FIFO (First-In-First-Out) principle. It extends the Collection interface and provides methods for adding, removing, and inspecting elements in a specific order. Queues are commonly used for tasks such as task scheduling, messaging, and breadth-first search algorithms.

Overview

  • FIFO Order: Elements are added to the end of the queue and removed from the beginning, maintaining their insertion order.
  • Implementations: Java provides several implementations of the Queue interface, each with different characteristics suited for specific use cases.
  • Additional Methods: Includes methods inherited from the Collection interface for basic operations and adds specialized methods for queue-specific operations.

Common Methods

  1. boolean add(E element):

    • Inserts the specified element into the queue if possible.
    • Throws an exception if the element cannot be added (e.g., capacity restrictions).
  2. boolean offer(E element):

    • Inserts the specified element into the queue if possible.
    • Returns true if the element was added, or false if it was not (e.g., due to capacity restrictions).
  3. E remove():

    • Retrieves and removes the head of the queue.
    • Throws an exception if the queue is empty.
  4. E poll():

    • Retrieves and removes the head of the queue.
    • Returns null if the queue is empty.
  5. E element():

    • Retrieves, but does not remove, the head of the queue.
    • Throws an exception if the queue is empty.
  6. E peek():

    • Retrieves, but does not remove, the head of the queue.
    • Returns null if the queue is empty.

Implementations

  1. LinkedList<E>:

    • Implements Queue using a doubly linked list.
    • Provides efficient add, remove, peek, and poll operations.
    • Suitable for general-purpose FIFO queues.
  2. PriorityQueue<E>:

    • Implements Queue using a priority heap.
    • Elements are ordered according to their natural ordering or by a specified comparator.
    • Supports efficient retrieval of the smallest (or largest) element.

Deque Interface in Java

The Deque interface in Java represents a double-ended queue, which allows insertion and removal of elements from both ends. It extends the Queue interface and provides versatile methods for stack-like (LIFO) and queue-like (FIFO) operations. Deque implementations typically offer more functionality than Queue implementations and can be used in scenarios requiring efficient insertion, removal, and traversal of elements from both ends.

Overview

  • Double-Ended Queue: Supports insertion and removal of elements from both ends.
  • Versatility: Provides methods for stack operations (LIFO - Last-In-First-Out) and queue operations (FIFO - First-In-First-Out).
  • Implementations: Java provides several implementations of the Deque interface, each with unique characteristics suitable for different use cases.

Common Methods

  1. Adding Elements:

    • void addFirst(E element): Inserts the specified element at the beginning of the deque.
    • void addLast(E element): Inserts the specified element at the end of the deque.
    • boolean offerFirst(E element): Inserts the specified element at the beginning of the deque if possible.
    • boolean offerLast(E element): Inserts the specified element at the end of the deque if possible.
  2. Removing Elements:

    • E removeFirst(): Retrieves and removes the first element of the deque.
    • E removeLast(): Retrieves and removes the last element of the deque.
    • E pollFirst(): Retrieves and removes the first element of the deque, or returns null if empty.
    • E pollLast(): Retrieves and removes the last element of the deque, or returns null if empty.
  3. Retrieving Elements:

    • E getFirst(): Retrieves, but does not remove, the first element of the deque.
    • E getLast(): Retrieves, but does not remove, the last element of the deque.
    • E peekFirst(): Retrieves, but does not remove, the first element of the deque, or returns null if empty.
    • E peekLast(): Retrieves, but does not remove, the last element of the deque, or returns null if empty.
  4. Other Operations:

    • boolean removeFirstOccurrence(Object object): Removes the first occurrence of the specified element from the deque.
    • boolean removeLastOccurrence(Object object): Removes the last occurrence of the specified element from the deque.
    • void push(E element): Pushes an element onto the stack represented by the deque (equivalent to addFirst).
    • E pop(): Pops an element from the stack represented by the deque (equivalent to removeFirst).

Implementations

  1. LinkedList<E>:

    • Implements Deque using a doubly linked list.
    • Provides efficient insertion, removal, and traversal operations from both ends.
    • Suitable for general-purpose double-ended queue operations.
  2. ArrayDeque<E>:

    • Implements Deque using a resizable array.
    • Provides more efficient performance in most cases compared to LinkedList.
    • Suitable for high-performance applications requiring frequent insertion and removal operations.

PriorityQueue in Java [Queue Interface]

PriorityQueue in Java is an implementation of the Queue interface that provides a priority-based ordering of elements. Elements in a PriorityQueue are ordered either by their natural ordering or by a specified comparator, and the least element according to this ordering is always at the front of the queue. This makes PriorityQueue suitable for applications where elements need to be processed based on their priority levels.

Overview

  • Priority-Based Ordering: Elements are ordered based on their natural ordering (if they implement Comparable) or by a specified comparator.
  • Heap-Based Structure: Internally implemented using a priority heap, which allows efficient retrieval of the smallest (or largest) element.
  • No Random Access: Does not provide indexed access to elements like ArrayList or LinkedList.

Creation

  1. Default Constructor: Constructs an empty priority queue with an initial capacity of 11.
   PriorityQueue<Integer> pq = new PriorityQueue<>();
Enter fullscreen mode Exit fullscreen mode
  1. Initialization with Comparator: Constructs a priority queue with the specified initial capacity and comparator.
   PriorityQueue<String> pq = new PriorityQueue<>(Comparator.reverseOrder());
Enter fullscreen mode Exit fullscreen mode
  1. Initialization from Collection: Constructs a priority queue containing the elements of the specified collection.
   Set<Integer> set = new HashSet<>();
   // add elements to set
   PriorityQueue<Integer> pq = new PriorityQueue<>(set);
Enter fullscreen mode Exit fullscreen mode

Key Methods

  1. boolean add(E element) or boolean offer(E element):
    • Inserts the specified element into the priority queue.
   pq.add(5);
   pq.offer(10);
Enter fullscreen mode Exit fullscreen mode
  1. E remove() or E poll():
    • Retrieves and removes the head of the priority queue (i.e., the smallest element).
   int smallest = pq.remove();
   int nextSmallest = pq.poll();
Enter fullscreen mode Exit fullscreen mode
  1. E peek():
    • Retrieves, but does not remove, the head of the priority queue, or returns null if the queue is empty.
   int minElement = pq.peek();
Enter fullscreen mode Exit fullscreen mode
  1. boolean isEmpty():
    • Returns true if the priority queue contains no elements.
   boolean empty = pq.isEmpty();
Enter fullscreen mode Exit fullscreen mode
  1. int size():
    • Returns the number of elements in the priority queue.
   int size = pq.size();
Enter fullscreen mode Exit fullscreen mode
  1. void clear():
    • Removes all of the elements from the priority queue.
   pq.clear();
Enter fullscreen mode Exit fullscreen mode

LinkedList in Java [Deque Interface]

LinkedList in Java implements both the List and Deque interfaces, providing a versatile doubly linked list implementation that supports both stack-like (LIFO - Last-In-First-Out) and queue-like (FIFO - First-In-First-Out) operations. It offers efficient insertion, deletion, and traversal operations from both ends of the list, making it suitable for scenarios where dynamic and flexible data manipulation is required.

Overview

  • Doubly Linked List: Uses a doubly linked list structure where each element is stored in a node containing references to the next and previous elements.
  • Deque Operations: Supports stack operations (push, pop) and queue operations (offer, poll) efficiently.
  • Random Access: Provides indexed access to elements similar to ArrayList, but with slower performance.

Creation

  1. Default Constructor: Constructs an empty linked list.
   LinkedList<String> list = new LinkedList<>();
Enter fullscreen mode Exit fullscreen mode
  1. Initialization from Collection: Constructs a linked list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
   Set<Integer> set = new HashSet<>();
   // add elements to set
   LinkedList<Integer> list = new LinkedList<>(set);
Enter fullscreen mode Exit fullscreen mode

Key Methods (Deque Operations)

  1. Adding Elements:
  • void addFirst(E element): Inserts the specified element at the beginning of the deque.

     list.addFirst("first");
    
  • void addLast(E element): Appends the specified element to the end of the deque.

     list.addLast("last");
    
  • boolean offerFirst(E element): Inserts the specified element at the beginning of the deque if possible.

     list.offerFirst("first");
    
  • boolean offerLast(E element): Appends the specified element to the end of the deque if possible.

     list.offerLast("last");
    
  1. Removing Elements:
  • E removeFirst(): Retrieves and removes the first element of the deque.

     String firstElement = list.removeFirst();
    
  • E removeLast(): Retrieves and removes the last element of the deque.

     String lastElement = list.removeLast();
    
  • E pollFirst(): Retrieves and removes the first element of the deque, or returns null if empty.

     String firstElement = list.pollFirst();
    
  • E pollLast(): Retrieves and removes the last element of the deque, or returns null if empty.

     String lastElement = list.pollLast();
    
  1. Retrieving Elements:
  • E getFirst(): Retrieves, but does not remove, the first element of the deque.

     String firstElement = list.getFirst();
    
  • E getLast(): Retrieves, but does not remove, the last element of the deque.

     String lastElement = list.getLast();
    
  • E peekFirst(): Retrieves, but does not remove, the first element of the deque, or returns null if empty.

     String firstElement = list.peekFirst();
    
  • E peekLast(): Retrieves, but does not remove, the last element of the deque, or returns null if empty.

     String lastElement = list.peekLast();
    
  1. Stack Operations:
  • void push(E element): Pushes an element onto the stack represented by the deque (equivalent to addFirst).

     list.push("top");
    
  • E pop(): Pops an element from the stack represented by the deque (equivalent to removeFirst).

     String topElement = list.pop();
    

Set Interface in Java

The Set interface in Java represents a collection of unique elements, ensuring that no duplicates are allowed. It extends the Collection interface and provides methods for adding, removing, and checking the presence of elements. Sets are commonly used for tasks where uniqueness of elements is essential, such as storing a collection of unique identifiers or filtering out duplicate entries from data.

Overview

  • Uniqueness: Does not allow duplicate elements; each element in a set must be unique.
  • Implementations: Java provides several implementations of the Set interface, each with unique characteristics suited for different use cases.
  • Mathematical Set Operations: Supports operations like union, intersection, and difference, making it useful for set theory operations.

Common Methods

  1. Adding Elements:

    • boolean add(E element): Adds the specified element to the set if it is not already present.
    • boolean addAll(Collection<? extends E> collection): Adds all elements from the specified collection to the set if they are not already present.
  2. Removing Elements:

    • boolean remove(Object object): Removes the specified element from the set if it is present.
    • boolean removeAll(Collection<?> collection): Removes all elements from the set that are present in the specified collection.
    • void clear(): Removes all elements from the set.
  3. Checking Presence:

    • boolean contains(Object object): Returns true if the set contains the specified element.
    • boolean containsAll(Collection<?> collection): Returns true if the set contains all elements in the specified collection.
    • boolean isEmpty(): Returns true if the set contains no elements.
  4. Set Operations:

    • boolean retainAll(Collection<?> collection): Retains only the elements in the set that are also present in the specified collection (intersection operation).
    • int size(): Returns the number of elements in the set.

Implementations

  1. HashSet<E>:

    • Implements Set using a hash table.
    • Provides constant-time performance for basic operations (add, remove, contains), assuming a good hash function.
    • Does not guarantee the order of elements.
  2. LinkedHashSet<E>:

    • Extends HashSet to maintain a linked list of entries in the order they were inserted.
    • Provides predictable iteration order (insertion-order), which is useful when order matters.
  3. TreeSet<E>:

    • Implements Set using a self-balancing binary search tree (Red-Black Tree).
    • Guarantees log(n) time complexity for add, remove, and contains operations.
    • Maintains elements in sorted order (natural ordering or by a specified comparator).

HashSet in Java [Set Interface]

HashSet in Java is an implementation of the Set interface that uses a hash table for storage. It provides constant-time performance for basic operations like add, remove, and contains, assuming a good hash function. HashSet does not guarantee the order of elements, making it suitable for scenarios where uniqueness of elements is more critical than maintaining insertion order.

Overview

  • Hash Table Implementation: Uses a hash table to store elements.
  • Uniqueness: Ensures that no duplicate elements are allowed.
  • Performance: Offers average constant-time performance (O(1)) for add, remove, and contains operations, assuming uniform hash distribution.

Creation

  1. Default Constructor: Constructs an empty HashSet with an initial capacity of 16 and a load factor of 0.75.
   HashSet<String> set = new HashSet<>();
Enter fullscreen mode Exit fullscreen mode
  1. Initialization with Capacity and Load Factor: Constructs a HashSet with the specified initial capacity and load factor.
   HashSet<Integer> set = new HashSet<>(100, 0.8f);  // initial capacity of 100, load factor of 0.8
Enter fullscreen mode Exit fullscreen mode
  1. Initialization from Collection: Constructs a HashSet containing the elements of the specified collection.
   Set<String> collection = new ArrayList<>();
   // add elements to collection
   HashSet<String> set = new HashSet<>(collection);
Enter fullscreen mode Exit fullscreen mode

Key Methods

  1. Adding Elements:
  • boolean add(E element): Adds the specified element to the set if it is not already present.

     set.add("apple");
    
  • boolean addAll(Collection<? extends E> collection): Adds all elements from the specified collection to the set if they are not already present.

     List<String> fruits = Arrays.asList("apple", "banana", "orange");
     set.addAll(fruits);
    
  1. Removing Elements:
  • boolean remove(Object object): Removes the specified element from the set if it is present.

     set.remove("apple");
    
  • boolean removeAll(Collection<?> collection): Removes all elements from the set that are present in the specified collection.

     List<String> fruitsToRemove = Arrays.asList("apple", "banana");
     set.removeAll(fruitsToRemove);
    
  • void clear(): Removes all elements from the set.

     set.clear();
    
  1. Checking Presence:
  • boolean contains(Object object): Returns true if the set contains the specified element.

     boolean containsApple = set.contains("apple");
    
  • boolean containsAll(Collection<?> collection): Returns true if the set contains all elements in the specified collection.

     List<String> fruitsToCheck = Arrays.asList("apple", "banana");
     boolean containsAll = set.containsAll(fruitsToCheck);
    
  1. Other Operations:
  • int size(): Returns the number of elements in the set.

     int setSize = set.size();
    
  • boolean isEmpty(): Returns true if the set contains no elements.

     boolean empty = set.isEmpty();
    

TreeSet in Java [Set Interface]

TreeSet in Java is an implementation of the SortedSet interface that uses a self-balancing binary search tree (Red-Black Tree) to store elements. It maintains elements in sorted order either using their natural ordering or a specified comparator. TreeSet provides guaranteed log(n) time complexity for basic operations like add, remove, and contains, making it suitable for scenarios where elements need to be stored in a sorted manner.

Overview

  • Self-Balancing Binary Search Tree: Uses a Red-Black Tree to store elements.
  • Sorted Order: Maintains elements in sorted (ascending) order based on either natural ordering or a comparator.
  • Performance: Offers logarithmic time complexity (O(log n)) for add, remove, and contains operations.

Creation

  1. Default Constructor: Constructs an empty TreeSet sorted according to the natural ordering of its elements.
   TreeSet<String> set = new TreeSet<>();
Enter fullscreen mode Exit fullscreen mode
  1. Initialization with Comparator: Constructs a TreeSet sorted according to the specified comparator.
   TreeSet<Integer> set = new TreeSet<>(Comparator.reverseOrder());
Enter fullscreen mode Exit fullscreen mode
  1. Initialization from Collection: Constructs a TreeSet containing the elements of the specified collection.
   List<String> list = Arrays.asList("apple", "banana", "orange");
   TreeSet<String> set = new TreeSet<>(list);
Enter fullscreen mode Exit fullscreen mode

Key Methods

  1. Adding Elements:
  • boolean add(E element): Adds the specified element to the set if it is not already present.

     set.add("apple");
    
  • boolean addAll(Collection<? extends E> collection): Adds all elements from the specified collection to the set if they are not already present.

     List<String> fruits = Arrays.asList("apple", "banana", "orange");
     set.addAll(fruits);
    
  1. Removing Elements:
  • boolean remove(Object object): Removes the specified element from the set if it is present.

     set.remove("apple");
    
  • boolean removeAll(Collection<?> collection): Removes all elements from the set that are present in the specified collection.

     List<String> fruitsToRemove = Arrays.asList("apple", "banana");
     set.removeAll(fruitsToRemove);
    
  • void clear(): Removes all elements from the set.

     set.clear();
    
  1. Checking Presence:
  • boolean contains(Object object): Returns true if the set contains the specified element.

     boolean containsApple = set.contains("apple");
    
  • boolean containsAll(Collection<?> collection): Returns true if the set contains all elements in the specified collection.

     List<String> fruitsToCheck = Arrays.asList("apple", "banana");
     boolean containsAll = set.containsAll(fruitsToCheck);
    
  1. Navigable Set Operations:
  • E first(): Returns the first (lowest) element currently in the set.

     String firstElement = set.first();
    
  • E last(): Returns the last (highest) element currently in the set.

     String lastElement = set.last();
    
  • E ceiling(E element): Returns the least element in the set greater than or equal to the given element, or null if there is no such element.

     String ceilingElement = set.ceiling("banana");
    
  • E floor(E element): Returns the greatest element in the set less than or equal to the given element, or null if there is no such element.

     String floorElement = set.floor("banana");
    

Collections Class in Java

The Collections class in Java provides utility methods for working with collections (List, Set, etc.). It offers various static methods for sorting, searching, and manipulating collections. These methods are useful for operations that are not specific to any particular type of collection, making them versatile for handling different data structures in Java.

Overview

  • Utility Methods: Provides static methods for operations such as sorting, searching, reversing, and more.
  • Static Methods: All methods in the Collections class are static, allowing them to be called directly without creating an instance of the class.
  • Generics Support: Supports generic types (<E>) to work with different types of collections (List<E>, Set<E>, etc.).

Key Methods

  1. Sorting:
  • sort(List<T> list): Sorts the specified list into ascending order, according to the natural ordering of its elements.

     List<Integer> numbers = Arrays.asList(5, 3, 8, 1, 2);
     Collections.sort(numbers);
    
  • sort(List<T> list, Comparator<? super T> c): Sorts the specified list according to the order induced by the specified comparator.

     List<String> names = Arrays.asList("Alice", "Bob", "Charlie");
     Collections.sort(names, Comparator.reverseOrder());
    
  1. Searching:
  • binarySearch(List<? extends Comparable<? super T>> list, T key): Searches the specified list for the specified key using the binary search algorithm.

     List<Integer> numbers = Arrays.asList(1, 3, 5, 7, 9);
     int index = Collections.binarySearch(numbers, 5);  // returns index of 5
    
  • binarySearch(List<? extends T> list, T key, Comparator<? super T> c): Searches the specified list for the specified key using the binary search algorithm based on the specified comparator.

     List<String> names = Arrays.asList("Alice", "Bob", "Charlie");
     int index = Collections.binarySearch(names, "Bob", Comparator.naturalOrder());
    
  1. Other Operations:
  • reverse(List<?> list): Reverses the order of elements in the specified list.

     List<Integer> numbers = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));
     Collections.reverse(numbers);
    

Arrays Class in Java

In Java, the Arrays class is part of the java.util package and provides utility methods for working with arrays. It offers static methods for performing various operations on arrays, including sorting, searching, filling, and converting arrays to collections. These methods are designed to efficiently handle arrays of different types, including arrays of objects, primitive types, and generic types.

Overview

  • Utility Methods: Provides static methods for operations such as sorting, searching, filling, copying, and converting arrays.
  • Static Methods: All methods in the Arrays class are static, allowing them to be called directly without creating an instance of the class.
  • Generics Support: Supports generic types (<T>) to work with arrays of different types, including primitive types (int[], double[], etc.).

Key Methods

  1. Sorting:
  • sort(T[] a): Sorts the specified array into ascending order, according to the natural ordering of its elements.

     Integer[] numbers = {5, 3, 8, 1, 2};
     Arrays.sort(numbers);
    
  • sort(T[] a, Comparator<? super T> c): Sorts the specified array according to the order induced by the specified comparator.

     String[] names = {"Alice", "Bob", "Charlie"};
     Arrays.sort(names, Comparator.reverseOrder());
    
  1. Searching:
  • binarySearch(T[] a, T key): Searches the specified sorted array for the specified key using the binary search algorithm.

     Integer[] numbers = {1, 3, 5, 7, 9};
     int index = Arrays.binarySearch(numbers, 5);  // returns index of 5
    
  • binarySearch(T[] a, T key, Comparator<? super T> c): Searches the specified sorted array for the specified key using the binary search algorithm based on the specified comparator.

     String[] names = {"Alice", "Bob", "Charlie"};
     int index = Arrays.binarySearch(names, "Bob", Comparator.naturalOrder());
    
  1. Other Operations:
  • fill(T[] a, T val): Assigns the specified value to each element of the specified array.

     Integer[] numbers = new Integer[5];
     Arrays.fill(numbers, 10);  // {10, 10, 10, 10, 10}
    
  • asList(T... a): Returns a fixed-size list backed by the specified array.

     String[] names = {"Alice", "Bob", "Charlie"};
     List<String> list = Arrays.asList(names);
    
  • copyOf(T[] original, int newLength): Copies the specified array, truncating or padding with default values if necessary to obtain the specified length.

     Integer[] numbers = {1, 2, 3, 4, 5};
     Integer[] copiedArray = Arrays.copyOf(numbers, 3);  // {1, 2, 3}
    
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .