ADVANCED JAVA

Module 1
The collections and Framework

3/25/2025
Department of Information Science and Engg
1
Transform Here
Collections Overview,
The Collection Interfaces,
The Collection Classes,
Accessing a collection Via an Iterator,
Storing User Defined Classes in Collections,
The Random Access, Interface, Working with Maps,
Comparators, The Collection Algorithms, Arrays,
The legacy Classes and Interfaces,
Parting Thoughts on Collections.

Department of Information Science and Engg

3/25/2025 2
Transform Here
 The Collection Framework
(java.util)
java.util package contains a large number of classes and interfaces that support
a broad range of functionality.

For example, this package contains a set of classes that generate

pseudorandom numbers, manage date and time, observe events, manipulate
sets of bits, tokenize strings, and handle formatted data.

The java.util package also contains one of Java’s most powerful subsystems:
The Collections Framework.

The Collections Framework is a sophisticated hierarchy of interfaces and classes

that provide state-of-the-art technology for managing groups of objects. It merits
close attention by all programmers.

Department of Information Science and Engg

3/25/2025 3
Transform Here
⚫ Collection form the foundation of efficient data handling in Java. Many
coding interview questions revolve around data structures and
algorithms, and Java Collections provide built-in implementations of these
concepts.
⚫ Important Topics to Prepare
List Interface: ArrayList, LinkedList, Vector
Set Interface: HashSet, LinkedHashSet, TreeSet
Queue Interface: PriorityQueue, Deque, ArrayDeque
Map Interface: HashMap, TreeMap, LinkedHashMap, ConcurrentHashMap
Sorting with Collections: Collections.sort(), Comparator vs Comparable
Thread-safe Collections: CopyOnWriteArrayList, ConcurrentHashMap
Practice solving problems using Java Collections on Leetcode, CodeChef,
CodeForces, or GeeksforGeeks.
Know time complexities (O(1), O(log N), O(N)) of different operations in collections.
Explain your choice of collection in a coding interview to show your depth of
knowledge.

3/25/2025
Department of Information Science and Engg
4
Transform Here
Collections Overview
The Java Collections Framework standardizes the way in which groups of
objects are handled by your programs.

Collections were not part of the original Java release, but were added by
J2SE 1.2. Prior to the Collections Framework, Java provided ad hoc classes
such as Dictionary, Vector, Stack, and Properties to store and manipulate
groups of objects.

Although these classes were quite useful, they lacked a central, unifying
theme.

Department of Information Science and Engg

3/25/2025 5
Transform Here
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. You may also implement your own collection, if you
choose.

Finally, mechanisms were added that allow the integration of standard

arrays into the Collections Framework.

Department of Information Science and Engg

3/25/2025 6
Transform Here
Algorithms are another important part of the collection mechanism.
Algorithms operate on collections and are defined as static methods
within the Collections class. Thus, they are available for all collections.

Each collection class need not implement its own versions. The
algorithms provide a standard means of manipulating collections.

Another item closely associated with the Collections Framework is the

Iterator interface. An iterator offers a general-purpose, standardized
way of accessing the elements within a collection, one at a time. Thus,
an iterator provides a means of enumerating the contents of a
collection.

Because each collection implements Iterator, the elements of any

collection class can be accessed through the methods defined by
Iterator. Thus, with only small changes, the code that cycles through a
set can also be used to cycle through a list, for example.

Department of Information Science and Engg

3/25/2025 7
Transform Here
In addition to collections, the framework defines several map interfaces
and classes. Maps store key/value pairs.

Although maps are part of the Collections Framework, they are not
“collections” in the strict use of the term. You can, however, obtain a
collection-view of a map. Such a view contains the elements from the
map stored in a collection.

Thus, you can process the contents of a map as a collection, if you

choose. The collection mechanism was retrofitted to some of the original
classes defined by java.util so that they too could be integrated into the
new system. It is important to understand that although the addition of
collections altered the architecture of many of the original utility classes,
it did not cause the deprecation of any. Collections simply provide a
better way of doing several things.

Department of Information Science and Engg

3/25/2025 8
Transform Here
The Collection Interfaces
The Collections Framework defines several interfaces. This section
provides an overview of each interface. Beginning with the collection
interfaces is necessary because they determine the fundamental
nature of the collection classes. Put differently, the concrete classes
simply provide different implementations of the standard interfaces.

Department of Information Science and Engg

3/25/2025 9
Transform Here
 Department of Information Science and Engg
3/25/2025 10
Transform Here
In addition to the collection interfaces, collections also use the Comparator,
RandomAccess, Iterator, and ListIterator interfaces.

Comparator defines how two objects are compared; Iterator and ListIterator
enumerate the objects within a collection. By implementing RandomAccess,
a list indicates that it supports efficient, random access to its elements.

