Java Collection Framework

What Is Java Collection Framework?

• The Java platform includes a collections framework. A collection is an object that represents a group of objects (such as the classic Vector class). A collections framework is a unified architecture for representing and manipulating collections, enabling collections to be manipulated independently of implementation details.
• Below are the primary advantages of a collections framework

Advantages	Details
Reduces programming effort	by providing data structures and algorithms so you don't have to write them yourself.
Increases performance	by providing high-performance implementations of data structures and algorithms. Because the various implementations of each interface are interchangeable, programs can be tuned by switching implementations.
Provides interoperability between unrelated APIs	by establishing a common language to pass collections back and forth.
Reduces the effort required to learn APIs	by requiring you to learn multiple ad hoc collection APIs.
Reduces the effort required to design and implement APIs	by not requiring you to produce ad hoc collections APIs.
Fosters software reuse	by providing a standard interface for collections and algorithms with which to manipulate them.

The collections framework consists of components.

Components	Details
Collection interfaces	Represent different types of collections, such as sets, lists, and maps. These interfaces form the basis of the framework.
General-purpose implementations	Primary implementations of the collection interfaces.
Legacy implementations	The collection classes from earlier releases, Vector and Hashtable, were retrofitted to implement the collection interfaces.
Special-purpose implementations	Implementations designed for use in special situations. These implementations display nonstandard performance characteristics, usage restrictions, or behavior.
Concurrent implementations	Implementations designed for highly concurrent use.
Wrapper implementations	Add functionality, such as synchronization, to other implementations.
Convenience implementations	High-performance "mini-implementations" of the collection interfaces.
Abstract implementations	Partial implementations of the collection interfaces to facilitate custom implementations.
Algorithms	Static methods that perform useful functions on collections, such as sorting a list.
Infrastructure	Interfaces that provide essential support for the collection interfaces.
Array Utilities	Utility functions for arrays of primitive types and reference objects. Not, strictly speaking, a part of the collections framework, this feature was added to the Java platform at the same time as the collections framework and relies on some of the same infrastructure.

Java Collection Framework Hierarchy

• The hierarchy of collection framework is showed as below.

• The collection interfaces are divided into two groups. The most basic interface, java.util.Collection, has the following descendants:

• java.util.Set
• java.util.SortedSet
• java.util.Queue
• java.util.Deque
• java.util.List

• The other collection interfaces are based on java.util.Map and are not true collections. However, these interfaces contain collection-view operations, which enable them to be manipulated as collections. Map has the following offspring:

• java.util.SortedMap
• java.util.NavigableMap

Collection Framework Interfaces

Iterable Interface

• Iterable Interface: This is the root interface for the entire collection framework. The collection interface extends the iterable interface. Therefore, inherently, all the interfaces and classes implement this interface. The main functionality of this interface is to provide an iterator for the collections. Therefore, this interface contains only one abstract method which is the iterator. It returns the.

/*
 * Copyright (c) 2003, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 */
package java.lang;

import java.util.Iterator;
import java.util.Objects;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Consumer;

/**
 * Implementing this interface allows an object to be the target of
 * the "for-each loop" statement. See
 * <strong>
 * <a href="{@docRoot}/../technotes/guides/language/foreach.html">For-each Loop</a>
 * </strong>
 *
 * @param <T> the type of elements returned by the iterator
 *
 * @since 1.5
 * @jls 14.14.2 The enhanced for statement
 */
public interface Iterable<T> {
    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    Iterator<T> iterator();

    /**
     * Performs the given action for each element of the {@code Iterable}
     * until all elements have been processed or the action throws an
     * exception.  Unless otherwise specified by the implementing class,
     * actions are performed in the order of iteration (if an iteration order
     * is specified).  Exceptions thrown by the action are relayed to the
     * caller.
     *
     * @implSpec
     * <p>The default implementation behaves as if:
     * <pre>{@code
     *     for (T t : this)
     *         action.accept(t);
     * }</pre>
     *
     * @param action The action to be performed for each element
     * @throws NullPointerException if the specified action is null
     * @since 1.8
     */
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

