UNIT-4

Collections Overview
• The Java collection’s framework provides a large set of readily usable
general-purpose data structures and algorithms.
• Collection framework standardizes the way in which group of objects are
handled by our program.
• These data structures and algorithms can be used with any suitable data type
in a type-safe manner; this is achieved through the use of a language feature
known as generics.

interfaces - in Collection framework

Collection:
• Common base interface for all the interfaces(classes) in the collection
hierarchy.
• Consists of methods that are common for all types of containers (List’s,
Set’s and Map’s)
List:
• List is for containers that store a sequence of elements
• You can insert the elements using an index, and retrieve the same element
later (so that it maintains the insertion order).
• You can store duplicate elements in a List.
Set:
List for containers that do not allow duplicate elements.
SortedSet:
It maintains the set elements in a sorted order.
NavigableSet:
It allows searching the set for the closest matches
Queue:
• It is the base interface for containers that holds a sequence of elements for
processing.
• For example, the classes implementing Queue can be LIFO (last in, first
out—as in stack data structure) or FIFO (first in, first out—as in queue data
structure).
Deque:
you can insert or remove elements from both the ends.
Map:
It is for containers that map keys to values.
SortedMap - the keys are in a sorted order.
NavigableMap - allows you to search and return the closest match for given
search criteria.
Note : Map hierarchy does not extend the Collection interface.
 Important Methods of “Collection” interface
add(): Adds elem into the underlying container.
clear(): Removes all elements from the container.
isEmpty(): Checks whether the container has any elements or not.
iterator(): Returns an Iterator<Element> object for iterating over the container.
remove(): Removes the element if obj is present in the container.
size(): Returns the number of elements in the container.
toArray(): Returns an array that has all elements in the container.
addAll(Collection c2): Adds all the elements in c2 into the underlying container.
containsAll(Collection c2): Checks if all elements given in c2 are present in the
underlying container.
removeAll(Collection c2): Removes all elements from the underlying container
that are also present in c2.
retainAll(Collection c2): Retains elements in the underlying container only if they
are also present in c2; it removes all other elements.

Classes - in Collection framework

 ArrayList
• Java “ArrayList” class uses a dynamic array for storing the elements.
• No size limit, We can add or remove elements anytime. So, it is much more
flexible than the traditional array.
• It inherits AbstractList class and implements List interface.
• It implements the List interface so we can use all the methods of List
interface apart from the methods of Collection interface.
• Maintains the insertion order.
• Allows random access.
• Manipulation is little bit slower than the LinkedList in Java because a lot of
shifting needs to occur if any element is removed from the array list.
• Can have the duplicate elements.
• It is in the java.util package.
• Non synchronized.
Example program:
import java.util.*;
class Demo1
{
public static void main(String args[])
{
ArrayList<String> al = new ArrayList<String>();
al.add("A");
al.add("B");
al.add("C");
al.add("D");
al.add("E");
al.add("F");
System.out.println( al);
System.out.println( al.size() );
 String s = al.get( 0 );
System.out.println("The First Element is : " + s );

al.add( 3 , "Z" );
System.out.println( al );

al.remove( "E" );
System.out.println( al );

al.remove(2);
System.out.println(al);
}
}

LinkedList
• LikedList class provides a linked-list data structure.
• Uses a “doubly linked” list to store the elements.
• It inherits from AbstractList class and implements List and Deque
interfaces.
• Manipulation is fast because no shifting needs to occur.
• Can be used as a list, stack, Queue & Deque.
• Maintains insertion order.
• Can contain duplicate elements.
• Non synchronized.
Example program:
import java.util.*;
class Demo3
{
public static void main(String args[])
{
LinkedList<String> ll = new LinkedList<String>();
ll.add("C");
ll.add("D");
ll.add("E");
System.out.println(ll);

ll.addFirst("B");
ll.addLast("F");
System.out.println(ll);

System.out.println(ll.peekFirst());
System.out.println(ll.peekLast());
System.out.println(ll);

ll.pollFirst();
ll.pollLast();
System.out.println(ll);
}
}
 HashSet
