Java Collections Framework

Dr. Surendra Kr. Keshari

Associate Professor
Department of Information Technology
KIET Group of Institutions

1
What is Collection in Java
• A Collection represents a single unit of objects, i.e., a group.
• In Java, a separate framework named the “Collection Framework” has been defined in JDK 1.2
which holds all the Java Collection Classes and Interface in it.

What is a Framework in Java?

• A framework is a set of classes and interfaces which provide a ready-made architecture.
• In order to implement a new feature or a class, there is no need to define a framework.
• However, an optimal object-oriented design always includes a framework with a collection of
classes such that all the classes perform the same kind of task.

2
Collection Framework in Java
• The Collection in Java is a framework that provides an architecture to store and manipulate the
group of objects.
• Java Collections can achieve all the operations that you perform on a data such as searching,
sorting, insertion, manipulation, and deletion.
• Java Collection means a single unit of objects.
• Java Collection framework provides many interfaces (Set, List, Queue, Deque) and classes
(ArrayList, Vector, LinkedList, PriorityQueue, HashSet, LinkedHashSet, TreeSet).

3
Collection Framework in Java
The Collections Framework was designed to meet several goals.
• First, the framework had to be high-performance. The implementations for the fundamental collections
(dynamic arrays, linked lists, trees, and hash tables) are highly efficient. You seldom, if ever, need to code
one of these “data engines” manually.
• Second, the framework had to allow different types of collections to work in a
similar manner and with a high degree of interoperability.
• Third, extending and/or adapting a collection had to be easy. Toward this end, the entire Collections
Framework is built upon a set of standard interfaces. Several standard implementations (such as LinkedList,
HashSet, and TreeSet) of these interfaces are provided that you may use as-is.
• Finally, mechanisms were added that allow the integration of standard arrays
into the Collections Framework.
• The Collection interface (java.util.Collection) and Map interface (java.util.Map)
are the two main “root” interfaces of Java collection classes.

4
Need for a Separate Collection Framework in Java

• Before the Collection Framework(or before JDK 1.2) was introduced, the standard methods for
grouping Java objects (or collections) were Arrays or Vectors, or Hashtables.
• All of these collections had no common interface. Therefore, though the main aim of all the
collections is the same, the implementation of all these collections was defined independently and
had no correlation among them.
• And also, it is very difficult for the users to remember all the different methods, syntax,
and constructors present in every collection class.

5
Advantages of the Java Collection Framework

1. Consistent API: The API has a basic set of interfaces like Collection, Set, List, or Map, all the classes
(ArrayList, LinkedList, Vector, etc) that implement these interfaces have some common set of methods.
2. Reduces programming effort: A programmer doesn’t have to worry about the design of the Collection
but rather he can focus on its best use in his program. Therefore, the basic concept of Object-oriented
programming (i.e.) abstraction has been successfully implemented.
3. Increases program speed and quality: Increases performance by providing high-performance
implementations of useful data structures and algorithms because in this case, the programmer need not
think of the best implementation of a specific data structure. He can simply use the best implementation
to drastically boost the performance of his algorithm/program.

6
Hierarchy of the Collection Framework in Java
• 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 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.
• The collection framework contains multiple interfaces where every interface is used to store a
specific type of data.

7
java.util classes

8
java.util interfaces

9
10
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.
• The Iterable interface was introduced in JDK 1.5. It belongs to java.lang package.
• An iterable interface allows an object to be the target of enhanced for loop(for-each loop).
• This interface contains only one abstract method which is the iterator.
Iterator<T> iterator() :It returns the iterator over the elements of type T.

Ways of Iterating
• Using enhanced for loop(for-each loop)
• Using Iterable forEach loop
• Using Iterator<T> interface

11
Iterate an Iterable using enhanced for loop
// Java Program to demonstrate iterate an iterable using for loop
import java.io.*;
import java.util.*;
class IterateUsingEnhancedForLoop {
public static void main (String[] args) {
List<String> list = new ArrayList<String>(); // create a list
list.add("Hello");
list.add("I am");
list.add("Good");
list.add("Student");
// Iterate through the list
for( String element : list ){
System.out.println( element );
} }
} 12
Iterate an Iterable using forEach loop
The forEach() method takes the Lambda Expression as a parameter. This Lambda Expression is called for
each element of the collection.
// Java Program to demonstrate iterate an Iterable using forEach method
import java.io.*;
import java.util.*;
class IterateUsingforEach {
public static void main(String[] args) {
List<String> list = new ArrayList<>(); // create a list
list.add("Hello");
list.add("I am");
list.add("Good");
list.add("Student");
// Iterate through the list
list.forEach( (element) -> { System.out.println(element); });
}
}

13
Iterate an Iterable using Iterator

// Java Program to demonstrate iterate an Iterable using an

Iterator
import java.io.*; We can iterate the elements of Java
import java.util.*; Iterable by obtaining the Iterator from it
class IterateUsingIterator { using the iterator() method.
public static void main(String[] args) { • hasNext(): It returns false if we have
List<String> list = new ArrayList<>(); reached the end of the collection,
list.add("Hello"); otherwise returns true.
list.add("I am");
• next(): Returns the next element in
list.add("Good");
a collection.
list.add("Student");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
String element = iterator.next();
System.out.println(element);
}
}}
14
15
Collection Interface
• The Collection interface is a member of the Java Collections Framework.
• It is a part of java.util package.
• It is one of the root interfaces of the Collection Hierarchy.
• The Collection interface is not directly implemented by any class.
• However, it is implemented indirectly via its subtypes or subinterfaces like List, Queue, and Set.
• This interface contains all the basic methods which every collection has like adding the data into the collection,
removing the data, clearing the data, etc.
• If a collection implementation doesn’t implement a particular operation, it should define the corresponding
method to throw UnsupportedOperationException.

16
1. List Interface in Java
List: This is a child interface of the collection 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.

Syntax of Java List

This type of safelist can be defined as:
List<Obj> list = new ArrayList<Obj> ();
Note: Obj is the type of the object to be stored in List

List interface is implemented by the classes ArrayList, LinkedList, Vector, and Stack.
To instantiate the List interface, we must use :
List <data-type> list1= new ArrayList();
List <data-type> list2 = new LinkedList();
List <data-type> list3 = new Vector();
List <data-type> list4 = new Stack();

17
Complexity of List Interface in Java
Operation Time Complexity Space Complexity

Adding Element in List

O(1) O(1)
Interface

Remove Element from List

O(N) O(N)
Interface

Replace Element in List

O(N) O(N)
Interface

Traversing List Interface O(N) O(N)

18
Java List vs Set
• Both the List interface and the Set interface inherits the Collection interface. However,
there exists some differences between them.

List Set

The List is an ordered sequence. The Set is an unordered sequence.

List allows duplicate elements Set doesn’t allow duplicate elements.

Elements by their position can be accessed. Position access to elements is not allowed.

Multiple null elements can be stored. The null element can store only once.

List implementations are ArrayList, LinkedList, Set implementations are HashSet,

Vector, Stack LinkedHashSet.