To provide the greatest flexibility in their use, the collection interfaces allow
some methods to be optional.

The optional methods enable you to modify the contents of a collection.

Collections that support these methods are called modifiable.

Collections that do not allow their contents to be changed are called

unmodifiable.
If an attempt is made to use one of these methods on an unmodifiable
collection, an UnsupportedOperationException is thrown. All the built-in
collections are modifiable.

Department of Information Science and Engg

3/25/2025 11
Transform Here
Overview of List collection
List is a fundamental and widely-used collection type in the Java Collections
Framework. Basically, a list collection stores elements by insertion order (either
at the end or at a specific position in the list).

A list maintains indices of its elements so it allows adding, retrieving, modifying,

removing elements by an integer index (zero-based index; the first element is
at 0-index, the second at 1-index, the third at 2-index, and so on).

The following picture illustrates a list that stores some String elements:

Department of Information Science and Engg

3/25/2025 12
Transform Here
Wrapper classes in Java
A Wrapper class in Java is one whose object wraps or contains primitive data types.

When we create an object to a wrapper class, it contains a field and in this field, we
can store primitive data types.
Primitive Data Types and their Corresponding Wrapper Class
Primitive Data Type Wrapper Class
// int data type
char Character int b = 10;
byte Byte
short Short // wrapping around Integer object
int Integer Integer intobj = new Integer(b);
long Long
// Use with Java 9
float Float // Integer intobj = Integer.valueOf(b);
double Double
boolean Boolean

Department of Information Science and Engg

3/25/2025 13
Transform Here
 Why Generics in Java? Function Overloading

public class Main static void printdata(double a)

{ {
static void printdata(int a) System.out.println(a);
{ }
System.out.println(a);
} static void printdata(String a)
{
public static void main (String[] args) System.out.println(a);
{ }
printdata(2);
printdata(3.5) //error
printdata(“Hello”); //error
}
}

Department of Information Science and Engg

3/25/2025 14
Transform Here
Generics in
Java
Generics means parameterized types. The idea is to allow a type (like
Integer, String, etc., or user-defined types) to be a parameter to methods,
classes, and interfaces.

Using Generics, it is possible to create classes that work with different data
types.

An entity such as a class, interface, or method that operates on a

parameterized type is a generic entity.

Department of Information Science and Engg

3/25/2025 15
Transform Here
Types of Java Generics

Generic Method: It is exactly like a normal function, however, a generic

method has type parameters that are cited by actual type. This allows the
generic method to be used in a more general way. The compiler takes care
of the type of safety which enables programmers to code easily since they
do not have to perform long, individual type castings.

Generic Classes: A generic class is implemented exactly like a

non-generic class. The only difference is that it contains a type parameter
section. There can be more than one type of parameter, separated by a
comma. The classes, which accept one or more parameters, are known as
parameterized classes or parameterized types.

Department of Information Science and Engg

3/25/2025 16
Transform Here
// Java program to show working of user defined Generic functions

class Test {
// A Generic method example
static <T> void genericDisplay(T element)
{
System.out.println(element.getClass().getName() + " = " + element);
}

public static void main(String[] args)

{

genericDisplay(11); // Calling generic method with Integer argument

genericDisplay("GeeksForGeeks"); // Calling generic method with String argument

genericDisplay(1.0); // Calling generic method with double argument

}
}

Department of Information Science and Engg

3/25/2025 17
Transform Here
// Java program to show multiple type parameters in Java Generics
// We use < > to specify Parameter type

class Test<T, U> // Driver class to test above

{ public class Main
T obj1; // An object of type T {
U obj2; // An object of type U public static void main (String[] args)
{
// constructor Test <String, Integer> obj =
Test(T obj1, U obj2)
new Test<String, Integer>("GfG", 15);
{
obj.print();
this.obj1 = obj1;
this.obj2 = obj2;
} Test <Integer, Double> obj2 =
new Test<Integer,Double>( 15, 12.14);
// To print objects of T and U obj2.print();
public void print()
{ }
System.out.println(obj1+" "+obj2); } Output
} GfG 15
} 15 12.14

Department of Information Science and Engg

3/25/2025 18
Transform Here
// Java program to show working of user defined Generic classes
class Test<T> { // We use < > to specify Parameter type
// An object of type T is declared
T obj;
Test(T obj) { this.obj = obj; } // constructor
public T getObject() { return this.obj; }
}
class Main { // Driver class to test above
public static void main(String[] args)
{
// instance of Integer type
Test<Integer> iObj = new Test<Integer>(15);
System.out.println(iObj.getObject());

// instance of String type

Test<String> sObj
= new Test<String>("GeeksForGeeks");
System.out.println(sObj.getObject());
}
} Department of Information Science and Engg
3/25/2025 19
Transform Here
Advantages of Generics
Code Reusability: You can write a method, class, or interface once and
use it with any type.