• HashSet class contains unique elements only.
• Inherits the AbstractSet class and implements Set interface.
• Creates a collection that uses a hash table for storage.
• Stores the elements by using a mechanism called hashing.
• Doesn't maintain the insertion order. Here, elements are inserted on the basis
of their hash code.
• Best approach for search operations.
• Non synchronized.
Example:
import java.util.*;
class Demo4
{
public static void main(String args[])
{
HashSet<String> hs = new HashSet<String>();
hs.add("Beta");
hs.add("Alpha");
hs.add("Eta");
hs.add("Gamma");
hs.add("Epsilon");
hs.add("Omega");
System.out.println(hs);
}
}
 LinkedHashSet
• Derived class of HashSet. Provides insertion order iteration
Program: Replace HashSet with LinkedHashSet in the above program

TreeSet
• TreeSet class inherits AbstractSet class and implements NavigableSet
interface.
• Objects are stored in ascending order.
• TreeSet class uses a Red Black tree for storage.
• Contains unique elements only like HashSet.
• Access and retrieval times are quite fast.
• Non synchronized.
Example program:
import java.util.*;
class Demo6
{
public static void main(String args[])
{
TreeSet<String> ts = new TreeSet<String>();
ts.add("Beta");
ts.add("Alpha");
ts.add("Eta");
ts.add("Gamma");
ts.add("Epsilon");
ts.add("Omega");
System.out.println(ts);
}
}
 PriorityQueue
• PriorityQueue class inherits from AbstractQueue class.
• Provides the facility of using queue. But it does not order elements in FIFO
manner.
• Retrieving elements based on priority.
• Irrespective of the order in which you insert, when you remove the elements,
the highest priority element will be retrieved first.
• Data structure used: Heap data structure.
Example:
import java.util.*;
class Demo
{
public static void main(String args[])
{
PriorityQueue<String> p = new PriorityQueue<String>();
p.add("Amit");
p.add("Vijay");
p.add("Karan");
p.add("Jai");
p.add("Rahul");
for(int i=1 ; i<=5 ; i++)
{
String s = p.poll();
System.out.println(s);
}
}
}
 ArrayDeque
• This class Provides the facility of using deque and resizable-array.
• Inherits AbstractCollection class & implements the Deque interface.
• Unlike Queue, we can add or remove elements from both sides.
• Not thread safe.
• No capacity restrictions.
Example Program:
import java.util.*;
class Demo7
{
public static void main(String args[])
{
ArrayDeque<Integer> adq = new ArrayDeque<Integer>();
adq.add(15);
adq.add(20);
adq.addLast(30);
adq.addLast(40);
adq.addLast(50);
adq.addFirst(10);
System.out.println(adq);
adq.pollLast();
System.out.println(adq);
}
}
 Accessing a Collection via - Iterator
Iterator interface help us to retrieve objects in the collection one by one.
Example Program:
import java.util.*;
class Demo8
{
public static void main(String args[])
{
ArrayList<String> al = new ArrayList<String>();
al.add("A");
al.add("B");
al.add("C");
al.add("D");
al.add("E");

Iterator<String> itr = al.iterator();

while( itr.hasNext() )
{
String x = itr.next();
System.out.println(x);
}
}
}
 The For-Each alternative
import java.util.*;
class Demo9
{
public static void main(String args[])
{
ArrayList<String> al = new ArrayList<String>();
al.add("A");
al.add("B");
al.add("C");
al.add("D");
al.add("E");

for(String x : al )
{
System.out.println( x );
}
}
}

HashMap
• HashMap class inherits AbstractMap class and implements the Map
interface.
• Allows us to store key and value pairs, where keys should be unique.
• If you try to insert the duplicate key, it will replace the element(value) of the
corresponding key.
• Operations like updation, deletion.. etc are performed using the key index.
• Does not maintain insertion order.
 • Not synchronized.
Example program:
import java.util.*;
class Demo14
{
public static void main(String args[])
{
HashMap<String,Integer> hm = new HashMap<String,Integer>();
hm.put("bhaskar", 55000);
hm.put("shiva",65000);
hm.put("anil",35000);
hm.put("younus",47000);

Set< Map.Entry<String,Integer> > s1 = hm.entrySet();

for( Map.Entry<String,Integer> e : s1 )
{
System.out.print( e.getKey() + " ");
System.out.println( e.getValue() );
}
}
}
TreeMap
• TreeMap class Provides an efficient means of storing key-value pairs in
sorted order.
• Implements the NavigableMap interface and extends AbstractMap class.
 • Uses Red-Black tree for implementation.