    /**
     * Creates a {@link Spliterator} over the elements described by this
     * {@code Iterable}.
     *
     * @implSpec
     * The default implementation creates an
     * <em><a href="Spliterator.html#binding">early-binding</a></em>
     * spliterator from the iterable's {@code Iterator}.  The spliterator
     * inherits the <em>fail-fast</em> properties of the iterable's iterator.
     *
     * @implNote
     * The default implementation should usually be overridden.  The
     * spliterator returned by the default implementation has poor splitting
     * capabilities, is unsized, and does not report any spliterator
     * characteristics. Implementing classes can nearly always provide a
     * better implementation.
     *
     * @return a {@code Spliterator} over the elements described by this
     * {@code Iterable}.
     * @since 1.8
     */
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

Collection Interface

• java.util.Collection is the root interface of Collection Framework. It contains some important methods such as size(), iterator(), add(), remove() and clear(). Below is all methods of java.util.Collection.

Method	Description
public boolean add(E e)	It is used to insert an element in this collection.
public boolean addAll(Collection<? extends E> c)	It is used to insert the specified collection elements in the invoking collection.
public boolean remove(Object element)	It is used to delete an element from the collection.
public boolean removeAll(Collection<?> c)	It is used to delete all the elements of the specified collection from the invoking collection.
default boolean removeIf(Predicate<? super E> filter)	It is used to delete all the elements of the collection that satisfy the specified predicate.
public boolean retainAll(Collection<?> c)	It is used to delete all the elements of invoking collection except the specified collection.
public int size()	It returns the total number of elements in the collection.
public void clear()	It removes the total number of elements from the collection.
public boolean contains(Object element)	It is used to search an element.
public boolean containsAll(Collection<?> c)	It is used to search the specified collection in the collection.
public Iterator iterator()	It returns an iterator.
public Object[] toArray()	It converts collection into array.
public <T> T[] toArray(T[] a)	It converts collection into array. Here, the runtime type of the returned array is that of the specified array.
public boolean isEmpty()	It checks if collection is empty.
default Stream<E> parallelStream()	It returns a possibly parallel Stream with the collection as its source.
default Stream<E> stream()	It returns a sequential Stream with the collection as its source.
default Spliterator<E> spliterator()	It generates a Spliterator over the specified elements in the collection.
public boolean equals(Object element)	It matches two collections.
public int hashCode()	It returns the hash code number of the collection.

• List, Set Queue are other important interfaces that inherit from the Collection interface.
• Map is the only interface that does not inherit from the Collection interface but it is part of Collection Framework.
• All the collection framework interfaces are present in java.util.package

List Interface

• List interface is the child interface of Collection interface. It inhibits a list type data structure in which we can store the ordered collection of objects. It can have duplicate values.
• List Interface contains methods as below

Method	Description
void add(int index, E element)	It is used to insert the specified element at the specified position in a list.
boolean add(E e)	It is used to append the specified element at the end of a list.
boolean addAll(Collection<? extends E> c)	It is used to append all of the elements in the specified collection to the end of a list.
boolean addAll(int index, Collection<? extends E> c)	It is used to append all the elements in the specified collection, starting at the specified position of the list.
void clear()	It is used to remove all of the elements from this list.
boolean equals(Object o)	It is used to compare the specified object with the elements of a list.
int hashcode()	It is used to return the hash code value for a list.
E get(int index)	It is used to fetch the element from the particular position of the list.
boolean isEmpty()	It returns true if the list is empty, otherwise false.
int lastIndexOf(Object o)	It is used to return the index in this list of the last occurrence of the specified element, or -1 if the list does not contain this element.
Object[] toArray()	It is used to return an array containing all of the elements in this list in the correct order.
<T> T[] toArray(T[] a)	It is used to return an array containing all of the elements in this list in the correct order.
boolean contains(Object o)	It returns true if the list contains the specified element
boolean containsAll(Collection<?> c)	It returns true if the list contains all the specified element
int indexOf(Object o)	It is used to return the index in this list of the first occurrence of the specified element, or -1 if the List does not contain this element.
E remove(int index)	It is used to remove the element present at the specified position in the list.
boolean remove(Object o)	It is used to remove the first occurrence of the specified element.
boolean removeAll(Collection<?> c)	It is used to remove all the elements from the list.
void replaceAll(UnaryOperator<E> operator)	It is used to replace all the elements from the list with the specified element.
void retainAll(Collection<?> c)	It is used to retain all the elements in the list that are present in the specified collection.
E set(int index, E element)	It is used to replace the specified element in the list, present at the specified position.
void sort(Comparator<? super E> c)	It is used to sort the elements of the list on the basis of specified comparator.
Spliterator<E> spliterator()	It is used to create spliterator over the elements in a list.
List<E> subList(int fromIndex, int toIndex)	It is used to fetch all the elements lies within the given range.
int size()	It is used to return the number of elements present in the list.

• List interface is implemented by the classes ArrayList, LinkedList, Vector, and Stack.
• To instantiate the List interface, we must use :

List<T> list1 = new ArrayList();  
List<T> list2 = new LinkedList();  
List<T> list3 = new Vector();  
List<T> list4 = new Stack();  

//Where T is the type of the object.

Queue Interface

• Queue interface maintains the first-in-first-out order. It can be defined as an ordered list that is used to hold the elements which are about to be processed. There are various classes like PriorityQueue, Deque, and ArrayDeque which implements the Queue interface.
• Queue Interface contains methods as in the table below:

Method	Description
boolean add(E e)	Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
E element()	Retrieves, but does not remove, the head of this queue.
boolean offer(E e)	Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions.
E peek()	Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E poll()	Retrieves and removes the head of this queue, or returns null if this queue is empty.
E remove()	Retrieves and removes the head of this queue.

• Queue interface can be instantiated as:

Queue <T> pq = new PriorityQueue<> ();   
Queue <T> ad = new ArrayDeque<> (); 

//Where T is the type of the object.

Deque Interface

• Deque interface extends the Queue interface. In Deque, we can remove and add the elements from both the side. Deque stands for a double-ended queue which enables us to perform the operations at both the ends.
• Deque interface contains methods as in the table below

Method	Description
boolean add(E e)	Inserts the specified element into the queue represented by this deque (in other words, at the tail of this deque) if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
void addFirst(E e)	Inserts the specified element at the front of this deque if it is possible to do so immediately without violating capacity restrictions.
void addLast(E e)	Inserts the specified element at the end of this deque if it is possible to do so immediately without violating capacity restrictions.
boolean contains(Object o)	Returns true if this deque contains the specified element.
Iterator<E> descendingIterator()	Returns an iterator over the elements in this deque in reverse sequential order.
E element()	Retrieves, but does not remove, the head of the queue represented by this deque (in other words, the first element of this deque).
E getFirst()	Retrieves, but does not remove, the first element of this deque.
E getLast()	Retrieves, but does not remove, the last element of this deque.
Iterator<E> iterator()	Returns an iterator over the elements in this deque in proper sequence.
boolean offer(E e)	Inserts the specified element into the queue represented by this deque (in other words, at the tail of this deque) if it is possible to do so immediately without violating capacity restrictions, returning true upon success and false if no space is currently available.
boolean offerFirst(E e)	Inserts the specified element at the front of this deque unless it would violate capacity restrictions.
boolean offerLast(E e)	Inserts the specified element at the end of this deque unless it would violate capacity restrictions.
E peek()	Retrieves, but does not remove, the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty.
E peekFirst()	Retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty.
E peekLast()	Retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty.
E poll()	Retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty.
E pollFirst()	Retrieves and removes the first element of this deque, or returns null if this deque is empty.
E pollLast()	Retrieves and removes the last element of this deque, or returns null if this deque is empty.
E pop()	Pops an element from the stack represented by this deque.
void push(E e)	Pushes an element onto the stack represented by this deque (in other words, at the head of this deque) if it is possible to do so immediately without violating capacity restrictions, returning true upon success and throwing an IllegalStateException if no space is currently available.
E remove()	Retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque).
boolean remove(Object o)	Removes the first occurrence of the specified element from this deque.
E removeFirst()	Retrieves and removes the first element of this deque.
boolean removeFirstOccurrence(Object o)	Removes the first occurrence of the specified element from this deque.
E removeLast()	Retrieves and removes the last element of this deque.
boolean removeLastOccurrence(Object o)	Removes the last occurrence of the specified element from this deque.
int size()	Returns the number of elements in this deque.

• Deque can be instantiated as:

Deque<T> ad = new ArrayDeque<> (); 

//Where T is the type of the object.  

Set Interface

• Set Interface in Java is present in java.util package. It extends the Collection interface. It represents the unordered set of elements which doesn't allow us to store the duplicate items. We can store at most one null value in Set. Set is implemented by HashSet, LinkedHashSet, and TreeSet.
• Set interface contains methods as in the table below.

Method	Description
boolean add(E e)	Adds the specified element to this set if it is not already present (optional operation).
boolean addAll(Collection<? extends E> c)	Adds all of the elements in the specified collection to this set if they're not already present (optional operation).
void clear()	Removes all of the elements from this set (optional operation).
boolean contains(Object o)	Returns true if this set contains the specified element.
boolean containsAll(Collection<?> c)	Returns true if this set contains all of the elements of the specified collection.
boolean equals(Object o)	Compares the specified object with this set for equality.
int hashCode()	Returns the hash code value for this set.
boolean isEmpty()	Returns true if this set contains no elements.
Iterator<E> iterator()	Returns an iterator over the elements in this set.
boolean remove(Object o)	Removes the specified element from this set if it is present (optional operation).
boolean removeAll(Collection<?> c)	Removes from this set all of its elements that are contained in the specified collection (optional operation).
boolean retainAll(Collection<?> c)	Retains only the elements in this set that are contained in the specified collection (optional operation).
int size()	Returns the number of elements in this set (its cardinality).
default Spliterator<E> spliterator()	Creates a Spliterator over the elements in this set.
Object[] toArray()	Returns an array containing all of the elements in this set.
<T> T[] toArray(T[] a)	Returns an array containing all of the elements in this set; the runtime type of the returned array is that of the specified array.

• Set can be instantiated as:

Set<T> hs = new HashSet<> (); 
Set<T> lhs = new LinkedHashSet<> (); 
Set<T> ts = new TreeSet<> (); 

//Where T is the type of the object.  

SortedSet Interface

• SortedSet is the alternate of Set interface that provides a total ordering on its elements. The elements of the SortedSet are arranged in the increasing (ascending) order. The SortedSet provides the additional methods that inhibit the natural ordering of the elements.
• SortedSet interface contains methods as in the table below.

Method	Description
Comparator<? super E> comparator()	Returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements.
E first()	Returns the first (lowest) element currently in this set.
SortedSet<E> headSet(E toElement)	Returns a view of the portion of this set whose elements are strictly less than toElement.
E last()	Returns the last (highest) element currently in this set.
default Spliterator<E> spliterator()	Creates a Spliterator over the elements in this sorted set.
SortedSet<E> subSet(E fromElement, E toElement)	Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.
SortedSet<E> tailSet(E fromElement)	Returns a view of the portion of this set whose elements are greater than or equal to fromElement.

• The SortedSet can be instantiated as:

SortedSet<T> ts = new TreeSet<> (); 

//Where T is the type of the object.  

Map

• Map Interface: A map is a data structure that supports the key-value pair mapping for the data. This interface doesn’t support duplicate keys because the same key cannot have multiple mappings. A map is useful if there is data and we wish to perform operations on the basis of the key. This map interface is implemented by various classes like HashMap, TreeMap, etc. Since all the subclasses implement the map, we can instantiate a map object with any of these classes. For example.

Map<T> hm = new HashMap<> ();   
Map<T> tm = new TreeMap<> ();  
   
//Where T is the type of the object.

• Map interface contains methods as in the table below.