Type Safety: Generics ensure that errors are detected at compile time
rather than runtime, promoting safer code.

No Need for Type Casting: The compiler automatically handles casting,

removing the need for explicit type casting when retrieving data.

Code Readability and Maintenance: By specifying types, code becomes

easier to read and maintain.

Generic Algorithms: Generics allow for the implementation of algorithms

that work across various types, promoting efficient coding practices.

Department of Information Science and Engg

3/25/2025 20
Transform Here
Disadvantages of Generics

Complexity: For beginners, understanding concepts like wildcards (?

extends, ? super) can be difficult.

Performance Overhead: Type erasure causes some overhead as generic

types are converted to Object during runtime.

No Support for Primitive Types: Generics only work with reference

types, requiring the use of wrapper classes like Integer or Double for
primitives.

Limited Reflection: Type erasure limits how much you can use reflection
with generics since type information is not available at runtime.

Department of Information Science and Engg

3/25/2025 21
Transform Here
 ArrayList
Array ArrayList
Fixed size Dynamic size
Value type elements Reference type elements
Can be multidimensional Single-dimensional
Type-safe Not type-safe
A bit faster than ArrayList A bit slower than Array

ArrayList is a dynamic, resizable collection of elements.

The ArrayList also provides more flexible and useful methods than arrays,
such as adding and removing elements, sorting, and searching.

Department of Information Science and Engg

3/25/2025 22
Transform Here
1. Creating ArrayList Object

ArrayList <Integer> integers; //null, only reference type is allowed

Integers = new ArrayList<>(); // Institating an ArrayList object

Or

ArrayList <Integer> integers = new ArrayList<>();

ArrayList <String> fruits = new ArrayList<>();
ArrayList <Double> dvalues = new ArrayList<>();

Note:
i. We are not specifying the size of array list
ii. In an ArrayList, we can store objects (String, Integer, Boolean, Double,
Character,..) not a primitive type (int, float, double, char…))

Department of Information Science and Engg

3/25/2025 23
Transform Here
 2. Adding items to ArrayList Object
- Using the add() method.
fruits.add(“Apple”);
fruits.add(“Banana”);
fruits.add(“Strawberry”);
System.out.println(fruits); // [Apple, Strawberry, Strawberry]

fruits.add(0, “Grapes”); // add item at index 0

3. Accessing items in the ArrayList Object

- Using the get() method.

System.out.println(fruits.get(0));
System.out.println(fruits.get(1));

4. Change an items in the ArrayList Object

- Using the set() method.
fruits.set(2, “Orange”);
System.out.println(fruits);

Department of Information Science and Engg

3/25/2025 24
Transform Here
5. Removing an item from the ArrayList Object

-To remove an element, use the remove() method

- Removing by index:

fruits.remove(1);
System.out.println(fruits); // [Apple, Orange]

- Removing by value:
fruits.remove(“Banana”);

-To remove all the elements, use the clear() method

fruits.clear();

Department of Information Science and Engg

3/25/2025 25
Transform Here
6. Print the size of ArrayList Object

-Using the size() method

System.out.println(fruits.size());

Department of Information Science and Engg

3/25/2025 26
Transform Here
Iterator
An Iterator is an object that can be used to loop through collections, like ArrayList
and HashSet. It is called an "iterator" because "iterating" is the technical term for
looping.

To use an Iterator, you must import it from the java.util package.

Getting an Iterator
The iterator() method can be used to get an Iterator for any collection:

Department of Information Science and Engg

3/25/2025 27
Transform Here
// Import the ArrayList class and the Iterator class
import java.util.ArrayList;
import java.util.Iterator;

public class Main {

public static void main(String[] args) {

// Make a collection
ArrayList<String> cars = new ArrayList<String>();
cars.add("Volvo");
cars.add("BMW"); while(it.hasNext()) {
cars.add("Ford"); System.out.println(it.next());
cars.add("Mazda"); }

// Get the iterator

Iterator<String> it = cars.iterator();

// Print the first item

System.out.println(it.next());
}
}
Department of Information Science and Engg
3/25/2025 28
Transform Here
 Removing Items from a Collection

import java.util.ArrayList; Iterator<Integer> it = numbers.iterator();

import java.util.Iterator; while(it.hasNext()) {
Integer i = it.next();
public class Main { if(i < 10) {
public static void main(String[] args) { it.remove();
ArrayList<Integer> numbers = new }
ArrayList<Integer>(); }
numbers.add(12); System.out.println(numbers);
numbers.add(8); }
numbers.add(2); }
numbers.add(23);