19
ArrayList
• The ArrayList class implements the List interface. It uses a dynamic array to store the duplicate element of different data
types. The ArrayList class maintains the insertion order and is non-synchronized. The elements stored in the ArrayList
class can be randomly accessed.
ArrayList<String> list=new ArrayList<String>(); //Creating String arraylist

ArrayList<Integer> list=new ArrayList<Integer>(); //Creating Integer arraylist

ArrayList<Double> list=new ArrayList<Double>(); //Creating Double arraylist
ArrayList<Character> list=new ArrayList<Character>(); //Creating Character arraylist
• The size of an ArrayList is increased automatically if the collection grows or shrinks if the objects are removed from
the collection. 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.
• Default Memory size of ArrayList is 10 memory location. If 11th elements is added, then size automatically increased
by (n+n/2+1) where size=n (initially 10). Then 16 memory location will be added. The Old ArrayList will be copied in
new ArrayList. (Note: This Size format is applicable for all data structure of Collection Interface)

20
Creating ArrayList Example
//Example-1 //Example-2
import java.util.*; import java.util.*;
class TestJavaCollection1{ class TestJavaCollection1{
public static void main(String args[]){ public static void main(String args[]){
ArrayList<String> list=new ArrayList<Integer>list=new
ArrayList<String>();//Creating arraylist
ArrayList<Integer>();
list.add("Ravi");//Adding object in arraylist
list.add(4);//Adding object in arraylist
list.add("Vijay");
list.add(8);
list.add("Ravi");
list.add(12);
list.add("Ajay");
list.add(16);
//Traversing list through Iterator
//Traversing list through Iterator
Iterator itr=list.iterator();
Iterator itr=list.iterator();
while(itr.hasNext()){
while(itr.hasNext()){
System.out.println(itr.next());
} } } System.out.println(itr.next());
21
} } }
Adding Elements:
• add(Object): This method is used to add an element at the end of the ArrayList.
• add(int index, Object): This method is used to add an element at a specific index in the ArrayList.

import java.util.*;
class Student {
public static void main(String args[])
{
ArrayList<String> al = new ArrayList<>();
al.add("Anil");
al.add("Vivek");
System.out.println(al);
// Here we are mentioning the index at which it is to be added
al.add(0, "Pankaj");
System.out.println(al);
}
}

22
Changing Elements
After adding the elements, if we wish to change the element, it can be done using the set() method. Since an
ArrayList is indexed, the element which we wish to change is referenced by the index of the element.
Therefore, this method takes an index and the updated element which needs to be inserted at that index.

import java.util.*;
class Student {
public static void main(String args[])
{
ArrayList<String> al = new ArrayList<>();
al.add("Anil");
al.add("Vivek");
System.out.println("Initial ArrayList " + al);
// Setting element at 1st index
al.set(1,"Gold");
// Printing the updated Arraylist
System.out.println("Updated ArrayList " + al);
}
}

23
Removing Elements
• remove(Object): This method is used to simply remove an object from the ArrayList. If there are
multiple such objects, then the first occurrence of the object is removed.
• remove(int index): Since an ArrayList is indexed, this method takes an integer value which simply
removes the element present at that specific index in the ArrayList. After removing the element, all the
elements are moved to the left to fill the space and the indices of the objects are updated.
import java.util.*;
class Student {
public static void main(String args[]) {
ArrayList<String> al = new ArrayList<>();
al.add("Anil");
al.add("Vivek");
al.add("Friend");
System.out.println(al);
al.add(0, "Pankaj");
System.out.println(al);
al.remove(1);
System.out.println(al);
al.remove("Friend");
System.out.println(al);
24
}}
get() method to get the element at a specific index

import java.io.*;
import java.util.*;
class Students {
public static void main (String[] args) {
ArrayList<Integer> list = new ArrayList();
list.add(9);
list.add(5);
list.add(6);
System.out.println(list);
// get method
Integer n= list.get(1);
System.out.println("at indext 1 number is:"+n);
}
}

25
ArrayList Sort

import java.io.*;
import java.util.*;
class Numbers {
public static void main(String[] args)
{
ArrayList<Integer> list = new ArrayList();
list.add(2);
list.add(4);
list.add(3);
list.add(1);
System.out.println("Before sorting list:");
System.out.println(list);
Collections.sort(list);
System.out.println("after sorting list:");
System.out.println(list);
}
}
26
Size of Elements

import java.io.*;
import java.util.*;
class Numbers {
public static void main(String[] args)
{
ArrayList<Integer> list = new ArrayList();
list.add(2);
list.add(4);
list.add(3);
list.add(1);
int b = list.size();
System.out.println("The size is :" + b);

}
}

27
Important Features of ArrayList in Java
• ArrayList is a dynamic array and we do not have to specify the size while creating it, the size of the array automatically
increases when we dynamically add and remove items.
• Creates a bigger-sized memory on heap memory.
• Copies the current memory elements to the new memory.
• It can store the duplicate elements.
• The new item is added now as there is bigger memory available now.
• Delete the old memory.
• ArrayList inherits AbstractList class and implements the List interface.
• ArrayList is initialized by size. However, the size is increased automatically if the collection grows or shrinks if
the objects are removed from the collection.
• Java ArrayList allows us to randomly access the list.
• ArrayList can not be used for primitive types, like int, char, etc. We need a wrapper class for such cases.
• ArrayList in Java can be seen as a vector in C++.
• ArrayList is not Synchronized. Its equivalent synchronized class in Java is Vector.
28
Advantages of Java ArrayList
• Dynamic size: ArrayList can dynamically grow and shrink in size, making it easy to add or remove
elements as needed.
• Easy to use: ArrayList is simple to use, making it a popular choice for many Java developers.
• Fast access: ArrayList provides fast access to elements, as it is implemented as an array under the hood.
• Ordered collection: ArrayList preserves the order of elements, allowing you to access elements in the
order they were added.
• Supports null values: ArrayList can store null values, making it useful in cases where the absence of a
value needs to be represented.
Disadvantages of Java ArrayList
• Slower than arrays: ArrayList is slower than arrays for certain operations, such as inserting elements in
the middle of the list.
• Increased memory usage: ArrayList requires more memory than arrays, as it needs to maintain its
dynamic size and handle resizing.
• Not thread-safe: ArrayList is not thread-safe, meaning that multiple threads may access and modify the
list concurrently, leading to potential race conditions and data corruption.
• Performance degradation: ArrayList’s performance may degrade as the number of elements in the list
increases, especially for operations such as searching for elements or inserting elements in the middle of
the list. 29
Complexity of Java ArrayList
Operation Time Complexity Space Complexity

Inserting Element in ArrayList O(1) O(N)

Removing Element from ArrayList O(N) O(1)

Traversing Elements in ArrayList O(N) O(N)

Replacing Elements in ArrayList O(1) O(1)

30
31
LinkedList
• LinkedList implements the Collection interface.
• It uses a doubly linked list internally to store the elements. It can store the duplicate elements.
• In LinkedList, the manipulation is fast because no shifting is required.
• It inherits the AbstractList class and implements List and Deque interfaces.
• It maintains the insertion order and is not synchronized.
• Java LinkedList class can be used as a list, stack or queue.
Performing Various Operations on LinkedList
• Adding elements
• Updating elements
• Removing elements
• Iterating over elements
• To Array();
• Size();
• remove First();
• remove last();
32
LinkedList