Method	Description
void clear()	Removes all of the mappings from this map (optional operation).
default V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)	Attempts to compute a mapping for the specified key and its current mapped value (or null if there is no current mapping).
default V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction)	If the specified key is not already associated with a value (or is mapped to null), attempts to compute its value using the given mapping function and enters it into this map unless null.
default V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)	If the value for the specified key is present and non-null, attempts to compute a new mapping given the key and its current mapped value.
boolean containsKey(Object key)	Returns true if this map contains a mapping for the specified key.
boolean containsValue(Object value)	Returns true if this map maps one or more keys to the specified value.
Set<Map.Entry<K,V>> entrySet()	Returns a Set view of the mappings contained in this map.
boolean equals(Object o)	Compares the specified object with this map for equality.
default void forEach(BiConsumer<? super K,? super V> action)	Performs the given action for each entry in this map until all entries have been processed or the action throws an exception.
V get(Object key)	Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
default V getOrDefault(Object key, V defaultValue)	Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.
int hashCode()	Returns the hash code value for this map.
boolean isEmpty()	Returns true if this map contains no key-value mappings.
Set<K> keySet()	Returns a Set view of the keys contained in this map.
default V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction)	If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value.
V put(K key, V value)	Associates the specified value with the specified key in this map (optional operation).
void putAll(Map<? extends K,? extends V> m)	Copies all of the mappings from the specified map to this map (optional operation).
default V putIfAbsent(K key, V value)	If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value.
V remove(Object key)	Removes the mapping for a key from this map if it is present (optional operation).
default boolean remove(Object key, Object value)	Removes the entry for the specified key only if it is currently mapped to the specified value.
default V replace(K key, V value)	Replaces the entry for the specified key only if it is currently mapped to some value.
default boolean replace(K key, V oldValue, V newValue)	Replaces the entry for the specified key only if currently mapped to the specified value.
default void replaceAll(BiFunction<? super K,? super V,? extends V> function)	Replaces each entry's value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.
int size()	Returns the number of key-value mappings in this map.
Collection<V> values()	Returns a Collection view of the values contained in this map.

Collection Framework Implementations

ArrayList

• Java ArrayList class uses a dynamic array for storing the elements. It is like an array, but there is no size limit. We can add or remove elements anytime. So, it is much more flexible than the traditional array. It is found in the java.util package. It is like the Vector in C++.
• The ArrayList in Java can have the duplicate elements also. It implements the List interface so we can use all the methods of the List interface here. The ArrayList maintains the insertion order internally.
• It inherits the AbstractList class and implements List interface.

• The important points about the Java ArrayList class are:

  • Java ArrayList class can contain duplicate elements.
  • Java ArrayList class maintains insertion order.
  • Java ArrayList class is non synchronized.
  • Java ArrayList allows random access because the array works on an index basis.
  • In ArrayList, manipulation is a little bit slower than the LinkedList in Java because a lot of shifting needs to occur if any element is removed from the array list.

• We can not create an array list of the primitive types, such as int, float, char, etc. It is required to use the required wrapper class in such cases. For example:

ArrayList<int> al = ArrayList<int>(); // does not work  
ArrayList<Integer> al = new ArrayList<Integer>(); // works fine  

• Java ArrayList gets initialized by the size. The size is dynamic in the array list, which varies according to the elements getting added or removed from the list.
• Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more elements, or explicitly resizes the backing array; merely setting the value of an element is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the list. If no such object exists, the list should be "wrapped" using the method below. This is best done at creation time, to prevent accidental unsynchronized access to the list.

List<T> list = Collections.synchronizedList(new ArrayList(...));

//Where T is the type of the object.

• ArrayList contains constructors as below:

Constructor	Description
ArrayList()	Constructs an empty list with an initial capacity of ten.
ArrayList(Collection<? extends E> c)	Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.
ArrayList(int initialCapacity)	Constructs an empty list with the specified initial capacity.

• All implemented methods of ArrayList are shown as in the table below:

Method	Description
boolean add(E e)	Appends the specified element to the end of this list.
void add(int index, E element)	Inserts the specified element at the specified position in this list.
boolean addAll(Collection<? extends E> c)	Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's Iterator.
boolean addAll(int index, Collection<? extends E> c)	Inserts all of the elements in the specified collection into this list, starting at the specified position.
void clear()	Removes all of the elements from this list.
Object clone()	Returns a shallow copy of this ArrayList instance.
boolean contains(Object o)	Returns true if this list contains the specified element.
void ensureCapacity(int minCapacity)	Increases the capacity of this ArrayList instance, if necessary, to ensure that it can hold at least the number of elements specified by the minimum capacity argument.
void forEach(Consumer<? super E> action)	Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception.
E get(int index)	Returns the element at the specified position in this list.
int indexOf(Object o)	Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
boolean isEmpty()	Returns true if this list contains no elements.
Iterator<E> iterator()	Returns an iterator over the elements in this list in proper sequence.
int lastIndexOf(Object o)	Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
ListIterator<E> listIterator()	Returns a list iterator over the elements in this list (in proper sequence).
ListIterator<E> listIterator(int index)	Returns a list iterator over the elements in this list (in proper sequence), starting at the specified position in the list.
E remove(int index)	Removes the element at the specified position in this list.
boolean remove(Object o)	Removes the first occurrence of the specified element from this list, if it is present.
boolean removeAll(Collection<?> c)	Removes from this list all of its elements that are contained in the specified collection.
boolean removeIf(Predicate<? super E> filter)	Removes all of the elements of this collection that satisfy the given predicate.
protected void removeRange(int fromIndex, int toIndex)	Removes from this list all of the elements whose index is between fromIndex, inclusive, and toIndex, exclusive.
void replaceAll(UnaryOperator<E> operator)	Replaces each element of this list with the result of applying the operator to that element.
boolean retainAll(Collection<?> c)	Retains only the elements in this list that are contained in the specified collection.
E set(int index, E element)	Replaces the element at the specified position in this list with the specified element.
int size()	Returns the number of elements in this list.
void sort(Comparator<? super E> c)	Sorts this list according to the order induced by the specified Comparator.
Spliterator<E> spliterator()	Creates a late-binding and fail-fast Spliterator over the elements in this list.
List<E> subList(int fromIndex, int toIndex)	Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive.
Object[] toArray()	Returns an array containing all of the elements in this list in proper sequence (from first to last element).
<T> T[] toArray(T[] a)	Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.
void trimToSize()	Trims the capacity of this ArrayList instance to be the list's current size.

LinkedList

• LinkedList is a part of the Collection framework present in java.util package. This class is an implementation of the LinkedList data structure which is a linear data structure where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part. The elements are linked using pointers and addresses. Each element is known as a node.
• Due to the dynamicity and ease of insertions and deletions, they are preferred over the arrays. It also has a few disadvantages like the nodes cannot be accessed directly instead we need to start from the head and follow through the link to reach a node we wish to access.
• LinkedList class uses a doubly linked list to store the elements. It provides a linked-list data structure.
  • A Doubly Linked List (DLL) contains an extra pointer, typically called the previous pointer, together with the next pointer and data which are there in the singly linked list.

• It inherits the AbstractList class and implements List and Deque interfaces.

• The important points about Java LinkedList are:

  • Java LinkedList class can contain duplicate elements.
  • Java LinkedList class maintains insertion order.
  • Java LinkedList class is non synchronized.
  • In Java LinkedList class, manipulation is fast because no shifting needs to occur.
  • Java LinkedList class can be used as a list, stack or queue.

• Like ArrayList, the implementation of LinkedList is not synchronized and in case we want LinkedList become synchronized, the list should be "wrapped" using the method below.

List<T> list = Collections.synchronizedList(new LinkedList(...));

//Where T is the type of the object.

• LinkedList contains constructors as below:

Constructor	Description
LinkedList()	Constructs an empty list.
LinkedList(Collection<? extends E> c)	Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

• All implemented methods of LinkedList are shown as in the table below:

Method	Description
boolean add(E e)	Appends the specified element to the end of this list.
void add(int index, E element)	Inserts the specified element at the specified position in this list.
boolean addAll(Collection<? extends E> c)	Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.
boolean addAll(int index, Collection<? extends E> c)	Inserts all of the elements in the specified collection into this list, starting at the specified position.
void addFirst(E e)	Inserts the specified element at the beginning of this list.
void addLast(E e)	Appends the specified element to the end of this list.
void clear()	Removes all of the elements from this list.
Object clone()	Returns a shallow copy of this LinkedList.
boolean contains(Object o)	Returns true if this list contains the specified element.
Iterator<E> descendingIterator()	Returns an iterator over the elements in this deque in reverse sequential order.
E element()	Retrieves, but does not remove, the head (first element) of this list.
E get(int index)	Returns the element at the specified position in this list.
E getFirst()	Returns the first element in this list.
E getLast()	Returns the last element in this list.
int indexOf(Object o)	Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
int lastIndexOf(Object o)	Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
ListIterator<E> listIterator(int index)	Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.
boolean offer(E e)	Adds the specified element as the tail (last element) of this list.
boolean offerFirst(E e)	Inserts the specified element at the front of this list.
boolean offerLast(E e)	Inserts the specified element at the end of this list.
E peek()	Retrieves, but does not remove, the head (first element) of this list.
E peekFirst()	Retrieves, but does not remove, the first element of this list, or returns null if this list is empty.
E peekLast()	Retrieves, but does not remove, the last element of this list, or returns null if this list is empty.
E poll()	Retrieves and removes the head (first element) of this list.
E pollFirst()	Retrieves and removes the first element of this list, or returns null if this list is empty.
E pollLast()	Retrieves and removes the last element of this list, or returns null if this list is empty.
E pop()	Pops an element from the stack represented by this list.
void push(E e)	Pushes an element onto the stack represented by this list.
E remove()	Retrieves and removes the head (first element) of this list.
E remove(int index)	Removes the element at the specified position in this list.
boolean remove(Object o)	Removes the first occurrence of the specified element from this list, if it is present.
E removeFirst()	Removes and returns the first element from this list.
boolean removeFirstOccurrence(Object o)	Removes the first occurrence of the specified element in this list (when traversing the list from head to tail).
E removeLast()	Removes and returns the last element from this list.
boolean removeLastOccurrence(Object o)	Removes the last occurrence of the specified element in this list (when traversing the list from head to tail).
E set(int index, E element)	Replaces the element at the specified position in this list with the specified element.
int size()	Returns the number of elements in this list.
Spliterator<E> spliterator()	Creates a late-binding and fail-fast Spliterator over the elements in this list.
Object[] toArray()	Returns an array containing all of the elements in this list in proper sequence (from first to last element).
<T> T[] toArray(T[] a)	Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.

Vector

• The Vector class implements a growable array of objects. Like an array, it contains components that can be accessed using an integer index. However, the size of a Vector can grow or shrink as needed to accommodate adding and removing items after the Vector has been created.

• Each vector tries to optimize storage management by maintaining a capacity and a capacityIncrement. The capacity is always at least as large as the vector size; it is usually larger because as components are added to the vector, the vector's storage increases in chunks the size of capacityIncrement. An application can increase the capacity of a vector before inserting a large number of components; this reduces the amount of incremental reallocation.

• The iterators returned by this class's iterator and list Iterator methods are fail-fast: if the vector is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future. The Enumerations returned by the elements method are not fail-fast.

• Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

• As of the Java 2 platform v1.2, this class was retrofitted to implement the List interface, making it a member of the Java Collections Framework. Unlike the new collection implementations, Vector is synchronized. If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector.

• Vector defines three protected data members as below.

Modifier and Type	Field	Description
protected int	capacityIncrement	The amount by which the capacity of the vector is automatically incremented when its size becomes greater than its capacity.
protected int	elementCount	The number of valid components in this Vector object.
protected Object[]	elementData	The array buffer into which the components of the vector are stored.

• Vector defines constructors as below.

Constructor	Description
Vector()	Constructs an empty vector so that its internal data array has size 10 and its standard capacity increment is zero.
Vector(Collection<? extends E> c)	Constructs a vector containing the elements of the specified collection, in the order they are returned by the collection's iterator.
Vector(int initialCapacity)	Constructs an empty vector with the specified initial capacity and with its capacity increment equal to zero.
Vector(int initialCapacity, int capacityIncrement)	Constructs an empty vector with the specified initial capacity and capacity increment.

• All methods of Vector are showed as below.

Modifier	Description
boolean add(E e)	Appends the specified element to the end of this Vector.
void add(int index, E element)	Inserts the specified element at the specified position in this Vector.
boolean addAll(Collection<? extends E> c)	Appends all of the elements in the specified Collection to the end of this Vector, in the order that they are returned by the specified Collection's Iterator.
boolean addAll(int index, Collection<? extends E> c)	Inserts all of the elements in the specified Collection into this Vector at the specified position.
void addElement(E obj)	Adds the specified component to the end of this vector, increasing its size by one.
int capacity()	Returns the current capacity of this vector.
void clear()	Removes all of the elements from this Vector.
Object clone()	Returns a clone of this vector.
boolean contains(Object o)	Returns true if this vector contains the specified element.
boolean containsAll(Collection<?> c)	Returns true if this Vector contains all of the elements in the specified Collection.
void copyInto(Object[] anArray)	Copies the components of this vector into the specified array.
E elementAt(int index)	Returns the component at the specified index.
Enumeration<E> elements()	Returns an enumeration of the components of this vector.
void ensureCapacity(int minCapacity)	Increases the capacity of this vector, if necessary, to ensure that it can hold at least the number of components specified by the minimum capacity argument.
boolean equals(Object o)	Compares the specified Object with this Vector for equality.
E firstElement()	Returns the first component (the item at index 0) of this vector.
void forEach(Consumer<? super E> action)	Performs the given action for each element of the Iterable until all elements have been processed or the action throws an exception.
E get(int index)	Returns the element at the specified position in this Vector.
int hashCode()	Returns the hash code value for this Vector.
int indexOf(Object o)	Returns the index of the first occurrence of the specified element in this vector, or -1 if this vector does not contain the element.
int indexOf(Object o, int index)	Returns the index of the first occurrence of the specified element in this vector, searching forwards from index, or returns -1 if the element is not found.
void insertElementAt(E obj, int index)	Inserts the specified object as a component in this vector at the specified index.
boolean isEmpty()	Tests if this vector has no components.
Iterator<E> iterator()	Returns an iterator over the elements in this list in proper sequence.
E lastElement()	Returns the last component of the vector.
int lastIndexOf(Object o)	Returns the index of the last occurrence of the specified element in this vector, or -1 if this vector does not contain the element.
int lastIndexOf(Object o, int index)	Returns the index of the last occurrence of the specified element in this vector, searching backwards from index, or returns -1 if the element is not found.
ListIterator<E> listIterator()	Returns a list iterator over the elements in this list (in proper sequence).
ListIterator<E> listIterator(int index)	Returns a list iterator over the elements in this list (in proper sequence), starting at the specified position in the list.
E remove(int index)	Removes the element at the specified position in this Vector.
boolean remove(Object o)	Removes the first occurrence of the specified element in this Vector If the Vector does not contain the element, it is unchanged.
boolean removeAll(Collection<?> c)	Removes from this Vector all of its elements that are contained in the specified Collection.
void removeAllElements()	Removes all components from this vector and sets its size to zero.
boolean removeElement(Object obj)	Removes the first (lowest-indexed) occurrence of the argument from this vector.
void removeElementAt(int index)	Deletes the component at the specified index.
boolean removeIf(Predicate<? super E> filter)	Removes all of the elements of this collection that satisfy the given predicate.
protected void removeRange(int fromIndex, int toIndex)	Removes from this list all of the elements whose index is between fromIndex, inclusive, and toIndex, exclusive.
void replaceAll(UnaryOperator<E> operator)	Replaces each element of this list with the result of applying the operator to that element.
boolean retainAll(Collection<?> c)	Retains only the elements in this Vector that are contained in the specified Collection.
E set(int index, E element)	Replaces the element at the specified position in this Vector with the specified element.
void setElementAt(E obj, int index)	Sets the component at the specified index of this vector to be the specified object.
void setSize(int newSize)	Sets the size of this vector.
int size()	Returns the number of components in this vector.
void sort(Comparator<? super E> c)	Sorts this list according to the order induced by the specified Comparator.
Spliterator<E> spliterator()	Creates a late-binding and fail-fast Spliterator over the elements in this list.
List<E> subList(int fromIndex, int toIndex)	Returns a view of the portion of this List between fromIndex, inclusive, and toIndex, exclusive.
Object[] toArray()	Returns an array containing all of the elements in this Vector in the correct order.
<T> T[] toArray(T[] a)	Returns an array containing all of the elements in this Vector in the correct order; the runtime type of the returned array is that of the specified array.
String toString()	Returns a string representation of this Vector, containing the String representation of each element.
void trimToSize()	Trims the capacity of this vector to be the vector's current size.

