Chapter 3:-Collection

Collections 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).

What is Collection in Java

A Collection represents a single unit of objects, i.e., a group.

What is a framework in Java

oIt provides readymade architecture.

oIt represents a set of classes and interfaces.

oIt is optional.

What is Collection framework

The Collection framework represents a unified architecture for storing and manipulating a group of objects. It has:

1.Interfaces and its implementations, i.e., classes

2.Algorithm

hierarchy of Collection Framework

Let us see the hierarchy of Collection framework. The java.util package contains all the classes and interfaces for the Collection framework.

Collection : Root interface with basic methods like add(), remove(),contains(), isEmpty(), addAll(), ... etc.

Set : Doesn't allow duplicates. Example implementations of Set    interface are HashSet (Hashing based) and TreeSet (balanced BST based). Note that TreeSet implements SortedSet.

List : Can contain duplicates and elements are ordered. Example implementations are LinkedList (linked list based) and   ArrayList (dynamic array based)

Queue : Typically order elements in FIFO order except exceptions like PriorityQueue. 

Deque : Elements can be inserted and removed at both ends. Allows   both LIFO and FIFO.

Map : Contains Key value pairs. Doesn't allow duplicates.  Example   implementation are HashMap and TreeMap. 

Java LinkedList class

Java LinkedList class uses a doubly linked list to store the elements. It provides a linked-list data structure. It inherits the AbstractList class and implements List and Deque interfaces.

The important points about Java LinkedList are:

oJava LinkedList class can contain duplicate elements.

oJava LinkedList class maintains insertion order.

oJava LinkedList class is non synchronized.

oIn Java LinkedList class, manipulation is fast because no shifting needs to occur.

oJava LinkedList class can be used as a list, stack or queue.

Constructors of Java LinkedList

LinkedList():-It is used to construct an empty list.

LinkedList(Collection c):- It is used to construct a list containing the elements of the specified collection, in the order, they are returned by the collection's iterator.

Methods of Java LinkedList

boolean add(E e):- It is used to append the specified element to the end of a list.

void addFirst(E e):- It is used to insert the given element at the beginning of a list.

void addLast(E e):- It is used to append the given element to the end of a list.

void clear():-It is used to remove all the elements from a list.

E getFirst():-It is used to return the first element in a list.

E getLast():-It is used to return the last element in a list.

import java.util.*; 

public class LinkedList1{ 

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()); 

} 

} 

}

java ArrayList class

Java ArrayList class uses a dynamic array for storing the elements. It inherits AbstractList class and implements List interface.

The important points about Java ArrayList class are:

oJava ArrayList class can contain duplicate elements.

oJava ArrayList class maintains insertion order.

oJava ArrayList class is non synchronized.

oJava ArrayList allows random access because array works at the index basis.

oIn Java ArrayList class, manipulation is slow because a lot of shifting needs to occur if any element is removed from the array list.

Constructors of Java ArrayList

ArrayList():-It is used to build an empty array list.

ArrayList(Collection c):- It is used to build an array list that is initialized with the elements of the collection c.

ArrayList(int capacity):- It is used to build an array list that has the specified initial capacity.

Methods of Java ArrayList

void add(int index, E element):- It is used to insert the specified element at the specified position in a list.

boolean add(E e):- It is used to append the specified element at the end of a list.

void clear():-It is used to remove all of the elements from this list.

boolean isEmpty():-It returns true if the list is empty, otherwise false.

int size():-It is used to return the number of elements present in the list.

import java.util.*; 

class ArrayList1

{ 

 public static void main(String args[])

 { 

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

list.add("Ravi");//Adding object in arraylist   

list.add("Vijay");   

list.add("Ravi");   

list.add("Ajay");   

//Invoking arraylist object  

System.out.println(list); 

} 

} 

} 

Difference between ArrayList and LinkedList

ArrayList

1)ArrayList internally uses a dynamic array to store the elements.

2) Manipulation with ArrayList is slow because it internally uses an array. If any element is removed from the array, all the bits are shifted in memory.

3)An ArrayList class can act as a list only because it implements List only.

4)ArrayList is better for storing and accessing data.

LinkedList:-

1)LinkedList internally uses a doubly linked list to store the elements.

2)Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory.

3)LinkedList class can act as a list and queue both because it implements List and Deque interfaces.