Department of Information Science and Engg

3/25/2025 29
Transform Here
Advantages of Iterator
The Iterator is a simple and easy-to-use interface that allows us to
traverse a collection without exposing its underlying implementation.

The Iterator is an efficient way to iterate over a collection, especially

when we have a large amount of data.

The Iterator provides a safe way to remove elements from a collection

during iteration without causing any concurrent modification
exceptions.

The Iterator interface is implemented by all the collection classes in

Java, so we can use the same code to iterate over different types of
collections

Department of Information Science and Engg

3/25/2025 30
Transform Here
Disadvantages of Iterator
The Iterator is a unidirectional interface, meaning that we
can only move forward through a collection. We cannot
move backward or jump to a specific element.

The Iterator is not thread-safe, so we cannot use it to

iterate over a collection in a multi-threaded environment
without proper synchronization.

The Iterator does not provide any mechanism to modify

elements while iterating over a collection, apart from
removing elements. If we need to modify elements, we
have to use other interfaces like ListIterator or a simple for
loop.

Department of Information Science and Engg

3/25/2025 31
Transform Here
Storing User-Defined Classes in Collections
Collection classes are used to store built in objects such
as Integer, String, Character etc. But the potential of
collection classes isn't just restricted to the storage of
built-in objects.

Collections classes can store any similar type of objects, be

it objects of a built-in class or objects of an user-defined
class.

This feature of collection class is very userful when we are

making an application which requires us to store many
objects of user-defined classes and not just objects of
built-in classes.
Department of Information Science and Engg
3/25/2025 32
Transform Here
Storing User-Defined Classes in Collections / User-Defined Objects in Collections
import java.util.LinkedList;
class Address {
private String name;
private String street;
private String city;
private String state;
private String code;
Address(String n, String s, String c, String st, String cd) {
name = n;
street = s;
city = c;
state = st;
code = cd;
}
public String toString() {
return name + "\n" + street + "\n" + city + " " + state + " " + code;
}
}
Department of Information Science and Engg
3/25/2025 33
Transform Here
public class Main {
public static void main(String args[])
{
LinkedList<Address> ml = new LinkedList<Address>();
Address obj1 =new Address("A", "11 Ave", "City", "IL", "00000")
ml.add(obj1);

ml.add(new Address("B", "11 Lane", "Town", "IL","99999"));

ml.add(new Address("T", "11 St", "Province", "IL", "11111"));

for (Address element : ml)

{
System.out.println(element + "\n");
}
}
}

Department of Information Science and Engg

3/25/2025 34
Transform Here
Program Analysis

▪ In this code above, we have overridden toString() method to give a

meaningful String representation of each object of Address class.
This method is inherited by all the classes from the main "Object"
class.

▪ ArrayList<Address>was declared to hold a collection of Customer

objects.

▪ We have declared and initialized 3 objects of Address class and

have stored them in an LinkedList(arr), by calling its add(Object o)
method.

▪ Finally, for-each loop iterates over the objects in ArrayList, and

display eachs object(one-by-one).

Department of Information Science and Engg

3/25/2025 35
Transform Here
The Random Access Interface
java.util
public Interface RandomAccess
Marker interface used by List implementations to indicate that they support fast
(generally constant time) random access. The primary purpose of this interface
is to allow generic algorithms to alter their behavior to provide good
performance when applied to either random or sequential access lists.

The best algorithms for manipulating random access lists (such as ArrayList)
can produce quadratic behavior when applied to sequential access lists (such
as LinkedList).

Generic list algorithms are encouraged to check whether the given list is an
instanceof this interface before applying an algorithm that would provide poor
performance if it were applied to a sequential access list, and to alter their
behavior if necessary to guarantee acceptable performance.

Department of Information Science and Engg

3/25/2025 36
Transform Here
It is recognized that the distinction between random and sequential access is
often fuzzy. For example, some List implementations provide asymptotically
linear access times if they get huge, but constant access times in practice. Such
a List implementation should generally implement this interface. As a rule of
thumb, a List implementation should implement this interface if, for typical
instances of the class, this loop:

for (int i=0, n=list.size(); i < n; i++)

list.get(i);

runs faster than this loop:

for (Iterator i=list.iterator();
i.hasNext(); )
i.next();

Department of Information Science and Engg

3/25/2025 37
Transform Here
 Working with Maps

A Map is an object that maps keys to values, or is a collection of

Key-Value pairs.

Java Map interface is not a subtype of the Collection interface. Therefore it

behaves a bit differently from the rest of the collection types.

No Duplicates in Keys: Ensures that keys are unique. However, values can be
duplicated.

Null Handling: Allows one null key in implementations like HashMap and
LinkedHashMap and allows multiple null values in most implementations.