import java.util.*;
public class TestJavaCollection2{
public static void main(String args[]){
LinkedList<String> al=new LinkedList<String>();
al.add("Ravi");
al.add("Vijay");
al.add("Ravi");
al.add("Ajay");
Iterator<String> itr=al.iterator();
while(itr.hasNext()){
System.out.println(itr.next());
}
//System.out.println(al);
}
}

33
Demonstrates how to use a LinkedList in Java:
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
// Create a new linked list
LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
// Add an element to the beginning of the linked list
linkedList.addFirst(0);
// Add an element to the end of the linked list
linkedList.addLast(4);
// System.out.println(linkedList); // Print the elements of the linked list
// linkedList.remove(3); // Remove element at index 3
// linkedList.removeFirst();
// linkedList.removeLast();
for (int i : linkedList) {
System.out.println(i); }
System.out.println("Size of Linked List is="+linkedList.size());
34
} }
Linked list to To Array by using toArray();

import java.util.*;
public class Students {
public static void main(String[] args)
{
LinkedList<Integer> list= new LinkedList<Integer>();
list.add(123);
list.add(12);
list.add(11);
list.add(1134);
System.out.println("LinkedList: "+ list);
Object[] array = list.toArray();
System.out.print("After converted LinkedList to Array: ");
for(Object element : array)
System.out.print(element+" ");
}
}
35
Advantages of using LinkedList in Java:

• Dynamic size: As with Vector, the size of a LinkedList can grow or shrink dynamically, so you don’t
have to worry about setting an initial size.
• Efficient Insertions and Deletions: LinkedList is an efficient data structure for inserting or deleting
elements in the middle of the list because you only need to change the links between elements, rather
than shifting all elements after the insertion or deletion point.
• Flexible Iteration: With a linked list, you can efficiently iterate through the list in either direction,
since each element has a reference to both its predecessor and successor elements.

Disadvantages of using LinkedList in Java:

• Performance: LinkedList has a slower performance than ArrayList when it comes to accessing
individual elements. This is because you need to traverse the list to reach the desired element, whereas
with ArrayList, you can simply access the desired element using an index.
• Memory overhead: LinkedList requires more memory than ArrayList because each element requires
additional memory for the links to its predecessor and successor elements.

36
37
Vector
• A vector 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. This is identical to ArrayList in terms of implementation.
However, the primary difference between a vector and an ArrayList is that a
Vector is synchronized and an ArrayList is non-synchronized.
• It was added in the original release of Java (Java 1.0) and provides a number
of methods for manipulating the elements of a vector, including adding,
inserting, and removing elements.
• The Vector class implements a growable array of objects. Vectors fall in
legacy classes, but now it is fully compatible with collections. It is found
in java.util package and implement the List interface. 38
Vector Example

import java.util.*;
public class TestJavaCollection3{
public static void main(String args[]){
Vector<String> v=new Vector<String>();
v.add("Ayush");
v.add("Amit");
v.add("Ashish");
v.add("Garima");
Iterator<String> itr=v.iterator();
while(itr.hasNext()){
System.out.println(itr.next());
}
}
}
39
Java program to demonstrate the working of Vector
import java.io.*; import java.util.*;
class ExampleVector {
public static void main(String[] args) {
Vector<Integer> v = new Vector<Integer>();
for (int i = 1; i <= 5; i++)
v.add(i); System.out.println(v); //Printing the vector
v.addElement(100); // Or Add elements to the vector
System.out.println(v);
v.remove(3); // Remove element at index 3
System.out.println(v); // Printing the Vector after deletion
v.removeElementAt(2); // Or Remove element at index 2
System.out.println(v); // Printing the Vector after deletion
for (int i = 0; i < v.size(); i++) // Printing elements one by one
System.out.print(v.get(i) + " "); System.out.println();
v.set(1,99); //updting vector at index 1
System.out.println(v);
v.insertElementAt(0,1); // Insert an element at index 1
System.out.println(v); } } 40
Advantages of using Vector in Java:
• Synchronisation: As mentioned before, Vector is synchronised, making it safe to use in a multi-threaded
environment.
• Dynamic Size: The size of a Vector can grow or shrink dynamically as elements are added or removed, so you don’t
have to worry about setting an initial size that will accommodate all elements.
• Legacy support: Vector has been part of Java since its inception and is still supported, so it’s a good option if you
need to work with older Java code that uses Vector.
Disadvantages of using Vector in Java:
• Performance: The synchronisation in Vector can lead to slower performance compared to other collection classes,
such as ArrayList.
• Legacy Code: While Vector is still supported, newer Java code is often written using the more modern collection
classes, so it may be harder to find examples and support for Vector.
• Unnecessary overhead: If you don’t need the synchronization features of Vector, using it will add unnecessary
overhead to your code.

41
42
Stack
• The stack is the subclass of Vector. It implements the last-in-first-out data structure, i.e., Stack.
• 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.
• In addition to the basic push and pop operations, the class provides three more functions empty, search,
and peek. The class can also be referred to as the subclass of Vector.

43
Stack

import java.util.Stack;
public class LearnStack
{
public static void main(String[] args)
{
Stack<String> animals= new Stack<>();

animals.push("Lion");
animals.push("Dog");
animals.push("Horse");
animals.push("Cat");
System.out.println("Stack: " + animals);
System.out.println(animals.peek());
animals.pop();
System.out.println("Stack: " + animals);
System.out.println(animals.peek());
}
} 44
// Java code for stack implementation // Displaying element on the top of the stack
static void stack_peek(Stack<Integer> stack) {
import java.io.*; Integer element = (Integer) stack.peek();
import java.util.*; System.out.println("Element on stack top: " +
class Test element);
{ }
// Pushing element on the top of the stack // Searching element in the stack
static void stack_push(Stack<Integer> stack) static void stack_search(Stack<Integer> stack, int element)
{ {Integer pos = (Integer) stack.search(element);
for(int i = 0; i < 5; i++) if(pos == -1)
{ System.out.println("Element not
stack.push(i); found");
} else
} System.out.println("Element is found
// Popping element from the top of the stack at position: " + pos);
static void stack_pop(Stack<Integer> stack) }
{ public static void main (String[] args) {
System.out.println("Pop Operation:"); Stack<Integer> stack = new Stack<Integer>();

for(int i = 0; i < 5; i++) stack_push(stack);

{ stack_pop(stack);
Integer y = (Integer) stack_push(stack);
stack.pop(); stack_peek(stack);
System.out.println(y); stack_search(stack, 2);
} stack_search(stack, 6);
} }} 45
• The isEmpty() method is used to check if the stack is empty before attempting to pop an element.
• This code creates a stack of integers and pushes 4 integers onto the stack in the order 1 -> 2 -> 3 -> 4.
• We then pop elements from the stack one by one using the pop() method, which removes and returns the
top element of the stack.
• Since the stack follows a last-in-first-out (LIFO) order, the elements are popped in the reverse order of
insertion, resulting in the output shown above.
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
// Create a new stack
Stack<Integer> stack = new Stack<>();
// Push elements onto the stack
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
// Pop elements from the stack
while(!stack.isEmpty()) {
System.out.println(stack.pop());
}
46
System.out.println(stack); }}
47
2. Queue Interface in Java