4)LinkedList is better for manipulating data.

Java Vector Class

Java Vector class comes under the java.util package. The vector class implements a growable array of objects. Like an array, it contains the component that can be accessed using an integer index.

Vector is very useful if we don't know the size of an array in advance or we need one that can change the size over the lifetime of a program.

Vector implements a dynamic array that means it can grow or shrink as required. It is similar to the ArrayList, but with two differences-

o Vector is synchronized.

o  The vector contains many legacy methods that are not the part of a collections framework

Java Vector Class Constructors

vector()-It constructs an empty vector with the default size as 10.

vector(int initialCapacity):- It constructs an empty vector with the specified initial capacity and with its capacity increment equal to zero.

vector(int initialCapacity, int capacityIncrement):- It constructs an empty vector with the specified initial capacity and capacity increment.

Vector( Collection<? extends E> c):- It constructs a vector that contains the elements of a collection c.

Vector class Methods:-

add():-It is used to append the specified element in the given vector.

addAll():-It is used to append all of the elements in the specified collection to the end of this Vector.

Capacity():-It is used to get the current capacity of this vector.

Clear():-It is used to delete all of the elements from this vector.

equals():-It is used to compare the specified object with the vector for equality.

get():-It is used to get an element at the specified position in the vector.

import java.util.Vector; 

public class VectorAddExample2

{   

public static void main(String arg[])

{ 

//Create vector object 

Vector vr = new Vector();

vr.add(0, "Java");

vr.add(1, "Android");

vr.add(2, "Python");

vr.add(3, "JavaTpoint");

vr.add(4, "Hindi100");

System.out.println("Vector is: " + vr); 

} 

} 

Output:

Vector is: [Java, Android, Python, JavaTpoint, Hindi100]

Set:-
A Set is a Collection that cannot contain duplicate elements. It models the mathematical set abstraction.
The Set interface contains only methods inherited from Collection and adds the restriction that duplicate elements are prohibited.
Set also adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set instances to be compared meaningfully even if their implementation types differ.

The methods declared by Set are summarized in the following table −
add( ):-Adds an object to the collection.
clear( ):-Removes all objects from the collection.
remove( ):-Removes a specified object from the collection.
size( ):-Returns the number of elements in the collection.

import java.util.*;
public class SetDemo
{
public static void main(String args[])
{
int count[] = {34, 22,10,60,30,22};
Set<Integer> set = new HashSet<Integer>();
try
{
for(int i = 0; i < 5; i++)
{
set.add(count[i]);
}
System.out.println(set);
TreeSet sortedSet = new TreeSet<Integer>(set);
System.out.println("The sorted list is:");
System.out.println(sortedSet);
System.out.println("The First element of the set is: "+ (Integer)sortedSet.first());
System.out.println("The last element of the set is: "+ (Integer)sortedSet.last());
}
catch(Exception e) {}
}
}

Java HashSet

Java HashSet class is used to create a collection that uses a hash table for storage. It inherits the AbstractSet class and implements Set interface.
The important points about Java HashSet class are:
oHashSet stores the elements by using a mechanism called hashing.
oHashSet contains unique elements only.
oHashSet allows null value.
oHashSet class is non synchronized.
oHashSet doesn't maintain the insertion order. Here, elements are inserted on the basis of their hashcode.
oHashSet is the best approach for search operations.

Difference between List and Set
A list can contain duplicate elements whereas Set contains unique elements only.

Constructors of Java HashSet class
HashSet():-It is used to construct a default HashSet.
HashSet(int capacity):- It is used to initialize the capacity of the hash set to the given integer value capacity. The capacity grows automatically as elements are added to the HashSet.

Methods of Java HashSet class
Add(E e):- It is used to add the specified element to this set if it is not already present.
Clear():-It is used to remove all of the elements from the set
isEmpty():-It is used to return true if this set contains no elements.
size():-It is used to return the number of elements in the set.
remove(Object o):- It is used to remove the specified element from this set if it is present.

import java.util.*;
class HashSet1
{
public static void main(String args[]){
//Creating HashSet and adding elements
HashSet<String> set=new HashSet();
set.add("One"); 
set.add("Two"); 
set.add("Three"); 
set.add("Four");
set.add("Five");
Iterator<String> i=set.iterator();
while(i.hasNext())
{
System.out.println(i.next());
}
}
}

