Java Collection

• Any group of individual objects which are represented as a single unit is known as the collection of the objects.
• The Collection in Java is a framework that provides an architecture to store and manipulate the group of objects.
• The Collection interface (java.util.Collection) and Map interface (java.util.Map) are the two main “root” interfaces of Java collection classes.
• Java Collections can achieve all the operations that you perform on a data such as searching, sorting, insertion, manipulation, and deletion.

Java Collection Hierarchy

The utility package, (java.util) contains all the classes and interfaces that are required by the collection framework. The collection framework contains an interface named as an iterable interface which provides the iterator to iterate through all the collections. This interface is extended by the main collection interface which acts as a root for the collection framework. All the collections extend this collection interface thereby extending the properties of the iterator and the methods of this 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

Iterator iterator();

List Interface

• This interface is dedicated to the data of the list type in which we can store all the ordered collection of the objects.
• This also allows duplicate data to be present in it.
• It is implemented by various classes like ArrayList, Vector, Stack, etc.

ArrayList

• ArrayList provides us with dynamic arrays in Java. Though, it may be slower than standard arrays but can be helpful in programs where lots of manipulation in the array is needed. The size of an ArrayList is increased automatically if the collection grows or shrinks if the objects are removed from the collection.
• It is like an array, but there is no size limit.
• Java ArrayList allows us to randomly access the list. ArrayList can not be used for primitive types, like int, char, etc. We will need a wrapper class for such cases.
• The ArrayList class maintains the insertion order and is non-synchronized.
• The elements stored in the ArrayList class can be randomly accessed.

LinkedList

• LinkedList 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.
• It uses a doubly linked list internally to store the elements.
• It can store the duplicate elements.
• It maintains the insertion order and is not synchronized.
• In LinkedList, the manipulation is fast because no shifting is required.
• It can be used as a list, stack or queue.

Vector

• Vector uses a dynamic array to store the data elements.
• It may be slower than standard arrays but can be helpful in programs where lots of manipulation in the array is needed.
• The primary difference between a vector and an ArrayList is that a Vector is synchronized and an ArrayList is non-synchronized.
• It is synchronized and contains many methods that are not the part of Collection framework.

Stack

• It implements the last-in-first-out data structure.
• The stack is the subclass of Vector. The stack contains all of the methods of Vector class and also provides its methods like boolean push(), boolean peek(), boolean push(object o), which defines its properties.

Queue Interface

A queue interface maintains the FIFO(First In First Out) order similar to a real-world queue line. This interface is dedicated to storing all the elements where the order of the elements matter. There are various classes like PriorityQueue, Deque, ArrayDeque, etc.

Priority Queue

• 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 and this class is used in these cases.
• The PriorityQueue is based on the priority heap.
• The elements of the priority queue are ordered according to the natural ordering, or by a Comparator provided at queue construction time, depending on which constructor is used.
• PriorityQueue doesn’t allow null values to be stored in the queue.
• The elements in PriorityQueue must be of Comparable type. String and Wrapper classes are Comparable by default.
• To add user-defined objects in PriorityQueue, you need to implement Comparable interface.

Deque Interface

Deque, also known as a double-ended queue, is a data structure where we can add and remove the elements from both the ends of the queue.

• This interface extends the queue interface.
• The class which implements this interface is ArrayDeque.

ArrayDeque

• The ArrayDeque class provides the facility of using deque and resizable-array. This is a special kind of array that grows and allows users to add or remove an element from both sides of the queue.
• Array deques have no capacity restrictions and they grow as necessary to support usage.
• ArrayDeque is faster than ArrayList and Stack.
• Unlike Queue, we can add or remove elements from both sides.
• Null elements are not allowed in the ArrayDeque.
• ArrayDeque is not thread safe, in the absence of external synchronization.

Set Interface

• A set is an unordered collection of objects in which duplicate values cannot be stored.
• This collection is used when we wish to avoid the duplication of the objects and wish to store only the unique objects.
• This set interface is implemented by various classes like HashSet, TreeSet, LinkedHashSet, etc.

HashSet