• Queue interface maintains the FIFO(First In First Out) order.

• It is an ordered list of objects with its use limited to inserting elements at the end of the list and deleting elements
from the start of the list.
• For example, whenever we try to book a ticket, the tickets are sold on a first come first serve basis. Therefore, the
person whose request arrives first into the queue gets the ticket.
• There are various classes like PriorityQueue, ArrayDeque, etc.
• Queue interface can be instantiated as:
Queue<String> q1 = new PriorityQueue();
Queue<String> q2 = new ArrayDeque();

48
Queue Interface in Java

The Queue interface provides several methods for adding, removing, and inspecting elements in the queue.
Here are some of the most commonly used methods:
• add(element): Adds an element to the rear of the queue. If the queue is full, it throws an exception.
• offer(element): Adds an element to the rear of the queue. If the queue is full, it returns false.
• remove(): Removes and returns the element at the front of the queue. If the queue is empty, it throws an
exception.
• poll(): Removes and returns the element at the front of the queue. If the queue is empty, it returns null.
• element(): Returns the element at the front of the queue without removing it. If the queue is empty, it
throws an exception.
• peek(): Returns the element at the front of the queue without removing it. If the queue is empty, it returns
null.

49
PriorityQueue

• A PriorityQueue is used when the objects are supposed to be processed based on 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.

50
PriorityQueue
Java program to demonstrate the working of priority queue in Java (PriorityQueue)

import java.util.*; System.out.println("iterating the queue elements:");

public class TestJavaCollection{ Iterator itr=queue.iterator();
public static void main(String args[]){ while(itr.hasNext()){
PriorityQueue<String> queue=new PriorityQueue<String>( System.out.println(itr.next());
); }
queue.add("Amit Sharma"); queue.remove();
queue.add("Vijay Raj"); queue.poll();
queue.add("JaiShankar"); System.out.println("after removing two elements:");
queue.add("Raj"); Iterator<String> itr2=queue.iterator();
System.out.println("head:"+queue.element()); while(itr2.hasNext()){
System.out.println("head:"+queue.peek()); System.out.println(itr2.next());
} }}

51
Java program to demonstrate the working of priority queue in Java (LinkedList)
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<String> queue = new LinkedList<>();
queue.add("apple");
queue.add("banana");
queue.add("cherry");
System.out.println("Queue: " + queue);
// remove the element at the front of the queue
String front = queue.remove();
System.out.println("Removed element: " + front);
System.out.println("Queue after removal: " + queue);
queue.add("date"); // add another element to the queue
// peek at the element at the front of the queue
String peeked = queue.peek();
System.out.println("Peeked element: " + peeked);
System.out.println("Queue after peek: " + queue);
}
} 52
Java program to demonstrate the creation of queue object using the LinkedList class

import java.util.*;
class Sample {
public static void main(String args[])
{ // Creating empty LinkedList
Queue<Integer> ll
= new LinkedList<Integer>();
ll.add(10);
ll.add(20);
ll.add(15);
System.out.println("Elemest in Queue are:"+ll);
// Printing the top element of the LinkedList
System.out.println("Top Element in Queue is:"+ll.peek());
// Printing the top element and removing it
// from the LinkedList container
ll.poll();
System.out.println("Elemest in Queue After Deletion Top Element:"+ll);
// Printing the top element again
System.out.println("Now Top Element in Queue is:"+ll.peek());
}
}
53
Advantages of using the Queue interface in Java:
• Order preservation: The Queue interface provides a way to store and retrieve elements in a specific order, following
the first-in, first-out (FIFO) principle.
• Flexibility: The Queue interface is a subtype of the Collection interface, which means that it can be used with many
different data structures and algorithms, depending on the requirements of the application.
• Thread–safety: Some implementations of the Queue interface, such as the
java.util.concurrent.ConcurrentLinkedQueue class, are thread-safe, which means that they can be accessed by multiple
threads simultaneously without causing conflicts.
• Performance: The Queue interface provides efficient implementations for adding, removing, and inspecting elements,
making it a useful tool for managing collections of elements in performance-critical applications.
Disadvantages of using the Queue interface in Java:
• Limited functionality: The Queue interface is designed specifically for managing collections of elements in a specific
order, which means that it may not be suitable for more complex data structures or algorithms.
• Size restrictions: Some implementations of the Queue interface, such as the ArrayDeque class, have a fixed size,
which means that they cannot grow beyond a certain number of elements.
• Memory usage: Depending on the implementation, the Queue interface may require more memory than other data
structures, especially if it needs to store additional information about the order of the elements.
• Complexity: The Queue interface can be difficult to use and understand for novice programmers, especially if they are
not familiar with the principles of data structures and algorithms.
54
Deque
• This is a very slight variation of the queue data structure. 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.
• Since this class implements the deque, we can instantiate a deque object with this class.
For example,
Deque<T> ad = new ArrayDeque<> ();
Where T is the type of the object.
The class which implements the deque interface is ArrayDeque.

ArrayDeque
• ArrayDeque class which is implemented in the collection framework provides us with a way to apply
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.

55
Java program to demonstrate the ArrayDeque class in Java
import java.util.*;
public class ArrayDequeDemo {
public static void main(String[] args) {
ArrayDeque<Integer> de_que= new ArrayDeque<Integer>(10);
de_que.add(10);
de_que.add(20);
de_que.add(30);
de_que.add(40);
de_que.add(50);
System.out.println(de_que);
de_que.clear(); // clear() method
// addFirst() method to insert the elements at the head
de_que.addFirst(564);
de_que.addFirst(291);
de_que.addFirst(222);
// addLast() method to insert the elements at the tail
de_que.addLast(24);
de_que.addLast(14);
de_que.addLast(333);
System.out.println(de_que); } } 56
Prioritize use of Deque over Stack
• The Stack class in Java is a legacy class and inherits from Vector in Java.
• It is a thread-safe class and hence involves overhead when we do not need thread safety.
• It is recommended to use ArrayDeque for stack implementation as it is more efficient in a single-threaded
environment.
• One more reason to use Deque over Stack is Deque has the ability to use streams convert to list with keeping
LIFO concept applied while Stack does not.
// A Java Program to show implementation of Stack using ArrayDeque
import java.util.*;
class Sample {
public static void main (String[] args) {
Deque<Character> stack = new ArrayDeque<Character>();
stack.push('A');
stack.push('B');
System.out.println(stack.peek());
System.out.println(stack.pop());
}
}

57
58
3. Set Interface in Java

• Set: A set is an unordered collection of objects in which duplicate values cannot be stored.
• The set interface is present in java.util package and extends the Collection interface.
• It is an interface that implements the mathematical set.
• This set interface is implemented by various classes like HashSet, TreeSet, LinkedHashSet, etc.
• Since all the subclasses implement the set, we can instantiate a set object with any of these classes.
For example,
Set<T> hs = new HashSet<> ();
Set<T> lhs = new LinkedHashSet<> ();
Set<T> ts = new TreeSet<> ();
Where T is the type of the object.