Stack

• The Stack class represents a last-in-first-out (LIFO) stack of objects. It extends class Vector with five operations that allow a vector to be treated as a stack. The usual push and pop operations are provided, as well as a method to peek at the top item on the stack, a method to test for whether the stack is empty, and a method to search the stack for an item and discover how far it is from the top.
• For the new implementations, we should favor the Deque interface and its implementations. Deque defines a more complete and consistent set of LIFO operations. However, we may still need to deal with the Stack class, especially in legacy code, so it's important to understand it well.
• When a stack is first created, it contains no items but it will have the default capacity of 10. If the number of added elements exceeds the total Stack size, it will be doubled automatically. However, its size will never shrink after removing elements.

• Stack is a direct subclass of Vector; this means that similarly to its superclass, it's a synchronized implementation.

• Stack defines constructors as below.

Constructor	Description
Stack()	Creates an empty Stack.

• All implemented methods of Stack are shown as in the table below:

Method	Description
boolean empty()	Tests if this stack is empty.
E peek()	Looks at the object at the top of this stack without removing it from the stack.
E pop()	Removes the object at the top of this stack and returns that object as the value of this function.
E push(E item)	Pushes an item onto the top of this stack.
int search(Object o)	Returns the 1-based position where an object is on this stack.

PriorityQueue

• A PriorityQueue is used when the objects are supposed to be processed based on the priority. It is known that a Queue follows the First-In-First-Out algorithm, but sometimes the elements of the queue are needed to be processed according to the priority, that’s when the PriorityQueue comes into play.
• An unbounded PriorityQueue based on a priority heap. The elements of the priority queue are ordered according to their natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used. A priority queue does not permit null elements. A PriorityQueue relying on natural ordering also does not permit insertion of non-comparable objects (doing so may result in ClassCastException).
• A priority queue is unbounded, but has an internal capacity governing the size of an array used to store the elements on the queue. It is always at least as large as the queue size. As elements are added to a priority queue, its capacity grows automatically. The details of the growth policy are not specified.

• A few important points on Priority Queue are as follows:

  • PriorityQueue doesn’t permit null.
  • We can’t create a PriorityQueue of Objects that are non-comparable
  • PriorityQueue are unbound queues.
  • The head of this queue is the least element with respect to the specified ordering. If multiple elements are tied for the least value, the head is one of those elements — ties are broken arbitrarily.
  • Since PriorityQueue is not thread-safe, java provides PriorityBlockingQueue class that implements the BlockingQueue interface to use in a java multithreading environment.
  • The queue retrieval operations poll, remove, peek, and element access the element at the head of the queue.
  • It provides O(log(n)) time for add and poll methods.
  • It inherits methods from AbstractQueue, AbstractCollection, Collection, and Object class.

• PriorityQueue contains constructors as below:

Constructor	Description
PriorityQueue()	Creates a PriorityQueue with the default initial capacity (11) that orders its elements according to their natural ordering.
PriorityQueue(Collection<? extends E> c)	Creates a PriorityQueue containing the elements in the specified collection.
PriorityQueue(Comparator<? super E> comparator)	Creates a PriorityQueue with the default initial capacity and whose elements are ordered according to the specified comparator.
PriorityQueue(int initialCapacity)	Creates a PriorityQueue with the specified initial capacity that orders its elements according to their natural ordering.
PriorityQueue(int initialCapacity, Comparator<? super E> comparator)	Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator.
PriorityQueue(PriorityQueue<? extends E> c)	Creates a PriorityQueue containing the elements in the specified priority queue.
PriorityQueue(SortedSet<? extends E> c)	Creates a PriorityQueue containing the elements in the specified sorted set.

• PriorityQueue contains all methods below:

Method	Description
boolean add(E e)	Inserts the specified element into this priority queue.
void clear()	Removes all of the elements from this priority queue.
Comparator<? super E> comparator()	Returns the comparator used to order the elements in this queue, or null if this queue is sorted according to the natural ordering of its elements.
boolean contains(Object o)	Returns true if this queue contains the specified element.
Iterator<E> iterator()	Returns an iterator over the elements in this queue.
boolean offer(E e)	Inserts the specified element into this priority queue.
E peek()	Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
E poll()	Retrieves and removes the head of this queue, or returns null if this queue is empty.
boolean remove(Object o)	Removes a single instance of the specified element from this queue, if it is present.
int size()	Returns the number of elements in this collection.
Spliterator<E> spliterator()	Creates a late-binding and fail-fast Spliterator over the elements in this queue.
Object[] toArray()	Returns an array containing all of the elements in this queue.
<T> T[] toArray(T[] a)	Returns an array containing all of the elements in this queue; the runtime type of the returned array is that of the specified array.

ArrayDeque

• The ArrayDeque in Java provides a way to apply resizable-array in addition to the implementation of the Deque interface. It is also known as Array Double Ended Queue or Array Deck. This is a special kind of array that grows and allows users to add or remove an element from both sides of the queue.

• Few important features of ArrayDeque are as follows:

  • Array deques have no capacity restrictions and they grow as necessary to support usage.
  • They are not thread-safe which means that in the absence of external synchronization, ArrayDeque does not support concurrent access by multiple threads.
  • Null elements are prohibited in the ArrayDeque.
  • ArrayDeque class is likely to be faster than Stack when used as a stack.
  • ArrayDeque class is likely to be faster than LinkedList when used as a queue.

• ArrayDeque contains constructors as below:

Constructor	Description
ArrayDeque()	Constructs an empty array deque with an initial capacity sufficient to hold 16 elements.
ArrayDeque(Collection<? extends E> c)	Constructs a deque containing the elements of the specified collection, in the order they are returned by the collection's iterator.
ArrayDeque(int numElements)	Constructs an empty array deque with an initial capacity sufficient to hold the specified number of elements.

• ArrayDeque contains all methods below:

Method	Description
boolean add(E e)	Inserts the specified element at the end of this deque.
void addFirst(E e)	Inserts the specified element at the front of this deque.
void addLast(E e)	Inserts the specified element at the end of this deque.
void clear()	Removes all of the elements from this deque.
ArrayDeque<E> clone()	Returns a copy of this deque.
boolean contains(Object o)	Returns true if this deque contains the specified element.
Iterator<E> descendingIterator()	Returns an iterator over the elements in this deque in reverse sequential order.
E element()	Retrieves, but does not remove, the head of the queue represented by this deque.
E getFirst()	Retrieves, but does not remove, the first element of this deque.
E getLast()	Retrieves, but does not remove, the last element of this deque.
boolean isEmpty()	Returns true if this deque contains no elements.
Iterator<E> iterator()	Returns an iterator over the elements in this deque.
boolean offer(E e)	Inserts the specified element at the end of this deque.
boolean offerFirst(E e)	Inserts the specified element at the front of this deque.
boolean offerLast(E e)	Inserts the specified element at the end of this deque.
E peek()	Retrieves, but does not remove, the head of the queue represented by this deque, or returns null if this deque is empty.
E peekFirst()	Retrieves, but does not remove, the first element of this deque, or returns null if this deque is empty.
E peekLast()	Retrieves, but does not remove, the last element of this deque, or returns null if this deque is empty.
E poll()	Retrieves and removes the head of the queue represented by this deque (in other words, the first element of this deque), or returns null if this deque is empty.
E pollFirst()	Retrieves and removes the first element of this deque, or returns null if this deque is empty.
E pollLast()	Retrieves and removes the last element of this deque, or returns null if this deque is empty.
E pop()	Pops an element from the stack represented by this deque.
void push(E e)	Pushes an element onto the stack represented by this deque.
E remove()	Retrieves and removes the head of the queue represented by this deque.
boolean remove(Object o)	Removes a single instance of the specified element from this deque.
E removeFirst()	Retrieves and removes the first element of this deque.
boolean removeFirstOccurrence(Object o)	Removes the first occurrence of the specified element in this deque (when traversing the deque from head to tail).
E removeLast()	Retrieves and removes the last element of this deque.
boolean removeLastOccurrence(Object o)	Removes the last occurrence of the specified element in this deque (when traversing the deque from head to tail).
int size()	Returns the number of elements in this deque.
Spliterator<E> spliterator()	Creates a late-binding and fail-fast Spliterator over the elements in this deque.
Object[] toArray()	Returns an array containing all of the elements in this deque in proper sequence (from first to last element).
<T> T[] toArray(T[] a)	Returns an array containing all of the elements in this deque in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.