The Map data structure in Java is implemented by two interfaces, the Map
Interface and the SortedMap Interface. Three primary classes implement these
interfaces HashMap, TreeMap, and LinkedHashMap.

Department of Information Science and Engg

3/25/2025 38
Transform Here
 Department of Information Science and Engg
3/25/2025 39
Transform Here
Why and When Use Maps:

Maps are perfect for key-value association mapping such as

dictionaries.

Use Maps when you want to retrieve and update elements by keys, or
perform look-ups by keys.

Some examples: A map of zip codes and cities.

A map of managers and employees. Each manager (key) is associated

with a list of employees (value) he manages.

A map of classes and students. Each class (key) is associated with a

list of students (value).

Department of Information Science and Engg

3/25/2025 40
Transform Here
Implementations of Map
In the inheritance tree of the Map interface, there
are several implementations but only 3 major,
common, and general-purpose implementations -
they are HashMap and LinkedHashMap and
TreeMap.

HashMap: this implementation uses a Hashtable

as the underlying data structure. It implements all
of the Map operations and allows null values and
one null key.
This class is roughly equivalent to Hashtable - a
legacy data structure before Java Collections
Framework, but it is not synchronized and permits
nulls.
HashMap does not guarantee the order of its
key-value elements. Therefore, consider to use a
HashMap when order does not matter and nulls
are acceptable.
Department of Information Science and Engg
3/25/2025 41
Transform Here
LinkedHashMap: this implementation uses a Hashtable and a linked list as
the underlying data structures, thus the order of a LinkedHashMap is
predictable, with insertion-order as the default order.
This implementation also allows nulls like HashMap. So consider using a
LinkedHashMap when you want a Map with its key-value pairs are sorted
by their insertion order.

TreeMap: this implementation uses a red-black tree as the underlying data

structure. A TreeMap is sorted according to the natural ordering of its
keys, or by a Comparator provided at creation time.
This implementation does not allow nulls. So consider using a TreeMap
when you want a Map sorts its key-value pairs by the natural order of the
keys (e.g. alphabetic order or numeric order), or by a custom order you
specify.

Department of Information Science and Engg

3/25/2025 42
Transform Here
Creating HashMap:

Always use interface type (Map), generics and diamond operator to declare a
new map. Creating any Map is as same as creating any other variable n Java.

Map<Integer, String> hashMap = new HashMap<>();

Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
Map<Integer, String> treeMap = new TreeMap<>();

Only there is a difference in creating different Maps but the most important
useful operations are same across all Maps.

So we use HashMap in all our examples to explain different most important Map
operations(Methods).

Most important basic operations of a Map are

• association (put),
• lookup (get),
• checking (containsKey and containsValue),
• modification (remove and replace) and
• cardinality (size and isEmpty).

Department of Information Science and Engg

3/25/2025 43
Transform Here
Association (put) and lookup (get) Operation

import java.util.HashMap;
import java.util.Map;

public class MapsDemo

{
public static void main(String[] args)
{
Map<Integer, String> zipCodes = new HashMap<>();
map.put(505001, "Hyderabad");
map.put(110001, "New Delhi");
map.put(400001, "Mumbai");

System.out.println("Getting the value Hyderabad with it's key:" + zipCodes.get(505001));

}
}

Department of Information Science and Engg

3/25/2025 44
Transform Here
Checking (containsKey and containsValue) and modification
(remove and replace) Operation
import java.util.HashMap;
import java.util.Map;

public class MapsDemo {

public static void main(String[] args) {
Map<Integer, String> zipCodes = new HashMap<>();
// Adding value in a Key and Value pair combination
zipCodes.put(505001, "Hyderabad");
zipCodes.put(110001, "New Delhi");
zipCodes.put(400001, "Mumbai");

System.out.println("Does map contains value Mumbai: " + zipCodes.containsValue("Mumbai"));

}
}

Output:
Does map contains value Mumbai: true

Department of Information Science and Engg

3/25/2025 45
Transform Here
import java.util.HashMap;
import java.util.Map;
public class MapsDemo
{
public static void main(String[] args) {
Map<Integer, String> zipCodes = new HashMap<>();
zipCodes.put(505001, "Hyderabad");
zipCodes.put(110001, "New Delhi");
zipCodes.put(400001, "Mumbai");

System.out.println("Map before removing: " + zipCodes);

zipCodes.remove(505001);
System.out.println("Map after removing: " + zipCodes);
}
}
Output:
Map before removing: {110001=New Delhi, 400001=Mumbai, 505001=Hyderabad}
Map after removing: {110001=New Delhi, 400001=Mumbai}

Department of Information Science and Engg