59
The following are the classes that implement the Set interface
i). HashSet
• The HashSet class is an inherent implementation of the hash table data structure.
• The objects that we insert into the HashSet do not guarantee to be inserted in the same order.
• The objects are inserted based on their hashcode.
• This class also allows the insertion of NULL elements.
// Java program to demonstrate the working of a HashSet
import java.util.*;
public class HashSetDemo {
public static void main(String args[]) {
HashSet<String> hs = new HashSet<String>(); // Creating HashSet and adding elements
hs.add("One");
hs.add("Two");
hs.add("Three");
hs.add("Four");
hs.add("Five");
Iterator<String> itr = hs.iterator(); // Traversing elements
while (itr.hasNext()) {
System.out.println(itr.next());
60
} } }
Java program to demonstrate the working of a HashSet by performing Operations like: add, remove, contains

import java.util.*;
public class HashSetDemo {
public static void main(String args[]) {
// Creating HashSet and adding elements
HashSet<String> hs = new HashSet<String>();
hs.add("One"); hs.add("Two"); hs.add("Three"); hs.add("Four"); hs.add("Five");
// Traversing elements
Iterator<String> itr = hs.iterator();
while (itr.hasNext()) {
System.out.println(itr.next()); }
// Declaring a string
String check = "One";
// Check if the above string exists in the SortedSet or not using contains() method
System.out.println("Contains " + check + " “ + hs.contains(check));
hs.remove("Two");
System.out.println(hs);
hs.removeAll(hs);
System.out.println(hs);
} } 61
ii). LinkedHashSet
• A LinkedHashSet is very similar to a HashSet. The difference is that this uses a doubly linked list to store the
data and retains the ordering of the 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.
// Java program to demonstrate the working of a LinkedHashSet
import java.util.*;
public class LinkedHashSetDemo {
public static void main(String args[]) {
// Creating LinkedHashSet and adding elements
LinkedHashSet<String> lhs = new LinkedHashSet<String>();
lhs.add("One");
lhs.add("Two");
lhs.add("Three");
lhs.add("Four");
lhs.add("Five");
Iterator<String> itr = lhs.iterator();
while (itr.hasNext()) {
System.out.println(itr.next());
62
} } }
Operations on the Set Interface

The set interface allows the users to perform the basic mathematical operation on the set. Let’s take two arrays
to understand these basic operations.
Let set1 = [1, 3, 2, 4, 8, 9, 0] and set2 = [1, 3, 7, 5, 4, 0, 7, 5]. Then the possible operations on the sets are:
1. Intersection: This operation returns all the common elements from the given two sets. For the above two
sets, the intersection would be: Intersection = [0, 1, 3, 4]
2. Union: This operation adds all the elements in one set with the other. For the above two sets, the union
would be: Union = [0, 1, 2, 3, 4, 5, 7, 8, 9]
3. Difference: This operation removes all the values present in one set from the other set. For the above two
sets, the difference would be: Difference = [2, 8, 9]

63
// Java Program Demonstrating Operations on the Set such as Union, Intersection and Difference operations Using HashSet.
import java.util.*;
public class SetExample {
public static void main(String args[]) {
// Creating an object of Set class and Declaring object of Integer type
Set<Integer> a = new HashSet<Integer>();
a.addAll(Arrays.asList(new Integer[] { 1, 3, 2, 4, 8, 9, 0 })); // Adding all elements to List
// Again declaring object of Set class with reference to HashSet
Set<Integer> b = new HashSet<Integer>();
b.addAll(Arrays.asList(new Integer[] { 1, 3, 7, 5, 4, 0, 7, 5 })); Output
Set<Integer> union = new HashSet<Integer>(a); // To find union Union of the two Set
union.addAll(b);
[0, 1, 2, 3, 4, 5, 7, 8, 9]
System.out.print("Union of the two Set");
System.out.println(union); Intersection of the two Set[0, 1, 3, 4]
Set<Integer> intersection = new HashSet<Integer>(a); // To find intersection
Difference of the two Set[2, 8, 9]
intersection.retainAll(b);
System.out.print("Intersection of the two Set");
System.out.println(intersection);
Set<Integer> difference = new HashSet<Integer>(a); // To find the symmetric difference
difference.removeAll(b);
System.out.print("Difference of the two Set");
System.out.println(difference);
} }
64
// Java Program Demonstrating Operations on the Set such as Union, Intersection and Difference operations Using
LinkedHashSet.
import java.util.*;
public class SetExample {
public static void main(String args[]) {
// Creating an object of Set class and Declaring object of Integer type
Set<Integer> a = new LinkedHashSet<Integer>();
a.addAll(Arrays.asList(new Integer[] { 1, 3, 2, 4, 8, 9, 0 })); // Adding all elements to List
// Again declaring object of Set class with reference to LinkedHashSet Output
Set<Integer> b = new LinkedHashSet<Integer>(); Union of the two Set
b.addAll(Arrays.asList(new Integer[] { 1, 3, 7, 5, 4, 0, 7, 5 })); [1, 3, 2, 4, 8, 9, 0, 7, 5]
Set<Integer> union = new LinkedHashSet<Integer>(a); // To find union Intersection of the two Set
union.addAll(b); [1, 3, 4, 0]
System.out.print("Union of the two Set"); Difference of the two Set
System.out.println(union); [2, 8, 9]
Set<Integer> intersection = new LinkedHashSet<Integer>(a); // To find intersection
intersection.retainAll(b);
System.out.print("Intersection of the two Set");
System.out.println(intersection);
Set<Integer> difference = new LinkedHashSet<Integer>(a); // To find the symmetric difference
difference.removeAll(b);
System.out.print("Difference of the two Set");
System.out.println(difference);
}} 65
66
Sorted Set 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.
• Since this class implements the SortedSet, we can instantiate a SortedSet object with this class. For example,
SortedSet<T> ts = new TreeSet<> ();
Where T is the type of the object.
The class which implements
TreeSetthe sorted set interface is TreeSet.
• TreeSet class which is implemented in the collections framework and implementation of the SortedSet
Interface and SortedSet extends Set Interface.
• It behaves like a simple set with the exception that it stores elements in a sorted format.
• TreeSet uses a tree data structure for storage.
• Objects are stored in sorted, ascending order. But we can iterate in descending order using the method
TreeSet.descendingIterator().
Note: All the elements of a SortedSet must implement the Comparable interface (or be accepted by the specified
Comparator) and all such elements must be mutually comparable. Mutually Comparable simply means that two
objects accept each other as the argument to their compareTo method.
67
Java program to demonstrate the Sorted Set
import java.util.*;
class SortedSetExample{
public static void main(String[] args) {
SortedSet<String> ts = new TreeSet<String>();
// Adding elements into the TreeSet using add()
ts.add("India");
ts.add("Australia");
ts.add("South Africa");
ts.add("India"); // Adding the duplicate element
System.out.println(“Displaying theTreeSet:”+(ts));
System.out.println("First Value " + ts.first());
System.out.println("Last Value " + ts.last());
ts.remove("Australia"); // Removing items from TreeSet using remove()
System.out.println("Set after removing "+ "Australia:" + ts);
// Iterating over Tree set items
System.out.println("Iterating over set:");
Iterator<String> i = ts.iterator();
while (i.hasNext())
System.out.println(i.next());
} } 68
Features of a TreeSet