• Non synchronized.
Example program:
import java.util.*;
class Demo
{
public static void main(String args[])
{
TreeMap<String, Integer> tm = new TreeMap<String, Integer>();
tm.put("bhaskar", 55000);
tm.put("shiva", 65000);
tm.put("anil", 35000);
tm.put("younus", 47000);

Set<Map.Entry<String,Integer>> s1 = tm.entrySet();

for(Map.Entry<String,Integer> e : s1 )
{
System.out.print( e.getKey() + " ");
System.out.println( e.getValue() );
}
}
}
 Comparator
Java Comparator interface is used to order the objects of a user-defined class.
This interface is in java.util package and contains 2 methods
1. compare(Object obj1,Object obj2)
2. 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.
Example program:
import java.util.*;
class Emp
{
String name;
int exp;
Emp(String name, int exp)
{
this.name = name;
this.exp = exp;
}
void display()
{
System.out.print(name + " ");
System.out.println(exp);
}
}
class Demo
{
public static void main(String args[])
{
TreeSet<Emp> ts = new TreeSet<Emp>( new A() );
Emp e1 = new Emp("shiva",15);
Emp e2 = new Emp("younus",13);
Emp e3 = new Emp("anil",12);
Emp e4 = new Emp("ravi",18);
ts.add(e1);
ts.add(e2);
ts.add(e3);
ts.add(e4);
for ( Emp x : ts )
{
x.display();
}
}
}
class A implements Comparator<Emp>
{
public int compare(Emp e1, Emp e2)
{
if( e1.exp > e2.exp )
{
 return 1;
}
else
{
return -1;
}
}
}

The Legacy Classes and Interfaces

Dictionary:
The Dictionary is an abstract class operates much like Map interface and
represents the key/value storage repository.

Hashtable
• Hashtable class is similar to HashMap, but synchronized.
• Implemented abstract class "Dictionary".
• However, with the advent of collections, Hashtable was reengineered to also
implement the Map interface.
• Thus, Vector is integrated into the Collection Framework
Example program:
import java.util.*;
class Demo
{
public static void main(String args[])
{
Hashtable<String,Integer> ht = new Hashtable<String,Integer>();
ht.put("cseE",70);
 ht.put("cseF",70);
ht.put("cseG",60);
ht.put("IT",60);
System.out.println( ht );
}
}

Properties
• Properties class is a sub class of Hashtable.
• For each entry, key is a String and the value is also a String.
• The Properties class is used by some other Java classes.
Example : System.getProperties( ) method returns environmental values.
Example program:
import java.util.*;
class Demo
{
public static void main(String args[])
{
Properties p = new Properties();
p.put("Telangana","Hyderabad");
p.put("Andhra Pradesh","Amaravathi");
p.put("Tamilnadu","Chennai");
p.put("Karnataka","Banglore");
System.out.println( p );
}
}
 Vector
• Vector class implements a dynamic array.
• Similar to ArrayList, but Synchronized.
• With the advent of collections, Vector was reengineered to extend
AbstractList & to implement the List interface.
• Thus, Vector is integrated into the Collection Framework.
Example:
import java.util.*;
class Demo1
{
public static void main(String args[])
{
Vector<Integer> v = new Vector<Integer>( 3 , 2 );
System.out.println(v.size());
System.out.println(v.capacity());

v.addElement(5);
v.add(6);
v.add(0,4);
System.out.println(v);
System.out.println(v.capacity());

v.addElement(7);
System.out.println(v);
System.out.println(v.capacity());
 System.out.println(v.firstElement());
System.out.println(v.lastElement());
if( v.contains(7) )
System.out.println("Vector contains 7");
}
}

Stack
• Stack is a subclass of Vector that implements a standard last-in, first-out
stack.
• With the release of JDK 5, Stack was retrofitted for generics
Example:
import java.util.*;
class Demo3
{
public static void main(String args[])
{
Stack<Integer> st = new Stack<Integer>();
st.push(30);
st.push(20);
st.push(10);
System.out.println(st);
st.pop();
System.out.println(st);
}
}
 Enumeration