• The HashSet class is an inherent implementation of the hash table data structure.
• HashSet stores the elements by using a mechanism called hashing.
• HashSet contains unique elements only.
• HashSet allows null value.
• HashSet class is non synchronized.
• HashSet doesn’t maintain the insertion order. Here, elements are inserted on the basis of their hashcode.
• HashSet is the best approach for search operations.
• The initial default capacity of HashSet is 16, and the load factor is 0.75.

LinkedHashSet

• LinkedHashSet uses a doubly linked list to store the data and retains the ordering of the elements.
• Like HashSet, It also contains unique elements only.
• It maintains the insertion order.
• It permits null elements.
• LinkedHashSet class is non synchronized.

SortedSet Interface

• This interface is very similar to the set interface. The only difference is that this interface has extra methods that maintain the ordering of the elements.
• The sorted set interface extends the set interface and is used to handle the data which needs to be sorted.
• The class which implements this interface is TreeSet.

TreeSet

• TreeSet class contains unique elements only like HashSet.
• TreeSet class doesn’t allow null element.
• The TreeSet class 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.
• It can also be ordered by a Comparator provided at set creation time, depending on which constructor is used.
• the access and retrieval time of TreeSet is quite fast.
• The elements in TreeSet stored in ascending order.
• TreeSet class is non synchronized.

Map Interface

A map is a data structure which 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 a 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.
There are two interfaces for implementing Map in java: Map and SortedMap, and three classes: HashMap, LinkedHashMap, and TreeMap. The hierarchy of Java Map is given below:

HashMap

HashMap provides the basic implementation of the Map interface of Java. It stores the data in (Key, Value) pairs. To access a value in a HashMap, we must know its key. HashMap uses a technique called Hashing. Hashing is a technique of converting a large String to small String that represents the same String so that the indexing and search operations are faster. HashSet also uses HashMap internally.

• 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 implementation
Working of HashMap in Java

• It stores the data in the pair of Key and Value.
• HashMap contains an array of the nodes, and the node is represented as a class.
• It uses an array and LinkedList data structure internally for storing Key and Value.

LinkedHashMap

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

TreeMap

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

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

HashTable

Java Hashtable class inherits Dictionary class and implements the Map interface.

• A Hashtable is an array of a list. Each list is known as a bucket. The position of the bucket is identified by calling the hashcode() method. A Hashtable contains values based on the key.
• Hashtable class contains unique elements.
• Hashtable class doesn’t allow null key or value.
• Hashtable class is synchronized.
• The initial default capacity of Hashtable class is 11 whereas loadFactor is 0.75.

EnumSet

EnumSet class is the specialized Set implementation for use with enum types. It inherits AbstractSet class and implements the Set interface.

EnumMap

EnumMap class is the specialized Map implementation for enum keys. It inherits Enum and AbstractMap classes.

Collections class

This class consists exclusively of static methods that operate on or return collections. It contains polymorphic algorithms that operate on collections, “wrappers”, which return a new collection backed by a specified collection, and a few other odds and ends.
The methods of this class all throw a NullPointerException if the collections or class objects provided to them are null.

Sorting in collection

1. String objects Collections.sort()
2. Wrapper class objects Collections.sort()
3. User-defined class objects
   Collections.sort() with user-defined class implements comparable interface (compareTo() method)

Comaprable

• Java Comparable interface is used to order the objects of the user-defined class.
• This interface is found in java.lang package and contains only one method named compareTo(Object).
• It provides a single sorting sequence only, i.e., you can sort the elements on the basis of single data member only. For example, it may be rollno, name, age or anything else.

compareTo(Object obj) method

public int compareTo(Object obj): It is used to compare the current object with the specified object. It returns

• positive integer, if the current object is greater than the specified object.
• negative integer, if the current object is less than the specified object.
• zero, if the current object is equal to the specified object.

Comparator

• Java Comparator interface is used to order the objects of a user-defined class.
• This interface is found in java.util package and contains 2 methods compare(Object obj1,Object obj2) and equals(Object element).
• It provides multiple sorting sequences, i.e., you can sort the elements on the basis of any data member, for example, rollno, name, age or anything else.

Comparator Implementation

• Non-generic Old Style
• Generic style