HashSet

• The HashSet class implements the Set interface, backed by a hash table which is actually a HashMap instance. No guarantee is made as to the iteration order of the set which means that the class does not guarantee the constant order of elements over time.
• This class permits the null element. The class also offers constant time performance for the basic operations like add, remove, contains, and size assuming the hash function disperses the elements properly among the buckets, which we shall see further in the article.

• A few important features of HashSet are:

  • Implements Set Interface.
  • The underlying data structure for HashSet is Hashtable.
  • As it implements the Set Interface, duplicate values are not allowed.
  • Objects that you insert in HashSet are not guaranteed to be inserted in the same order. Objects are inserted based on their hash code.
  • NULL elements are allowed in HashSet.
  • HashSet also implements Serializable and Cloneable interfaces.

• HashSet contains constructors as below:

Constructor	Description
HashSet()	Constructs a new, empty set; the backing HashMap instance has default initial capacity (16) and load factor (0.75).
HashSet(Collection<? extends E> c)	Constructs a new set containing the elements in the specified collection.
HashSet(int initialCapacity)	Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and default load factor (0.75).
HashSet(int initialCapacity, float loadFactor)	Constructs a new, empty set; the backing HashMap instance has the specified initial capacity and the specified load factor.

• HashSet contains all methods below:

Method	Description
boolean add(E e)	Adds the specified element to this set if it is not already present.
void clear()	Removes all of the elements from this set.
Object clone()	Returns a shallow copy of this HashSet instance: the elements themselves are not cloned.
boolean contains(Object o)	Returns true if this set contains the specified element.
boolean isEmpty()	Returns true if this set contains no elements.
Iterator<E> iterator()	Returns an iterator over the elements in this set.
boolean remove(Object o)	Removes the specified element from this set if it is present.
int size()	Returns the number of elements in this set (its cardinality).
Spliterator<E> spliterator()	Creates a late-binding and fail-fast Spliterator over the elements in this set.

LinkedHashSet

• The LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. When the iteration order is needed to be maintained this class is used. When iterating through a HashSet the order is unpredictable, while a LinkedHashSet lets us iterate through the elements in the order in which they were inserted. When cycling through LinkedHashSet using an iterator, the elements will be returned in the order in which they were inserted.

• The important points about the Java LinkedHashSet class are:

  • Java LinkedHashSet class contains unique elements only like HashSet.
  • Java LinkedHashSet class provides all optional set operations and permits null elements.
  • Java LinkedHashSet class is non-synchronized.
  • Java LinkedHashSet class maintains insertion order.

• LinkedHashSet contains constructors as below:

Constructor	Description
LinkedHashSet()	Constructs a new, empty linked hash set with the default initial capacity (16) and load factor (0.75).
LinkedHashSet(Collection<? extends E> c)	Constructs a new linked hash set with the same elements as the specified collection.
LinkedHashSet(int initialCapacity)	Constructs a new, empty linked hash set with the specified initial capacity and the default load factor (0.75).
LinkedHashSet(int initialCapacity, float loadFactor)	Constructs a new, empty linked hash set with the specified initial capacity and load factor.

• LinkedHashSet contains all methods below:

Method	Description
Spliterator<E> spliterator()	Creates a late-binding and fail-fast Spliterator over the elements in this set.
Methods inherited from class java.util.HashSet	add, clear, clone, contains, isEmpty, iterator, remove, size
Methods inherited from class java.util.AbstractSet	equals, hashCode, removeAll
Methods inherited from class java.util.AbstractCollection	addAll, containsAll, retainAll, toArray, toArray, toString
Methods inherited from class java.lang.Object	finalize, getClass, notify, notifyAll, wait, wait, wait
Methods inherited from interface java.util.Set	add, addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray
Methods inherited from interface java.util.Collection	parallelStream, removeIf, stream
Methods inherited from interface java.lang.Iterable	forEach

TreeSet

• TreeSet is one of the most important implementations of the SortedSet interface in Java that uses a Tree for storage. The ordering of the elements is maintained by a set using their natural ordering whether or not an explicit comparator is provided. This must be consistent with equals if it is to correctly implement the Set interface.

• A few important features of TreeSet are:

  • It stores unique elements
  • It doesn't preserve the insertion order of the elements
  • It sorts the elements in ascending order
  • It's not thread-safe

• TreeSet contains constructors as below:

Constructor	Description
TreeSet()	Constructs a new, empty tree set, sorted according to the natural ordering of its elements.
TreeSet(Collection<? extends E> c)	Constructs a new tree set containing the elements in the specified collection, sorted according to the natural ordering of its elements.
TreeSet(Comparator<? super E> comparator)	Constructs a new, empty tree set, sorted according to the specified comparator.
TreeSet(SortedSet<E> s)	Constructs a new tree set containing the same elements and using the same ordering as the specified sorted set.

• TreeSet contains all methods below:

Method	Description
boolean add(E e)	Adds the specified element to this set if it is not already present.
boolean addAll(Collection<? extends E> c)	Adds all of the elements in the specified collection to this set.
E ceiling(E e)	Returns the least element in this set greater than or equal to the given element, or null if there is no such element.
void clear()	Removes all of the elements from this set.
Object clone()	Returns a shallow copy of this TreeSet instance.
Comparator<? super E> comparator()	Returns the comparator used to order the elements in this set, or null if this set uses the natural ordering of its elements.
boolean contains(Object o)	Returns true if this set contains the specified element.
Iterator<E> descendingIterator()	Returns an iterator over the elements in this set in descending order.
NavigableSet<E> descendingSet()	Returns a reverse order view of the elements contained in this set.
E first()	Returns the first (lowest) element currently in this set.
E floor(E e)	Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
SortedSet<E> headSet(E toElement)	Returns a view of the portion of this set whose elements are strictly less than toElement.
NavigableSet<E> headSet(E toElement, boolean inclusive)	Returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement.
E higher(E e)	Returns the least element in this set strictly greater than the given element, or null if there is no such element.
boolean isEmpty()	Returns true if this set contains no elements.
Iterator<E> iterator()	Returns an iterator over the elements in this set in ascending order.
E last()	Returns the last (highest) element currently in this set.
E lower(E e)	Returns the greatest element in this set strictly less than the given element, or null if there is no such element.
E pollFirst()	Retrieves and removes the first (lowest) element, or returns null if this set is empty.
E pollLast()	Retrieves and removes the last (highest) element, or returns null if this set is empty.
boolean remove(Object o)	Removes the specified element from this set if it is present.
int size()	Returns the number of elements in this set (its cardinality).
Spliterator<E> spliterator()	Creates a late-binding and fail-fast Spliterator over the elements in this set.
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)	Returns a view of the portion of this set whose elements range from fromElement to toElement.
SortedSet<E> subSet(E fromElement, E toElement)	Returns a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive.
SortedSet<E> tailSet(E fromElement)	Returns a view of the portion of this set whose elements are greater than or equal to fromElement.
NavigableSet<E> tailSet(E fromElement, boolean inclusive)	Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement.

EnumMap

• EnumMap is a specialized implementation of the Map interface for enumeration types. It extends AbstractMap and implements the Map interface in Java. It belongs tojava.util package.

• Important features of EnumMap are as follows:

  • EnumMap class is a member of the Java Collections Framework & is not synchronized.
  • EnumMap is an ordered collection and they are maintained in the natural order of their keys(the natural order of keys means the order on which enum constants are declared inside enum type )
  • It’s a high-performance map implementation, much faster than HashMap. All keys of each EnumMap instance must be keys of a single enum type. EnumMap doesn’t allow null key and throws NullPointerException when we attempt to insert the null key.
  • Iterators returned by the collection views are weakly consistent: they will never throw ConcurrentModificationException and they may or may not show the effects of any modifications to the map that occur while the iteration is in progress.
  • EnumMap is internally represented as arrays. This representation is extremely compact and efficient.

• EnumMap contains constructors as below:

Constructor	Description
EnumMap(Class<K> keyType)	Creates an empty enum map with the specified key type.
EnumMap(EnumMap<K,? extends V> m)	Creates an enum map with the same key type as the specified enum map, initially containing the same mappings (if any).
EnumMap(Map<K,? extends V> m)	Creates an enum map initialized from the specified map.

• EnumMap contains all methods below:

Method	Description
void clear()	Removes all mappings from this map.
EnumMap<K,V> clone()	Returns a shallow copy of this enum map.
boolean containsKey(Object key)	Returns true if this map contains a mapping for the specified key.
boolean containsValue(Object value)	Returns true if this map maps one or more keys to the specified value.
Set<Map.Entry<K,V>> entrySet()	Returns a Set view of the mappings contained in this map.
boolean equals(Object o)	Compares the specified object with this map for equality.
V get(Object key)	Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
int hashCode()	Returns the hash code value for this map.
Set<K> keySet()	Returns a Set view of the keys contained in this map.
V put(K key, V value)	Associates the specified value with the specified key in this map.
void putAll(Map<? extends K,? extends V> m)	Copies all of the mappings from the specified map to this map.
V remove(Object key)	Removes the mapping for this key from this map if present.
int size()	Returns the number of key-value mappings in this map.
Collection<V> values()	Returns a Collection view of the values contained in this map.

TreeMap

• Java TreeMap class is a red-black tree based implementation. It provides an efficient means of storing key-value pairs in sorted order.

• The important points about Java TreeMap class are:

  • Java TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
  • Java TreeMap contains only unique elements.
  • Java TreeMap cannot have a null key but can have multiple null values.
  • Java TreeMap is non synchronized.
  • Java TreeMap maintains ascending order.

• TreeMap contains constructors as below:

Constructor	Description
TreeMap()	Constructs a new, empty tree map, using the natural ordering of its keys.
TreeMap(Comparator<? super K> comparator)	Constructs a new, empty tree map, ordered according to the given comparator.
TreeMap(Map<? extends K,? extends V> m)	Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys.
TreeMap(SortedMap<K,? extends V> m)	Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map.

• TreeMap contains all methods below:

Method	Description
Map.Entry<K,V> ceilingEntry(K key)	Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.
K ceilingKey(K key)	Returns the least key greater than or equal to the given key, or null if there is no such key.
void clear()	Removes all of the mappings from this map.
Object clone()	Returns a shallow copy of this TreeMap instance.
Comparator<? super K> comparator()	Returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys.
boolean containsKey(Object key)	Returns true if this map contains a mapping for the specified key.
boolean containsValue(Object value)	Returns true if this map maps one or more keys to the specified value.
NavigableSet<K> descendingKeySet()	Returns a reverse order NavigableSet view of the keys contained in this map.
NavigableMap<K,V> descendingMap()	Returns a reverse order view of the mappings contained in this map.
Set<Map.Entry<K,V>> entrySet()	Returns a Set view of the mappings contained in this map.
Map.Entry<K,V> firstEntry()	Returns a key-value mapping associated with the least key in this map, or null if the map is empty.
K firstKey()	Returns the first (lowest) key currently in this map.
Map.Entry<K,V> floorEntry(K key)	Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
K floorKey(K key)	Returns the greatest key less than or equal to the given key, or null if there is no such key.
void forEach(BiConsumer<? super K,? super V> action)	Performs the given action for each entry in this map until all entries have been processed or the action throws an exception.
V get(Object key)	Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
SortedMap<K,V> headMap(K toKey)	Returns a view of the portion of this map whose keys are strictly less than toKey.
NavigableMap<K,V> headMap(K toKey, boolean inclusive)	Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey.
Map.Entry<K,V> higherEntry(K key)	Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.
K higherKey(K key)	Returns the least key strictly greater than the given key, or null if there is no such key.
Set<K> keySet()	Returns a Set view of the keys contained in this map.
Map.Entry<K,V> lastEntry()	Returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
K lastKey()	Returns the last (highest) key currently in this map.
Map.Entry<K,V> lowerEntry(K key)	Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.
K lowerKey(K key)	Returns the greatest key strictly less than the given key, or null if there is no such key.
NavigableSet<K> navigableKeySet()	Returns a NavigableSet view of the keys contained in this map.
Map.Entry<K,V> pollFirstEntry()	Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.
Map.Entry<K,V> pollLastEntry()	Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
V put(K key, V value)	Associates the specified value with the specified key in this map.
void putAll(Map<? extends K,? extends V> map)	Copies all of the mappings from the specified map to this map.
V remove(Object key)	Removes the mapping for this key from this TreeMap if present.
V replace(K key, V value)	Replaces the entry for the specified key only if it is currently mapped to some value.
boolean replace(K key, V oldValue, V newValue)	Replaces the entry for the specified key only if currently mapped to the specified value.
void replaceAll(BiFunction<? super K,? super V,? extends V> function)	Replaces each entry's value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.
int size()	Returns the number of key-value mappings in this map.
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)	Returns a view of the portion of this map whose keys range from fromKey to toKey.
SortedMap<K,V> subMap(K fromKey, K toKey)	Returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.
SortedMap<K,V> tailMap(K fromKey)	Returns a view of the portion of this map whose keys are greater than or equal to fromKey.
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive)	Returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey.
Collection<V> values()	Returns a Collection view of the values contained in this map.

HashTable

• The Hashtable class implements a hash table, which maps keys to values. Any non-null object can be used as a key or as a value. To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the hashCode method and the equals method.

• Features of Hashtable

  • It is similar to HashMap, but is synchronized.
  • Hashtable stores key/value pair in hash table.
  • In Hashtable we specify an object that is used as a key, and the value we want to associate to that key. The key is then hashed, and the resulting hash code is used as the index at which the value is stored within the table.
  • The initial default capacity of Hashtable class is 11 whereas loadFactor is 0.75.
  • HashMap doesn’t provide any Enumeration, while Hashtable provides not fail-fast Enumeration.

• Hashtable contains constructors as below:

Constructor	Description
Hashtable()	Constructs a new, empty hashtable with a default initial capacity (11) and load factor (0.75).
Hashtable(int initialCapacity)	Constructs a new, empty hashtable with the specified initial capacity and default load factor (0.75).
Hashtable(int initialCapacity, float loadFactor)	Constructs a new, empty hashtable with the specified initial capacity and the specified load factor.
Hashtable(Map<? extends K,? extends V> t)	Constructs a new hashtable with the same mappings as the given Map.

• HashTable contains all methods below:

Method	Description
void clear()	Clears this hashtable so that it contains no keys.
Object clone()	Creates a shallow copy of this hashtable.
V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)	Attempts to compute a mapping for the specified key and its current mapped value (or null if there is no current mapping).
V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction)	If the specified key is not already associated with a value (or is mapped to null), attempts to compute its value using the given mapping function and enters it into this map unless null.
V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)	If the value for the specified key is present and non-null, attempts to compute a new mapping given the key and its current mapped value.
boolean contains(Object value)	Tests if some key maps into the specified value in this hashtable.
boolean containsKey(Object key)	Tests if the specified object is a key in this hashtable.
boolean containsValue(Object value)	Returns true if this hashtable maps one or more keys to this value.
Enumeration<V> elements()	Returns an enumeration of the values in this hashtable.
Set<Map.Entry<K,V>> entrySet()	Returns a Set view of the mappings contained in this map.
boolean equals(Object o)	Compares the specified Object with this Map for equality, as per the definition in the Map interface.
void forEach(BiConsumer<? super K,? super V> action)	Performs the given action for each entry in this map until all entries have been processed or the action throws an exception.
V get(Object key)	Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
V getOrDefault(Object key, V defaultValue)	Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.
int hashCode()	Returns the hash code value for this Map as per the definition in the Map interface.
boolean isEmpty()	Tests if this hashtable maps no keys to values.
Enumeration<K> keys()	Returns an enumeration of the keys in this hashtable.
Set<K> keySet()	Returns a Set view of the keys contained in this map.
V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction)	If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value.
V put(K key, V value)	Maps the specified key to the specified value in this hashtable.
void putAll(Map<? extends K,? extends V> t)	Copies all of the mappings from the specified map to this hashtable.
V putIfAbsent(K key, V value)	If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value.
protected void rehash()	Increases the capacity of and internally reorganizes this hashtable, in order to accommodate and access its entries more efficiently.
V remove(Object key)	Removes the key (and its corresponding value) from this hashtable.
boolean remove(Object key, Object value)	Removes the entry for the specified key only if it is currently mapped to the specified value.
V replace(K key, V value)	Replaces the entry for the specified key only if it is currently mapped to some value.
boolean replace(K key, V oldValue, V newValue)	Replaces the entry for the specified key only if currently mapped to the specified value.
void replaceAll(BiFunction<? super K,? super V,? extends V> function)	Replaces each entry's value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.
int size()	Returns the number of keys in this hashtable.
String toString()	Returns a string representation of this Hashtable object in the form of a set of entries, enclosed in braces and separated by the ASCII characters ", " (comma and space).
Collection<V> values()	Returns a Collection view of the values contained in this map.