• TreeSet implements the SortedSet interface. So, duplicate values are not allowed.
• Objects in a TreeSet are stored in a sorted and ascending order.
• TreeSet does not preserve the insertion order of elements but elements are sorted by keys.
• If we are depending on the default natural sorting order, the objects that are being inserted into the
tree should be homogeneous and comparable.
• TreeSet does not allow the insertion of heterogeneous objects. It will throw a classCastException at
Runtime if we try to add heterogeneous objects.
• The TreeSet can only accept generic types which are comparable. For example, the StringBuffer class
implements the Comparable interface

69
Map Interface

70
Map Interface
• A map is a data structure that supports the key-value pair for mapping the data.
• This interface doesn’t support duplicate keys because the same key cannot have multiple mappings,
however, it allows duplicate values in different keys.
• In Java, Map Interface is present in java.util package represents a mapping between a key and a value.
• Java Map interface is not a subtype of the Collection interface.
• Therefore it behaves a bit differently from the rest of the collection types.
• A map contains values on the basis of key, i.e. key and value pair.
• Each key and value pair is known as an entry. A Map contains unique keys.
• 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.
• 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.
• The frequently used implementation of a Map interface is a HashMap.
For example:
Map<T> hm = new HashMap<> ();
Map<T> tm = new TreeMap<> ();
Where T is the type of the object. 71
Hierarchy of Java Map

72
1. HashMap
• HashMap provides the basic implementation of the Map interface of Java.
• It stores the data in (Key, Value) pairs. ).
• One object is used as a key (index) to another object (value).
• If you try to insert the duplicate key in HashMap, it will replace the element of the corresponding key.
• 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 a small String that represents the same String so
that the indexing and search operations are faster.
• HashSet also uses HashMap internally.
• Java HashMap is similar to HashTable, but it is unsynchronized.
• It allows to store the null keys as well, but there should be only one null key object and there can be any
number of null values.
• This class makes no guarantees as to the order of the map.
• To use this class and its methods, you need to import java.util.HashMap package or its superclass.

73
Java program to demonstrate the working of a HashMap
import java.util.*;
public class HashMapDemo {
public static void main(String args[])
{
HashMap<Integer, String> hm = new HashMap<Integer, String>();
hm.put(1, "Hello");
hm.put(2, "New");
hm.put(3, "Old");
System.out.println("HashMap:"+hm);
// Finding the value for a key
System.out.println("Value for 2 is " + hm.get(2));

// Traversing through the HashMap

for (Map.Entry<Integer, String> e : hm.entrySet())
System.out.println(e.getKey() + " “ + e.getValue());
//removing element
//hm.remove(2);
//System.out.println("HashMap:"+hm);
}
74
}
Java program to illustrate HashMap class of java.util package
import java.util.HashMap;
public class HashMapDemo {
public static void main(String[] args)
{ // Create an empty hash map by declaring object of string and integer type
HashMap<String, Integer> map = new HashMap<>();
// Adding elements to the Map using standard put() method
map.put("vishal", 10);
map.put("sachin", 30);
map.put("vaibhav", 20);
System.out.println("Size of map is:- "+ map.size()); // Print size and content of the Map
System.out.println(map); // Printing elements in object of Map
// Checking if a key is present and if present, print value by passing random element
if (map.containsKey("vishal")) {
// Mapping
Integer a = map.get("vishal");
// Printing value for the corresponding key
System.out.println("value for key“ + " \"vishal\" is:- " + a);
//map.remove("vishal");
//System.out.println("HashMap:"+map);
} } } 75
2. LinkedHashMap
• LinkedHashMap is just like HashMap with the additional feature of maintaining an order of elements
inserted into it.
• HashMap provided the advantage of quick insertion, search, and deletion but it never maintained the
track and order of insertion which the LinkedHashMap provides where the elements can be accessed
in their insertion order.

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.

76
Java Program to Illustrate the LinkedHashmap Class
import java.util.*;
public class GFG {
public static void main(String[] args) {
// Creating an empty LinkedHashMap
Map<String, Integer> map = new LinkedHashMap<>();
// Inserting pair entries in above Map using put() method
map.put("vishal", 10);
map.put("sachin", 30);
map.put("vaibhav", 20);
// Iterating over Map
for (Map.Entry<String, Integer> e : map.entrySet())
System.out.println(e.getKey() + " "+ e.getValue());
System.out.println("printing Map List"+map);
//Updating the value
map.put("sachin", 35);
System.out.println("Updated Map List"+map);
//removing the value
map.remove("vishal");
System.out.println("After removing Map List"+map);
} } 77
3. TreeMap in Java

• The TreeMap in Java is used to implement Map interface along with the AbstractMap Class.
• The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map
creation time, depending on which constructor is used.
• This proves to be an efficient way of sorting and storing the key-value pairs.
• The storing order maintained by the treemap must be consistent with equals just like any other sorted map,
irrespective of the explicit comparators.
• The treemap implementation is not synchronized in the sense that if a map is accessed by multiple threads,
concurrently and at least one of the threads modifies the map structurally, it must be synchronized
externally.
• The TreeMap in Java is a concrete implementation of the java.util.SortedMap interface.
• It provides an ordered collection of key-value pairs, where the keys are ordered based on their natural order
or a custom Comparator passed to the constructor.
• A TreeMap is implemented using a Red-Black tree, which is a type of self-balancing binary search tree.
• This provides efficient performance for common operations such as adding, removing, and retrieving
elements, with an average time complexity of O(log n).

78
Java Program to Illustrate the TreeMap
import java.util.Map;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
Map<String, Integer> treeMap = new TreeMap<>();
// Adding elements to the tree map
treeMap.put("A", 1);
treeMap.put("C", 3);
treeMap.put("B", 2);
System.out.println("TreeMap:"+treeMap);
// Getting values from the tree map
int valueA = treeMap.get("A");
System.out.println("Value of A: " + valueA);
// Removing elements from the tree map
treeMap.remove("B");
System.out.println("After Remove B TreeMap:"+treeMap);
// Iterating over the elements of the tree map
for (String key : treeMap.keySet()) {
System.out.println("Key: " + key + ", Value: " + treeMap.get(key));
} }} 79
Java Hashtable class
• Java Hashtable class implements a hashtable, which maps keys to values. It 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.
• Java Hashtable class contains unique elements.
• Java Hashtable class doesn't allow null key or value.
• Java Hashtable class is synchronized.
• To successfully store and retrieve objects from a hashtable, the objects used as keys must implement the
hashCode method and the equals method.
• The java.util.Hashtable class is a class in Java that provides a key-value data structure, similar to the Map
interface.
• It was part of the original Java Collections framework and was introduced in Java 1.0.
• However, the Hashtable class has since been considered obsolete and its use is generally discouraged.
• This is because it was designed prior to the introduction of the Collections framework and does not implement
the Map interface, which makes it difficult to use in conjunction with other parts of the framework.
• In addition, the Hashtable class is synchronized, which can result in slower performance compared to other
implementations of the Map interface.
• In general, it’s recommended to use the Map interface or one of its implementations (such as HashMap or
ConcurrentHashMap) instead of the Hashtable class. 80
Java Program to Demonstrate Hashtable
//import java.util.Enumeration;
//import java.util.Hashtable;
import java.util.*;
public class Main {
public static void main(String[] args) {
Hashtable<String, Integer> hashtable = new Hashtable<>();
hashtable.put("A", 1); // Adding elements to the hashtable
hashtable.put("B", 2);
hashtable.put("C", 3);
System.out.println("Hashtable:"+hashtable);
int valueA = hashtable.get("A"); // Getting values from the hashtable
System.out.println("Value of A: " + valueA);
// Removing elements from the hashtable
hashtable.remove("B");
System.out.println("After remove B Hashtable:"+hashtable);
// Enumerating the elements of the hashtable
Enumeration<String> keys = hashtable.keys();
while (keys.hasMoreElements()) {
String key = keys.nextElement();
System.out.println("Key: " + key + ", Value: " + hashtable.get(key));
81
}}}
Sorting in Collection