3/25/2025 46
Transform Here
System.out.println("Map before replacing: " + zipCodes);
zipCodes.replace(505001, "Secunderabad");
System.out.println("Map after replacing: " + zipCodes);

Output:
Map before replacing: {110001=New Delhi, 400001=Mumbai, 505001=Hyderabad}
Map after replacing: {110001=New Delhi, 400001=Mumbai, 505001=Secunderabad}

Department of Information Science and Engg

3/25/2025 47
Transform Here
The size()method returns the number of key-value mappings in this
map. For example:
import java.util.HashMap;
import java.util.Map;
public class MapsDemo
{
public static void main(String[] args) {
Map<Integer, String> zipCodes = new HashMap<>();
// Adding value in a Key and Value pair combination
zipCodes.put(505001, "Hyderabad");
zipCodes.put(110001, "New Delhi");
zipCodes.put(400001, "Mumbai");

System.out.println("Map size: " + zipCodes.size());

}
}

Output:
Map size: 3
Department of Information Science and Engg
3/25/2025 48
Transform Here
clear Method and isEmpty Method
import java.util.HashMap;
import java.util.Map;
public class MapsDemo
{
public static void main(String[] args) {
Map<Integer, String> zipCodes = new HashMap<>();
// Adding value in a Key and Value pair combination
zipCodes.put(505001, "Hyderabad");
zipCodes.put(110001, "New Delhi");
zipCodes.put(400001, "Mumbai");

// Reset map i.e. clear all existing entries Output:

zipCodes.clear(); Map size: 0
// Size becomes Zero as we cleared all entries
System.out.println("Map size: " + zipCodes.size());
}
}

Department of Information Science and Engg

3/25/2025 49
Transform Here
 Department of Information Science and Engg
3/25/2025 50
Transform Here
Java Advanced Sorting (Comparator and Comparable)
An object that implements the Comparator interface is called a comparator.

The Comparator interface allows you to create a class with a compare()

method that compares two objects to decide which one should go first in a
list.

The compare() method, when used in the context of a Comparator

interface, should return a negative integer, zero, or a positive integer to
indicate whether the first argument is less than, equal to, or greater than
the second argument, respectively.

Comparator interface in Java is used to order the objects of user-defined

classes. A comparator object is capable of comparing two objects of the
same class.

Department of Information Science and Engg

3/25/2025 51
Transform Here
import java.util.*;
// Sort student objects by rollno
class Student {
int rollno; String name;
Student(int rollno, String name) {
this.rollno = rollno;
this.name = name;
}
public String toString() { return rollno + ": " + name; }
}

// Helper class implementing Comparator interface

class SortbyRoll implements Comparator<Student>
{
public int compare(Student a, Student b)
{
return a.rollno - b.rollno;
}
}

Department of Information Science and Engg

3/25/2025 52
Transform Here
public class GFG
{
public static void main(String[] args)
{
List<Student> students = new ArrayList<>();

students.add(new Student(111, "Mayank"));

students.add(new Student(131, "Anshul"));
students.add(new Student(121, "Solanki"));
students.add(new Student(101, "Aggarwal"));

// Sort students by roll number using SortbyRoll comparator

Collections.sort(students, new SortbyRoll());

System.out.println("Sorted by Roll Number ");

for (int i = 0; i < students.size(); i++)

System.out.println(students.get(i));

}
}
Department of Information Science and Engg
3/25/2025 53
Transform Here
// Sort Car objects by year
class SortByYear implements Comparator
{
public int compare(Object obj1, Object obj2)
{
// Make sure that the objects are Car objects
Car a = (Car) obj1;
Car b = (Car) obj2;

// Compare the objects

if (a.year < b.year) return -1; // The first car has a old Model
if (a.year > b.year) return 1; // The first car has a latest Model
return 0; // Both cars have the same year
}
}

Department of Information Science and Engg

3/25/2025 54
Transform Here
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
// Create a comparator
// Define a Car class class SortByYear implements Comparator {
class Car { public int compare(Object obj1, Object obj2) {
public String brand; // Make sure that the objects are Car objects
Car a = (Car) obj1;
public String model; Car b = (Car) obj2;
public int year;
// Compare the year of both objects
if (a.year < b.year) return -1; // The first car has a smaller year
public Car(String b, String m, int y)
if (a.year > b.year) return 1; // The first car has a larger year
{ return 0; // Both cars have the same year
brand = b; }
model = m; }
year = y;
}
}

Department of Information Science and Engg

3/25/2025 55
Transform Here
public class Main {
public static void main(String[] args) {
// Create a list of cars
ArrayList<Car> myCars = new ArrayList<Car>();
myCars.add(new Car("BMW", "X5", 1999));
myCars.add(new Car("Honda", "Accord", 2006));
myCars.add(new Car("Ford", "Mustang", 1970));

// Use a comparator to sort the cars

Comparator myComparator = new SortByYear();
Collections.sort(myCars, myComparator);

// Display the cars

for (Car c : myCars) {
System.out.println(c.brand + " " + c.model + " " + c.year);
}
}
}