HashMap

• Java HashMap class implements the Map interface which allows us to store key and value pair, where keys should be unique. If you try to insert the duplicate key, it will replace the element of the corresponding key. It is easy to perform operations using the key index like update, delete, etc. HashMap class is found in the java.util package.

• HashMap in Java is like the legacy Hashtable class, but it is not synchronized. It allows us to store the null elements as well, but there should be only one null key. Since Java 5, it is denoted as HashMap, where K stands for key and V for value. It inherits the AbstractMap class and implements the Map interface.

• Features of HashMap

  • Java HashMap contains values based on the key.
  • Java HashMap contains only unique keys.
  • Java HashMap may have one null key and multiple null values.
  • Java HashMap is non synchronized.
  • Java HashMap maintains no order.
  • The initial default capacity of Java HashMap class is 16 with a load factor of 0.75.

• HashMap contains constructors as below:

Constructor	Description
HashMap()	Constructs an empty HashMap with the default initial capacity (16) and the default load factor (0.75).
HashMap(int initialCapacity)	Constructs an empty HashMap with the specified initial capacity and the default load factor (0.75).
HashMap(int initialCapacity, float loadFactor)	Constructs an empty HashMap with the specified initial capacity and load factor.
HashMap(Map<? extends K,? extends V> m)	Constructs a new HashMap with the same mappings as the specified Map.

• HashMap contains all methods below:

Method	Description
void clear()	Removes all of the mappings from this map.
Object clone()	Returns a shallow copy of this HashMap instance: the keys and values themselves are not cloned.
V compute(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)	Attempts to compute a mapping for the specified key and its current mapped value (or null if there is no current mapping).
V computeIfAbsent(K key, Function<? super K,? extends V> mappingFunction)	If the specified key is not already associated with a value (or is mapped to null), attempts to compute its value using the given mapping function and enters it into this map unless null.
V computeIfPresent(K key, BiFunction<? super K,? super V,? extends V> remappingFunction)	If the value for the specified key is present and non-null, attempts to compute a new mapping given the key and its current mapped value.
boolean containsKey(Object key)	Returns true if this map contains a mapping for the specified key.
boolean containsValue(Object value)	Returns true if this map maps one or more keys to the specified value.
Set<Map.Entry<K,V>> entrySet()	Returns a Set view of the mappings contained in this map.
void forEach(BiConsumer<? super K,? super V> action)	Performs the given action for each entry in this map until all entries have been processed or the action throws an exception.
V get(Object key)	Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
V getOrDefault(Object key, V defaultValue)	Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.
boolean isEmpty()	Returns true if this map contains no key-value mappings.
Set<K> keySet()	Returns a Set view of the keys contained in this map.
V merge(K key, V value, BiFunction<? super V,? super V,? extends V> remappingFunction)	If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value.
V put(K key, V value)	Associates the specified value with the specified key in this map.
void putAll(Map<? extends K,? extends V> m)	Copies all of the mappings from the specified map to this map.
V putIfAbsent(K key, V value)	If the specified key is not already associated with a value (or is mapped to null) associates it with the given value and returns null, else returns the current value.
V remove(Object key)	Removes the mapping for the specified key from this map if present.
boolean remove(Object key, Object value)	Removes the entry for the specified key only if it is currently mapped to the specified value.
V replace(K key, V value)	Replaces the entry for the specified key only if it is currently mapped to some value.
boolean replace(K key, V oldValue, V newValue)	Replaces the entry for the specified key only if currently mapped to the specified value.
void replaceAll(BiFunction<? super K,? super V,? extends V> function)	Replaces each entry's value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.
int size()	Returns the number of key-value mappings in this map.
Collection<V> values()	Returns a Collection view of the values contained in this map.

LinkedHashMap

• The LinkedHashMap class is very similar to HashMap in most aspects. However, the linked hash map is based on both hash table and linked list to enhance the functionality of hash map.
• It maintains a doubly-linked list running through all its entries in addition to an underlying array of default size 16.
• To maintain the order of elements, the linked hashmap modifies the Map.Entry class of HashMap by adding pointers to the next and previous entries:

• Important Features of a LinkedHashMap are listed as follows:

  • A LinkedHashMap contains values based on the key. It implements the Map interface and extends the HashMap class.
  • It contains only unique elements.
  • It may have one null key and multiple null values.
  • It is non-synchronized.
  • It is the same as HashMap with an additional feature that it maintains insertion order. For example, when we run the code with a HashMap, we get a different order of elements.

• LinkedHashMap contains constructors as below:

Constructor	Description
LinkedHashMap()	Constructs an empty insertion-ordered LinkedHashMap instance with the default initial capacity (16) and load factor (0.75).
LinkedHashMap(int initialCapacity)	Constructs an empty insertion-ordered LinkedHashMap instance with the specified initial capacity and a default load factor (0.75).
LinkedHashMap(int initialCapacity, float loadFactor)	Constructs an empty insertion-ordered LinkedHashMap instance with the specified initial capacity and load factor.
LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)	Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode.
LinkedHashMap(Map<? extends K,? extends V> m)	Constructs an insertion-ordered LinkedHashMap instance with the same mappings as the specified map.

• LinkedHashMap contains all methods below:

Method	Description
void clear()	Removes all of the mappings from this map.
boolean containsValue(Object value)	Returns true if this map maps one or more keys to the specified value.
Set<Map.Entry<K,V>> entrySet()	Returns a Set view of the mappings contained in this map.
void forEach(BiConsumer<? super K,? super V> action)	Performs the given action for each entry in this map until all entries have been processed or the action throws an exception.
V get(Object key)	Returns the value to which the specified key is mapped, or null if this map contains no mapping for the key.
V getOrDefault(Object key, V defaultValue)	Returns the value to which the specified key is mapped, or defaultValue if this map contains no mapping for the key.
Set<K> keySet()	Returns a Set view of the keys contained in this map.
protected boolean removeEldestEntry(Map.Entry<K,V> eldest)	Returns true if this map should remove its eldest entry.
void replaceAll(BiFunction<? super K,? super V,? extends V> function)	Replaces each entry's value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.
Collection<V> values()	Returns a Collection view of the values contained in this map.

Components Comparison

HashMap And HashTable

• HashMap and Hashtable both are used to store data in key and value form. Both are using hashing technique to store unique keys.

HashMap	Hashtable
HashMap allows one null key and multiple null values	Hashtable does not allow any null key or value
HashMap is non synchronized. It is not thread-safe and can not be shared between many threads without proper synchronization code	Hashtable is synchronized. It is thread-safe and can be shared with many threads
HashMap is fast	Hashtable is slow

• We can make the HashMap as synchronized by calling this code:

Map m = Collections.synchronizedMap(hashMap);

ArrayList And LinkedList

• ArrayList and LinkedList both implemented list interface and maintains insertion order. Both are non synchronized classes.

ArrayList	LinkedList
ArrayList internally uses a dynamic array to store the elements	LinkedList internally uses a doubly linked list to store the elemnents
Manipulation with ArrayList is slow because it internally uses an array. If any element is removed from the array, all the bits are shifted in memory	Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory
An ArrayList can act as a list only because it implements List only	LinkedList class can act as a list and queue both because it implements List and Dequeue interfaces
ArrayList is better for storing and accessing data	LinkedList is better for manipulation data

See Also

• Java Core Introduction

References

• GeeksForGeeks
• JavaTPoint