82
Sorting in Collection
We can sort the elements of:
1. String objects
2. Wrapper class objects
3. User-defined class objects
Collections class
• Collections class provides static methods for sorting the elements of a collection.
• If collection elements are of Set or Map, we can use TreeSet or TreeMap.
• However, we cannot sort the elements of List.
• Collections class provides methods for sorting the elements of List type elements also.
Method of Collections class for sorting List elements
• public void sort(List list): It is a method used to sort the elements of List. List elements must be of the
Comparable type.
• Note: String class and Wrapper classes implement the Comparable interface by default. So if you store the
objects of string or wrapper classes in a list, set or map, it will be Comparable by default.
83
Example to sort string objects

import java.util.*;
class TestSort1{ Output
public static void main(String args[]){ Mukesh
Saurav
ArrayList<String> al=new ArrayList<String>(); Tahir
al.add("Viru"); Viru
al.add("Saurav");
al.add("Mukesh");
al.add("Tahir");

Collections.sort(al);
Iterator itr=al.iterator();
while(itr.hasNext()){
System.out.println(itr.next());
}
}
}

84
Example to sort string objects in reverse order

import java.util.*;
class TestSort2{ Output
public static void main(String args[]){ Viru
Tahir
ArrayList<String> al=new ArrayList<String>(); Saurav
al.add("Viru"); Mukesh
al.add("Saurav");
al.add("Mukesh");
al.add("Tahir");

Collections.sort(al,Collections.reverseOrder());
Iterator i=al.iterator();
while(i.hasNext())
{
System.out.println(i.next());
}
}
}
85
Example to sort Wrapper class objects

import java.util.*;
class TestSort3{
public static void main(String args[]){

ArrayList al=new ArrayList();

al.add(Integer.valueOf(201));
al.add(Integer.valueOf(101));
al.add(230); //internally will be converted into objects as
Integer.valueOf(230)

Collections.sort(al);

Iterator itr=al.iterator();
while(itr.hasNext()){
System.out.println(itr.next());
}
}
}
86
Comparable Interface
and
Comparator Interface

87
Java Comparable interface
• The Comparable interface is used to compare an object of the same class with an instance of that class.
• It provides ordering of data for objects of the user-defined class.
• The class has to implement the java.lang.Comparable interface to compare its instance and contains only one
method named compareTo(Object).
• It Override the compareTo method in the Pair class.
• It Create an array of Pairs and populate the array.
• It Use the Arrays.sort() function to sort the array.
• 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.
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.
• It returns negative integer, if the current object is less than the specified object.
• It returns zero, if the current object is equal to the specified object.
88
Java Comparable Example-1
Given an array of Pairs consisting of two fields of type string and integer. you have to sort the array in ascending
Lexicographical order and if two strings are the same sort it based on their integer value.
Sample I/O:
Input: { {"abc", 3}, {"a", 4}, {"bc", 5}, {"a", 2} }
Output: { {"a", 2}, {"a", 4}, {"abc", 3}, {"bc", 5} }

Input: { {"efg", 1}, {"gfg", 1}, {"cba", 1}, {"zaa", 1} }

Output: { {"cba", 1}, {"efg", 1}, {"gfg", 1}, {"zaa", 1} }

89
Java Comparable Example-1
import java.io.*; public class ExampleCompare1 {
import java.util.*; public static void main(String[] args) {
class Pair implements Comparable<Pair> { int n = 4;
String x; Pair arr[] = new Pair[n];
int y; arr[0] = new Pair("abc", 3);
public Pair(String x, int y) { arr[1] = new Pair("a", 4);
this.x = x; arr[2] = new Pair("bc", 5);
this.y = y; } arr[3] = new Pair("a", 2);
public String toString() { System.out.println("Before Sorting:");
return "(" + x + "," + y + ")"; } for (int i = 0; i < arr.length; i++) {
@Override public int compareTo(Pair a) { System.out.println(arr[i]); }
// if the string are not equal Arrays.sort(arr); // Sorting the array
if (this.x.compareTo(a.x) != 0) { System.out.println("After Sorting:");
return this.x.compareTo(a.x); } print(arr); }
else {// we compare int values if the strings public static void print(Pair[] arr) {
are equal for (int i = 0; i < arr.length; i++) {
return this.y - a.y; } System.out.println(arr[i]); }
} } } } 90
Java Comparable Example-2

Given an array of Pairs consisting of two strings with first and last names. you have to sort the array in
ascending Lexicographical order of the first name and if two strings are the same sort it based on their last
name.
Sample I/O:
Input: { {"raj", "kashup"}, {"rahul", "singh"}, {"reshmi", "dubey"}, {"rahul", "jetli"} }
Output: { {"rahul", "jetli"}, {"rahul", "singh"}, {"raj", "kashup"}, {"reshmi", "dubey"} }

Input: { {"abc", "last"}, {"pklz", "yelp"}, {"rpng", "note"}, {"ppza", "xyz"} }

Output: { {"abc", "last"}, {"pklz", "yelp"}, {"ppza", "xyz"}, {"rpng", "note"} }

91
Java Comparable Example-2
import java.io.*; public class ExampleCompare2 {
import java.util.*; public static void main(String[] args) {
class Pair implements Comparable<Pair> { int n = 4;
String firstName; Pair arr[] = new Pair[n];
String lastName; arr[0] = new Pair("raj", "kashup");
public Pair(String x, String y) { arr[1] = new Pair("rahul", "singh");
arr[2] = new Pair("reshmi", "dubey");
this.firstName = x;
arr[3] = new Pair("rahul", "jetli");
this.lastName = y; }
System.out.println("Before Sorting:");
public String toString() {
for (int i = 0; i < arr.length; i++) {
return "( " + firstName + " , " + lastName + " )"; }
System.out.println(arr[i]); }
@Override public int compareTo(Pair a) {
System.out.println("After Sorting:");
// if the string are not equal
Arrays.sort(arr);
if (this.firstName.compareTo(a.firstName) != 0) {
print(arr); }
return this.firstName.compareTo(a.firstName); } public static void print(Pair[] arr) {
else { // we compare lastName if firstNames are equal for (int i = 0; i < arr.length; i++) {
return this.lastName.compareTo(a.lastName); } System.out.println(arr[i]);
} } }
} } 92
Java Comparator interface