Department of Information Science and Engg

3/25/2025 56
Transform Here
Special Sorting Rules
Comparators can also be used to make special sorting rules for strings
and numbers. In this example we use a comparator to list all of the even
numbers before the odd ones:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class SortEvenFirst implements Comparator {

public int compare(Object obj1, Object obj2) {
// Make sure the objects are integers
Integer a = (Integer)obj1;
Integer b = (Integer)obj2;

// Check each number to see if it is even

// A number is even if the remainder when dividing by 2 is 0
boolean aIsEven = (a % 2) == 0;
boolean bIsEven = (b % 2) == 0;

Department of Information Science and Engg

3/25/2025 57
Transform Here
if (aIsEven == bIsEven) {

// If both numbers are even or both are odd then use normal sorting rules
if (a < b) return -1;
if (a > b) return 1;
return 0;

} else {

// If a is even then it goes first, otherwise b goes first

if (aIsEven) {
return -1;
} else {
return 1;
}
}
}
}

Department of Information Science and Engg

3/25/2025 58
Transform Here
public class Main {
public static void main(String[] args) {
ArrayList<Integer> myNumbers = new ArrayList<Integer>();
myNumbers.add(33);
myNumbers.add(15);
myNumbers.add(20);
myNumbers.add(34);
myNumbers.add(8);
myNumbers.add(12);

Comparator myComparator = new SortEvenFirst();

Collections.sort(myNumbers, myComparator);

for (int i : myNumbers) {

System.out.println(i);
}
}
}

Department of Information Science and Engg

3/25/2025 59
Transform Here
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 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.
// Using Comparator Interface Via More than One Field
import java.util.*;
class Student
{
String name;
Integer age;
Student(String name, Integer age) {
this.name = name;
this.age = age;
}

public String getName() { return name; }

public Integer getAge() { return age; }

public String toString() { return name + " : " + age; }

}

Department of Information Science and Engg

3/25/2025 60
Transform Here
// Comparator in a Helper Class

class CustomerSortingComparator implements Comparator<Student>

{

// Compare first by name, then by age

public int compare(Student customer1, Student customer2) {

int NameCompare = customer1.getName().compareTo(customer2.getName());

// If names are the same, compare by age

int AgeCompare = customer1.getAge().compareTo(customer2.getAge());

// Return the result: first by name, second by age

return (NameCompare == 0) ? AgeCompare : NameCompare;
}
}

Department of Information Science and Engg

3/25/2025 61
Transform Here
public class ComparatorHelperClassExample
{
public static void main(String[] args)
{
List<Student> students = new ArrayList<>();

students.add(new Student("Ajay", 27));

students.add(new Student("Sneha", 23));
students.add(new Student("Simran", 37));
students.add(new Student("Ankit", 22));
students.add(new Student("Anshul", 29));
students.add(new Student("Sneha", 22));

System.out.println("Original List ");

for (Student it : students) { System.out.println(it); }

System.out.println();
// Sort students by name, then by age using the CustomerSortingComparator
Collections.sort(students, new CustomerSortingComparator());

Department of Information Science and Engg

3/25/2025 62
Transform Here
 // Display message only
System.out.println("After Sorting ");

// Iterating using enhanced for-loop

// after Sorting ArrayList
for (Student it : students) {
System.out.println(it);
}
}
}

Department of Information Science and Engg

3/25/2025 63
Transform Here
The Comparable
Interface
The Comparable interface allows an object to specify its own sorting rule with a
compareTo() method.

The compareTo() method takes an object as an argument and compares the

comparable with the argument to decide which one should go first in a list.

Like the comparator, the compareTo() method returns a number which is:

Negative if the comparable should go first in a list.

Positive if the other object should go first in a list.
Zero if the order does not matter.

Many native Java classes implement the Comparable interface, such as String
and Integer.

This is why strings and numbers do not need a comparator to be sorted.

Department of Information Science and Engg

3/25/2025 64
Transform Here
import java.util.*;
class Student2 implements Comparable<Student2> {
int rollno;
String name;

Student2(int rollno, String name) {

this.rollno = rollno;
this.name = name;
}

public String toString() {

return rollno + ": " + name;
}

public int compareTo(Student2 other) {

return this.rollno - other.rollno;
}
}
Department of Information Science and Engg
3/25/2025 65
Transform Here
public class ComparableStudents {
public static void main(String[] args) {
List<Student2> students = new ArrayList<>();

students.add(new Student2(111, "Mayank"));

students.add(new Student2(131, "Anshul"));
students.add(new Student2(121, "Solanki"));
students.add(new Student2(101, "Aggarwal"));

// Sort students by roll number using Comparable

Collections.sort(students);

System.out.println("Sorted by Roll Number ");

for (Student2 student : students) {

System.out.println(student);
}
}
}