Output:- Five
One
Four
Two
Three

Java TreeSet class

Java TreeSet class implements the Set interface that uses a tree for storage. It inherits AbstractSet class and implements the NavigableSet interface. The objects of the TreeSet class are stored in ascending order.

The important points about Java TreeSet class are:

oJava TreeSet class contains unique elements only like HashSet.

oJava TreeSet class access and retrieval times are quiet fast.

oJava TreeSet class doesn't allow null element.

oJava TreeSet class is non synchronized.

oJava TreeSet class maintains ascending order.

Constructors of Java TreeSet class

TreeSet():-It is used to construct an empty tree set that will be sorted in ascending order according to the natural order of the tree set.

TreeSet(Collection<? extends E> c):- It is used to build a new tree set that contains the elements of the collection c.

TreeSet(SortedSet<E> s):- It is used to build a TreeSet that contains the elements of the given SortedSet.

Methods of Java TreeSet class

add(E e):- It is used to add the specified element to this set if it is not already present.

addAll(Collection<? extends E> c):- It is used to add all of the elements in the specified collection to this set.

isEmpty():-It returns true if this set contains no elements.

int size():-It returns the number of elements in this set.

void clear():-It is used to remove all of the elements from this set.

E first():-It returns the first (lowest) element currently in this sorted set.

E last():-It returns the last (highest) element currently in this sorted set.

import java.util.*; 

class TreeSet1

{ 

public static void main(String args[])

{ 

//Creating and adding elements 

TreeSet<String> al=new TreeSet<String>(); 

al.add("Ravi"); 

al.add("Vijay"); 

al.add("Ravi"); 

al.add("Ajay"); 

//Traversing elements 

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

while(itr.hasNext()){ 

System.out.println(itr.next()); 

} 

} 

} 

Output:

Ajay

Ravi

Vijay

Java Hashtable class
Java Hashtable class implements a hashtable, which maps keys to values. It inherits Dictionary class and implements the Map interface.

Points to remember
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.

Hashtable class Parameters
K: It is the type of keys maintained by this map.
V: It is the type of mapped values.

Constructors of Java Hashtable class
Hashtable():-It creates an empty hashtable having the initial default capacity and load factor.
Hashtable(int capacity):- It accepts an integer parameter and creates a hash table that contains a specified initial capacity.
Hashtable(int capacity, float loadFactor):- It is used to create a hash table having the specified initial capacity and loadFactor.

Methods of Java Hashtable class
void clear():-It is used to reset the hash table.
int size():-This method returns the number of entries in the hash table.
V remove(Object key):- It is used to remove the key and its value. This method returns the value associated with the key.
isEmpty():-This method returns true if the hash table is empty; returns false if it contains at least one key.

import java.util.*;
public class Hashtable2
{
public static void main(String args[])
{
Hashtable<Integer,String> map=new Hashtable<Integer,String>();     
map.put(100,"Amit"); 
map.put(102,"Ravi"); 
map.put(101,"Vijay"); 
map.put(103,"Rahul"); 
System.out.println("Before remove: "+ map); 
// Remove value for key 102
map.remove(102);
System.out.println("After remove: "+ map);
}   
}

Output:
Before remove: {103=Rahul, 102=Ravi, 101=Vijay, 100=Amit}
After remove: {103=Rahul, 101=Vijay, 100=Amit}

Java Map Interface
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.
A Map is useful if you have to search, update or delete elements on the basis of a key.

Useful methods of Map interface
V put(Object key, Object value):- It is used to insert an entry in the map.
void putAll(Map map):- It is used to insert the specified map in the map.
V remove(Object key):- It is used to delete an entry for the specified key.
void clear():-It is used to reset the map.
int hashCode():-It returns the hash code value for the Map
int size():-This method returns the number of entries in the map.
V replace(K key, V value):- It replaces the specified value for a specified key.

import java.util.*;
public class MapExample1
{
public static void main(String[] args)
{
Map map=new HashMap();
map.put(1,"Amit");
map.put(5,"Rahul");
map.put(2,"Jai");
map.put(6,"Amit");
System.out.println(“Map Elements”);
System.out.println(+map);
}
}

Java HashMap class