• A comparator interface is used to order the objects of user-defined classes.

• A comparator object is capable of comparing two objects of the same 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.
• public void sort(List list, ComparatorClass c): is used to sort the elements of List by the given
Comparator.
• To sort a given List, ComparatorClass must implement a Comparator interface.

How do the sort() method of Collections class work?

Internally the Sort method does call Compare method of the classes it is sorting. To compare two elements, it asks
“Which is greater?” Compare method returns -1, 0, or 1 to say if it is less than, equal, or greater to the other. It
uses this result to then determine if they should be swapped for their sort.

93
Java Comparator Example-1
import java.io.*; (Java Program to Demonstrate Working of Comparator Interface)
import java.lang.*;
import java.util.*;
class Student { // Class 1 to represent a Student
int rollno;
String name, address;
public Student(int rollno, String name, String address) {
this.rollno = rollno;
this.name = name;
this.address = address; }
public String toString() {
return this.rollno + " " + this.name + " "+ this.address; } }
// Class 2 Helper class implementing Comparator interface
class Sortbyroll implements Comparator<Student> {
public int compare(Student a, Student b) {
return a.rollno - b.rollno; } }
// Class 3 Helper class implementing Comparator interface
class Sortbyname implements Comparator<Student> {
public int compare(Student a, Student b) {
return a.name.compareTo(b.name); } } 94
// Class 4 Main class
public class Main {
public static void main(String[] args) {
ArrayList<Student> ar = new ArrayList<Student>();//an empty ArrayList of Student type
ar.add(new Student(111, "Mayank", "london"));
ar.add(new Student(131, "Anshul", "nyc"));
ar.add(new Student(121, "Solanki", "jaipur"));
ar.add(new Student(101, "Aggarwal", "Hongkong"));
System.out.println("Unsorted");
for (int i = 0; i < ar.size(); i++)
System.out.println(ar.get(i));
Collections.sort(ar, new Sortbyroll()); // Sorting student entries by roll number
System.out.println("\nSorted by rollno");
for (int i = 0; i < ar.size(); i++)
System.out.println(ar.get(i));
Collections.sort(ar, new Sortbyname()); // Sorting student entries by name
System.out.println("\nSorted by name");
for (int i = 0; i < ar.size(); i++)
System.out.println(ar.get(i));
} }
95
Output
Unsorted
111 Mayank london
131 Anshul nyc
121 Solanki jaipur By changing the return value inside
101 Aggarwal Hongkong
the compare method, you can sort in
Sorted by rollno any order that you wish to, for
101 Aggarwal Hongkong
example: For descending order just
111 Mayank london
121 Solanki jaipur change the positions of ‘a’ and ‘b’ in
131 Anshul nyc
the above compare method.
Sorted by name
101 Aggarwal Hongkong
131 Anshul nyc
111 Mayank london
121 Solanki jaipur
96
Sort collection by more than one field
In the previous example, we have discussed how to sort the list of objects on the basis of a single field using
the Comparable and Comparator interface But, what if we have a requirement to sort ArrayList objects in
accordance with more than one field like firstly, sort according to the student name and secondly, sort
according to student age.

97
Java Comparator Example-2
(Java Program to Demonstrate Working of Comparator Interface Via More than One Field)

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
// Class 1: Helper class representing a Student
class Student {
String Name;
int Age;
public Student(String Name, Integer Age) {
this.Name = Name;
this.Age = Age; }
// Getter setter methods
public String getName() { return Name; }
public void setName(String Name) { this.Name = Name; }
public Integer getAge() { return Age; }
public void setAge(Integer Age) { this.Age = Age; }
98
@Override public String toString() {
return "Customer{"+ "Name=" + Name + ", Age=" + Age + ‘}’; } }
// Class 2: Helper class implementing Comparator interface
class CustomerSortingComparator
implements Comparator<Student> {
// Method 1: To compare customers
@Override public int compare(Student customer1, Student customer2) {
// Comparing customers
int NameCompare = customer1.getName().compareTo(customer2.getName());
int AgeCompare = customer1.getAge().compareTo(customer2.getAge());
// 2nd level comparison
return (NameCompare == 0) ? AgeCompare : NameCompare;}}

99
public class Main {
public static void main(String[] args) {
List<Student> al = new ArrayList<>();
Student obj1 = new Student("Ajay", 27);
Student obj2 = new Student("Sneha", 23);
Student obj3 = new Student("Simran", 37);
Student obj4 = new Student("Ajay", 22);
Student obj5 = new Student("Ajay", 29);
Student obj6 = new Student("Sneha", 22);
al.add(obj1); al.add(obj2);
al.add(obj3); al.add(obj4);
al.add(obj5); al.add(obj6);
// Iterating using Iterator before Sorting ArrayList
Iterator<Student> custIterator = al.iterator();
System.out.println("Before Sorting:\n");
while (custIterator.hasNext()) {
System.out.println(custIterator.next()); }
// Sorting using sort method of Collections class
Collections.sort(al, new CustomerSortingComparator());
System.out.println("\n\nAfter Sorting:\n");
for (Student customer : al) {
System.out.println(customer);} } }
100
Output
Before Sorting:

Customer{Name=Ajay, Age=27}
Customer{Name=Sneha, Age=23}
Customer{Name=Simran, Age=37}
Customer{Name=Ajay, Age=22}
Customer{Name=Ajay, Age=29}
Customer{Name=Sneha, Age=22}

After Sorting:

Customer{Name=Ajay, Age=22}
Customer{Name=Ajay, Age=27}
Customer{Name=Ajay, Age=29}
Customer{Name=Simran, Age=37}
Customer{Name=Sneha, Age=22}
Customer{Name=Sneha, Age=23}

101
Comparable Interface and Comparator Interface
Comparable and Comparator both are interfaces and can be used to sort collection elements.
Comparable Comparator
1) Comparable provides a single sorting The Comparator provides multiple sorting
sequence. In other words, we can sort the sequences. In other words, we can sort the
collection on the basis of a single element such collection on the basis of multiple elements
as id, name, and price. such as id, name, and price etc.
2) Comparable affects the original class, i.e., Comparator doesn't affect the original class,
the actual class is modified. i.e., the actual class is not modified.
3) Comparable provides compareTo() Comparator provides compare() method to sort
method to sort elements. elements.
4) Comparable is present in java.lang package. A Comparator is present in
the java.util package.
5) We can sort the list elements of Comparable We can sort the list elements of Comparator
type by Collections.sort(List) method. type by Collections.sort(List,
Comparator) method.
102