• This legacy interface works similar to Iterator interface of collection frame
work.
• Helps us to retrieve one object at a time from the group of objects.
Example:
import java.util.*;
class Demo2
{
public static void main(String args[])
{
Vector<Integer> v = new Vector<Integer>();
v.addElement(5);
v.addElement(6);
v.add(7);
v.add(8);

Enumeration<Integer> e = v.elements();

while( e.hasMoreElements() )
{
System.out.println(e.nextElement());
}
}
}
 More Utility classes
StringTokenizer
• Allows you to break a String into tokens. It is simple way to break string.
• It doesn't provide the facility to differentiate numbers, quoted strings,
identifiers etc. like StreamTokenizer class.
Example Program:
import java.util.*;
class Demo1
{
static String s = "sunday,monday,tuesday,wednesday";
public static void main(String args[])
{
StringTokenizer st = new StringTokenizer(s, ",");
while( st.hasMoreTokens() )
{
String t = st.nextToken();
System.out.println(t);
}
}
}

BitSet
• The Java BitSet class implements a vector of bits.
• Grows automatically as more bits are needed.
• Each element of BitSet contains either true(1) or false(0) value.
• Initially, all bits of a BitSet have the false value.
• The index of bits of BitSet class is represented by positive integers.
 • The contents of one BitSet may be changed by other BitSet using logical
AND, logical OR and logical exclusive OR operations.
• Not thread safe.
Example program:
import java.util.*;
class Demo2
{
public static void main(String args[])
{
BitSet bits1 = new BitSet(8);
BitSet bits2 = new BitSet(8);

for(int i=0; i<8; i++)

{
if( (i%2) == 0 )
bits1.set( i );
if((i%3) == 0)
bits2.set( i );
}
System.out.println(bits1);
System.out.println(bits2);

bits2.and(bits1);
System.out.println(bits2);

bits2.or(bits1);
 System.out.println(bits2);

bits2.xor(bits1);
System.out.println(bits2);
}
}

Date
• Represents date and time in java.
• Provides constructors and methods to deal with date and time in java.
• Implements Serializable, Cloneable and Comparable interfaces.
• After Calendar class, most of the constructors and methods of Date class
has been deprecated.
Example program:
import java.util.Date;
class Demo3
{
public static void main(String args[])
{
Date d = new Date();
/* To Display Complete date and time information */
System.out.println( d );
/* To Display number of milliseconds since midnight, January 1, 1970 GMT */
long msec = d.getTime();
System.out.println("Time: " + msec);
}
}
 Calendar
• Java Calendar class is an abstract class that provides methods for converting
date between a specific instant in time and a set of calendar fields such as
MONTH, YEAR, HOUR, etc.
• It inherits Object class and implements the Comparable interface.
Example program:
import java.util.*;
class Demo4
{
public static void main(String args[])
{
Calendar c1 = Calendar.getInstance();
String months[] = {
"Jan", "Feb", "Mar", "Apr",
"May", "June", "Jul", "Aug",
"Sep", "Oct", "Nov", "Dec"};

System.out.print("Date: ");
System.out.print( c1.get(Calendar.DATE) + " " );
int m = c1.get( Calendar.MONTH );
System.out.print(months[m] + " ");
System.out.println(c1.get( Calendar.YEAR ) );

System.out.print("Time: ");
System.out.print( c1.get( Calendar.HOUR ) + " : ");
System.out.print( c1.get( Calendar.MINUTE ) + " : " );
 System.out.println( c1.get( Calendar.SECOND ) );
}
}

Random
Java Random class is used to generate a stream of pseudorandom numbers.
Example program:
import java.util.*;
class Demo5
{
public static void main(String args[])
{
Random r = new Random();
for ( int i=1 ; i<=10 ; i++)
{
int x = r.nextInt(100);
System.out.println(x);
}
}
}

Formatter
• This class is used for layout justification and alignment, common formats for
numeric, string, and date/time data, and locale-specific output in java
programming.
• The Formatter class is defined as final class inside the java.util package.
Example program:
import java.util.*;
class Demo6
{
public static void main(String args[])
{
Formatter fmt1 = new Formatter();
fmt1.format("Formatting %s is easy %d %4.2f", "with Java", 10, 98.6);
System.out.println(fmt1);
fmt1.close();

Formatter fmt2 = new Formatter();

Calendar c1 = Calendar.getInstance();
fmt2.format("%tr", c1); // Display standard 12-hour time format.
System.out.println(fmt2);
fmt2.close();
}
}