Java HashMap class implements the map interface by using a hash table. It inherits AbstractMap class and implements Map interface.

Points to remember

oJava HashMap class contains values based on the key.

oJava HashMap class contains only unique keys.

oJava HashMap class may have one null key and multiple null values.

oJava HashMap class is non synchronized.

oJava HashMap class maintains no order.

HashMap class Parameters

oK: It is the type of keys maintained by this map.

oV: It is the type of mapped values.

Constructors of Java HashMap class

HashMap():-It is used to construct a default HashMap.

HashMap(int capacity):- It is used to initializes the capacity of the hash map to the given integer value, capacity.

Methods of Java HashMap class

void clear():-It is used to remove all of the mappings from this map.

boolean isEmpty():-It is used to return true if this map contains no key-value mappings.

void putAll(Map map):- It is used to insert the specified map in the map.

boolean equals(Object o):- It is used to compare the specified Object with the Map.

int size():-This method returns the number of entries in the map.

import java.util.*; 

class HashMap1

{ 

public static void main(String args[])

{ 

HashMap<Integer,String> hm=new HashMap<Integer,String>();   

System.out.println("Initial list of elements: "+hm); 

hm.put(100,"Amit");   

hm.put(101,"Vijay");   

hm.put(102,"Rahul");  

System.out.println("After invoking put() method "); 

for(Map.Entry m:hm.entrySet())

{   

System.out.println(m.getKey()+" "+m.getValue());   

} 

}

}

Java TreeMap class

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

The important points about Java TreeMap class are:

oJava TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.

oJava TreeMap contains only unique elements.

oJava TreeMap cannot have a null key but can have multiple null values.

oJava TreeMap is non synchronized.

oJava TreeMap maintains ascending order.

TreeMap class Parameters

oK: It is the type of keys maintained by this map.

oV: It is the type of mapped values.

Constructors of Java TreeMap class

TreeMap():-It is used to construct an empty tree map that will be sorted using the natural order of its key.

TreeMap(Comparator<? super K> comparator):- It is used to construct an empty tree-based map that will be sorted using the comparator comp.

Methods of Java TreeMap class

void clear():-It removes all the key-value pairs from a map.

int size():-It returns the number of key-value pairs exists in the hashtable.

K firstKey():-It is used to return the first (lowest) key currently in this sorted map.

K lastKey():-It is used to return the last (highest) key currently in the sorted map.

Collection values():-It returns a collection view of the values contained in the map.

import java.util.*; 

class TreeMap1{ 

public static void main(String args[])

{ 

TreeMap<Integer,String> map=new TreeMap<Integer,String>();   

map.put(100,"Amit");   

map.put(102,"Ravi");   

map.put(101,"Vijay");   

map.put(103,"Rahul");   

for(Map.Entry m:map.entrySet())

{   

System.out.println(m.getKey()+" "+m.getValue());   

}   

} 

} 

Output:100 Amit

       101 Vijay

       102 Ravi

       103 Rahul

Difference between HashMap and Hashtable

HashMap

1)HashMap is non synchronized. It is not-thread safe and can't be shared between many threads without proper synchronization code.

2)HashMap allows one null key and multiple null values.

3)HashMap is fast.

4)HashMap is traversed by Iterator.

5)Iterator in HashMap is fail-fast.

6)HashMap inherits AbstractMap class.

HashTable

1)Hashtable is synchronized. It is thread-safe and can be shared with many threads.

2)Hashtable doesn't allow any null key or value.

3)Hashtable is slow.

4)Hashtable is traversed by Enumerator and Iterator.

5)Enumerator in Hashtable is not fail-fast.

6)Hashtable inherits Dictionary class.

Difference between ArrayList and Vector

ArrayList

1)ArrayList is not synchronized.

2)ArrayList increments 50% of current array size if the number of elements exceeds from its capacity.

3)ArrayList is fast because it is non-synchronized.

4)ArrayList uses the Iterator interface to traverse the elements

Vector:-

1)Vector is synchronized.

2)Vector increments 100% means doubles the array size if the total number of elements exceeds than its capacity.

3)Vector is slow because it is synchronized, i.e., in a multithreading environment, it holds the other threads in runnable or non-runnable state until current thread releases the lock of the object.

4)A Vector can use the Iterator interface or Enumeration interface to traverse the elements