Department of Information Science and Engg

3/25/2025 66
Transform Here
 Java - The Collection Algorithms

The collections framework defines several algorithms that can be applied to

collections and maps.

The polymorphic algorithms described here are pieces of reusable functionality

provided by the Java platform. All of them come from the Collections class, and all
take the form of static methods whose first argument is the collection on which the
operation is to be performed.
The great majority of the algorithms provided by the Java platform operate on List
instances, but a few of them operate on arbitrary Collection instances. This section
briefly describes the following algorithms:
i. Sorting
ii. Shuffling
iii. Routine Data Manipulation
iv. Searching
v. Composition
vi. Finding Extreme Values

Department of Information Science and Engg

3/25/2025 67
Transform Here
import java.util.*;

public class Sort {

public static void main(String[] args) {
List<String> list = Arrays.asList(args);
Collections.sort(list);
System.out.println(list);
}
}
The program was included only to show you that algorithms really are as easy to
use as they appear to be.

The second form of sort takes a Comparator in addition to a List and sorts the
elements with the Comparator.

Department of Information Science and Engg

3/25/2025 68
Transform Here
Shuffling
The shuffle algorithm does the opposite of what sort does, destroying any trace of
order that may have been present in a List. That is, this algorithm reorders the
List based on input from a source of randomness such that all possible
permutations occur with equal likelihood, assuming a fair source of randomness.

This algorithm is useful in implementing games of chance. For example, it could

be used to shuffle a List of Card objects representing a deck. Also, it's useful for
generating test cases.

This operation has two forms: one takes a List and uses a default source of
randomness, and the other requires the caller to provide a Random object to use
as a source of randomness. The code for this algorithm is used as an example in
the List section.

Department of Information Science and Engg

3/25/2025 69
Transform Here
 Routine Data Manipulation
The Collections class provides five algorithms for doing routine data manipulation
on List objects, all of which are pretty straightforward:

i. reverse — reverses the order of the elements in a List.

ii. fill — overwrites every element in a List with the specified value. This
operation is useful for reinitializing a List.

iii. copy — takes two arguments, a destination List and a source List, and copies
the elements of the source into the destination, overwriting its contents. The
destination List must be at least as long as the source. If it is longer, the
remaining elements in the destination List are unaffected.

iv. swap — swaps the elements at the specified positions in a List.

v. addAll — adds all the specified elements to a Collection. The elements to be

added may be specified individually or as an array.

Department of Information Science and Engg

3/25/2025 70
Transform Here
Searching
The binarySearch algorithm searches for a specified element in a sorted List.
This algorithm has two forms.

The first takes a List and an element to search for (the "search key"). This form
assumes that the List is sorted in ascending order according to the natural ordering of
its elements.
The second form takes a Comparator in addition to the List and the search key, and
assumes that the List is sorted into ascending order according to the specified
Comparator. The sort algorithm can be used to sort the List prior to calling
binarySearch.

The return value is the same for both forms. If the List contains the search key, its
index is returned. If not, the return value is (-(insertion point) - 1), where the insertion
point is the point at which the value would be inserted into the List, or the index of the
first element greater than the value or list.size() if all elements in the List are less than
the specified value.
int pos = Collections.binarySearch(list, key);
if (pos < 0)
l.add(-pos-1, key);
Department of Information Science and Engg
3/25/2025 71
Transform Here
Composition
The frequency and disjoint algorithms test some aspect of the composition of one
or more Collections:

frequency — counts the number of times the specified element occurs in the
specified collection
disjoint — determines whether two Collections are disjoint; that is, whether they
contain no elements in common.

Finding Extreme Values

The min and the max algorithms return, respectively, the minimum and maximum
element contained in a specified Collection.

Both of these operations come in two forms.

The simple form takes only a Collection and returns the minimum (or maximum)
element according to the elements' natural ordering.

The second form takes a Comparator in addition to the Collection and returns the
minimum (or maximum) element according to the specified Comparator.

Department of Information Science and Engg

3/25/2025 72
Transform Here
 Department of Information Science and Engg
3/25/2025 73
Transform Here
 Department of Information Science and Engg
3/25/2025 74
Transform Here
 Department of Information Science and Engg
3/25/2025 75
Transform Here
 Department of Information Science and Engg
3/25/2025 76
Transform Here
 Department of Information Science and Engg
3/25/2025 77
Transform Here