Scanner
• From java.util package.
• It is the simplest way to get input in Java. By the help of Scanner in Java, we
can get input from the user in primitive types such as int, long, double, byte,
float, short, etc.
• breaks the input into tokens using a delimiter which is whitespace by default.
• It provides many methods to read and parse various primitive values.
• Widely used to parse text for strings and primitive types using a regular
expression.
Example program:
import java.util.*;
class Test
{
public static void main(String args[])
{
Scanner in = new Scanner(System.in);
System.out.print("Enter your name: ");
String name = in.nextLine();
System.out.println("Name is: " + name);
in.close();
}
}

Collection Algorithms ( “Collections” class)

• The collections framework defines several algorithms that can be applied to
collections and maps.
• These algorithms are defined as static methods within the Collections class
which are helpful for the operations such as:
➢ Data Manipulation
➢ Sorting
➢ Shuffling
➢ Searching
➢ Finding Extreme Values
addAll() : To add more than one value at once.
List<Integer> a = new ArrayList<>();
Collections.addAll( a , 60,50,40,30);
System.out.println( a );
max() : Returns the maximum element in the collection as determined by natural
ordering.
int x = Collections.max(a);
System.out.println(x);
sort() : Sorts the elements of the collection.
Ex1: Collections.sort(a);
System.out.println(a);
Ex2: Collections.sort( a , Collections.reverseOrder() );
System.out.println(a);
binarySearch(): searches the key using binary search in the specified list.
Collections.sort(a);
System.out.println( Collections.binarySearch(a,50) );
reverse() : Reverses the sequence in list
Collections.reverse(a);
System.out.println(a);
shuffle() : Shuffles (i.e., randomizes) the elements in list.
Collections.shuffle(a)
System.out.println(a);
disjoint(): This method returns true if the two specified collections have no
elements in common.
boolean x = Collections.disjoint( list1, list2 )
System.out.println(x);
rotate() : Rotates list by n places to the right. To rotate left, use a negative value
for n.
Collections.rotate(a,2);
System.out.println(a);
 Example:
[10, 20, 30, 40, 50]
[40, 50, 10, 20, 30]
copy(List l1, List l2) : Copies the elements of list l2 to l1.

"Arrays" - class
➢ The "Arrays" class is in java.util package & is part of Collection
Framework.
➢ Arrays class provides several static methods that can be used to
perform many tasks directly without the use of loops such as
➢ Fill an array with a particular value
➢ Sorting
➢ Searching, …… etc,

sort() : Sorts the complete array in ascending order.

int a[] = {10,20,15,22,35};
Arrays.sort( a );
binarySearch() : Searches for the specified element in the array with the help of
the Binary Search Algorithm.
int Key = 22;
int p = Arrays.binarySearch( a , Key ); // 3
mismatch() : Finds and returns the index of the first unmatched element between
the two specified arrays.
int a[] = {10,20,15,22,35};
int b[] = {10,20,22,25,35};
S.o.p( Arrays.mismatch( a , b) ); // 2
compare() : Compares two arrays passed as parameters lexicographically.
int a[] = {10,20,30,66};
 int b[] = {10,20,31};
S.o.p(Arrays.compare(a,b); // -1
toString() : It returns a string representation of the contents of this array.
int a[] = {10,20,15,22,35};
System.out.println( Arrays.toString( a ) );
copyOf() : Copies the specified array, truncating or padding with the default value
(if necessary) so the copy has the specified length.
int a[] = {10,20,15,22,35};
int b[] = Arrays.copyOf( a , 5);
S.o.p( Arrays.toString(b) );
copyOfRange(array , start_index, end_index) : Copies the specified range of the
specified array into a new Array.
int b[] = Arrays.copyOfRange( a , 1 , 3 );
S.o.p( Arrays.toString(b) );
equals() : Checks if both the arrays are equal or not.
int a[] = { 10, 20, 15, 20};
int b[] = { 10, 20, 15 };
S.o.p( Arrays.equals( a , b ) ); // false
fill() : Assigns the fill value to each index of the array.
int a[] = new int[5];
Arrays.fill(a, 20);