Java 8 Comparator Interface

Java 8 has more comparator methods

Properties class

• The properties object contains key and value pair both as a string.
• The java.util.Properties class is the subclass of Hashtable.
• It can be used to get property value based on the property key. The Properties class provides methods to get data from the properties file and store data into the properties file. Moreover, it can be used to get the properties of a system.
• Recompilation is not required if the information is changed from a properties file: If any information is changed from the properties file, you don’t need to recompile the java class. It is used to store information which is to be changed frequently.

A Little Deep In Queues

The queue (a FIFO list)

Implementation of a queue

• A queue (of bounded size) can be efficiently implemented in an array.
• A queue can be efficiently implemented using any linked list that supports deletion in the front and insertion at the end in constant time. The first (last) element of the queue is at the front (end) of the linked list.

The stack (a LIFO list)

Implementation of a stack

• A stack (of bounded size) can be efficiently implemented using an array b and an int variable n: The n elements of the stack are in b[0..n-1], with b[0] being the bottom element and b[n-1] being the top element.
• A stack can be efficiently implemented using a linked list. The first element is the top of the stack and the last element is the bottom. It’s easy to push (prepend) an element and pop (remove) the first element in constant time.

The deque

The word deque, usually pronounced deck, is short for double-ended queue. A deque is a list that supports insertion and removal at both ends. Thus, a deque can be used as a queue or as a stack.

Stacks, queues, and deques in the Java Collection framework

• Java has interface Deque. It is implemented by classes ArrayDeque (which implements a list in an expandable array) and LinkedList, so these two classes can be used for a queue and for a stack.

• Both ArrayDeque and LinkedList also implement interface Queue, so you can use this interface to restrict operations to queue operations. For example, create a LinkedList and assign it to a Queue variable.

    Queue<E> q= new LinkedList<>();  
  

Thereafter, use only q for the LinkedList and operations are restricted to queue operations.

• Java also has a class Stack, which implements a stack in an expandable array. However, the Java API would rather you use an ArrayDeque. The problem is that there is no suitable way to restrict the operations of an Array-Deque to stack operations, so we prefer to use class Stack.

Some Implementations

• LinkedList: Although mainly known to be a List implementation, this class also implements the Queue interface. This implementation works by linking its elements together and going through that chain when iterating or searching for elements.
• ArrayDeque: An implementation of both Queue and Deque. It’s backed up by an array, which can be increased when the number of elements increase over its current capacity.
• DelayQueue: Can only contain elements which implement the Delayed interface - elements that become active after a certain time. The DelayQueue will only deliver elements whose delays have expired.
• PriorityQueue: Orders its elements according to their natural order or a Comparator (if provided). This means it doesn’t work using the FIFO principle, but rather returns the element with the highest priority (defined by how they compare to each other).

Non-generic vs Generic

• Java collection framework was non-generic before JDK 1.5. Since 1.5, it is generic.

• Java new generic collection allows you to have only one type of object in a collection. Now it is type safe so typecasting is not required at runtime.

• In a generic collection, the type is specified in angular braces.

• If trying to add another type of object into generic collection, it gives compile time error.

    ArrayList list=new ArrayList();//creating old non-generic arraylist  
    ArrayList<String> list=new ArrayList<String>();//creating new generic arraylist  
  

Ways to iterate the elements of the collection in Java

• By Iterator interface.
• By for-each loop.
• By ListIterator interface.
• By for loop.
• By forEach() method.
• By forEachRemaining() method.

Comparison

Array vs ArrayList

ArrayList vs LinkedList

ArrayList vs Vector

List vs Set

A list can contain duplicate elements whereas Set contains unique elements only.

HashMap vs LinkedHashMap vs TreeMap

• A Map doesn’t allow duplicate keys, but you can have duplicate values.
• HashMap and LinkedHashMap allow null keys and values, but TreeMap doesn’t allow any null key or value.
• A Map can’t be traversed, so you need to convert it into Set using keySet() or entrySet() method.

HashMap vs Hashtable

Collections Class vs Collection Framework

Comparable vs Comparator

Links

Collections in Java
Java Collections: Queue and Deque Interfaces
Java ArrayList