Collection Framework in Java

• A Collection allows a group of objects to be treated as a single unit

• Java Collection Framework provides a set of utility classes for managing various kinds of collections

The collection interface extends the Iterable interface that specifies an iterator to sequentially access the elements of the Iterable Object

Hierarchy of Map interface

Creating Customized generic List

Now we will create our own Customized generic List which Implements Iterables and behaves the same as Array List

package base;

import java.util.Iterator;

public class OurGenericList<T> implements Iterable<T>{

    private T[] items;
    private int size;

    public OurGenericList() {
        size=0;
        items=(T[]) new Object[100];
    }

    public void add(T item) {
        items[size++]=item;
    }

    public T getItemIndex(int index) {
        return items[index];
    }

    public int size() {
        return size;
    }

    @Override
    public Iterator iterator() {
        // TODO Auto-generated method stub

        return new OurGenericIterator(this);
    }
    private class OurGenericIterator implements Iterator<T>{

        private OurGenericList<T> ourGenericList;
        private int index=0;

        OurGenericIterator( OurGenericList<T> ourGenericList){
            this.ourGenericList=ourGenericList;
        }

        @Override
        public boolean hasNext() {
            // TODO Auto-generated method stub

            return index< ourGenericList.size();
        }

        @Override
        public T next() {
            // TODO Auto-generated method stub
            return ourGenericList.items[index++];
        }

    }

}

//Main Class

package base;

import java.util.Iterator;

public class driverclass {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        OurGenericList<Integer> al=new OurGenericList<>();
        al.add(10);
        al.add(20);
        al.add(30);
        al.add(40);

        Iterator<Integer> iterator=al.iterator();
        while(iterator.hasNext()) {
            System.out.println(iterator.next());
        }
    }
}

The reason why collection extends Iterable is The other classes which extends collection can be Iterable. we can use for each loop to traverse

List :

• Lists are collections that maintain their elements in order and can contain duplicates

• The elements in List are ordered

• Each elements are position based starting from 0

List Methods :

E get(index)

E set(index, element)

void add(int index, element)

boolean AddAll(int index,collection<? extends e> c)

E remove(int index)

Implementations of List

implementations of List are provided in Java.util package

1. Array List

2. Linked List

3. Vector

Array List

Array List is a dynamic array, and will use when we don't know the size

internally it uses some array set to some default size

when the capacity is reached it will create a new Array of bigger sizes (50 % of its current capacity) and copy all the elements from the old array to the new Array

New Array reference for its internal usage

As the old array is no longer in use,and is Garbage collected in the next garbage collection

Vector Class

The vector class is a legacy class that implements Array List

Unlike ArrayList, Vector is thread-safe ie concurrent calls to vector will not compromise its integrity

Linked List

1. Linked list implements uses doubly linked list

2. Insertions and deletions are very efficient in a doubly linked list

Array List Vs Linked List

Position-based access has a constant time performance in Array list and Vector class

whereas in Linked List it will take linear time

for insertions and deletion Linked list is better choice when compared to Array List and vector

In addition to List Interface Linked also implements Dequee which help in creating stacks and Queues

Example on ArrayList

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        System.out.println("Hello World");
        List<Integer> al1=new ArrayList<>();
        al1.add(10);
        al1.add(20);
        al1.add(30);
        al1.add(40);
        List<Integer> al2=new ArrayList<>(al1); // To create a copy of Array List . and we can pass any collection here
        al2.add(50);
        System.out.println(al1);
        System.out.println(al2);

    }
}

by using the AddAll method

import java.util.*;
public class Main
{
    public static void main(String[] args) {
        System.out.println("Hello World");
        List<Integer> al1=new ArrayList<>();
        al1.add(10);
        al1.add(20);
        al1.add(30);
        al1.add(40);
        List<Integer> al2=new ArrayList<>();
        al2.add(100);
        al2.addAll(al1);
        System.out.println(al1);
        System.out.println(al2);
        System.out.println(al2.indexOf(100)); // To get Index of a particular element
         List<Integer> al3=al2.subList(0,4);
        System.out.println(al3);
        al3.set(0,999);
       // System.out.println(al1);
        System.out.println(al2);
        System.out.println(al3);

    }
}

Note: In the above example if we change the subset it will affect the actual Array List

List Iterator :

List Iterator is an Interface that implements Iterator, we can travel in a bidirectional way by using Previous method

next() returns an element and then moves to next position

previous() first moves and then return element

Queues :

The Queue interface extends the collection interface with the following methods

• boolean add(E element) // throws illegal state exception if Queue is full

• boolean offer(E element) // it does not throw any exception it just return false

• E poll() // if queue is empty it will return null

• E remove() // If the Queue is empty, it will throw a NoSuchElement Exception.

E peek()

Deque :

1. The Deque interface extends the Queue interface to allow double-ended queues

2. It allows operations not just at its head , but also at its tail

3. Elements can be inserted or removed from either end

Adding elements :

1. boolean offerFirst

2. boolean offerLast

3. Void push

4. void addFirst

5. void addLast

    import java.util.*;
    public class Main
    {
        public static void main(String[] args) {
            Queue<Integer> q=new LinkedList<>();
            q.offer(1);
            q.offer(2);
            q.offer(3);
            System.out.println(q.peek()); //1
            System.out.println(q.poll()); //1
            System.out.println(q.peek()); //2
        }
    }
   

   Stack Implementation using Deque

             Deque<Integer> q=new ArrayDeque<>();
              q.addFirst(10);
              q.addFirst(20);
              q.addFirst(30);
              System.out.println(q);
              System.out.println(q.peek());
              System.out.println(q.removeFirst());
   

Queue implementation using Deque

   Deque<Integer> q=new ArrayDeque<>();
          q.addFirst(10);
          q.addFirst(20);
          q.addFirst(30);
          System.out.println(q);
          System.out.println(q.peek());
          System.out.println(q.removeLast());

Priority Queue :

Priority Queue works on priority

The implementation is based on priority heap. a tree like structure that yields an element at the head of the queue according to priority order. which is defined as the natural sorting order of the comparator

In case of several elements having the same priority one of them is choosen arbitrarily

Elements of the priority queue are not sorted

Program to display the top 2 elements from the queue

PriorityQueue<Integer> pq=new PriorityQueue<>();
pq.offer(10);
pq.offer(20);
pq.offer(5);
pq.offer(0);
pq.offer(50);

ArrayList<Integer> al=new ArrayList<>();
int index=0;
while(!pq.isEmpty()){
     if(index==2)
        break;
     al.add(pq.poll());
    index++;
}

The above program displays top 2 elements in Ascending order . because PriorityQueue internally implements Comparable which is sorting in ascending order.

The generic type of priority queue must be type of Comparable class other it will class cast exception. Internally integer extends Comparable

if we want to overwrite the behavior pass it as argument to priority queue

class Descending implements Comparator<Integer>
{
    public int compare(Interger I1,Integer I2){
        if(I1<I2)
          return 1;
        else if(I1>I2)
          return -1;
        else
          return 0;
    }
}
class main{
    public static void main(String args[]){
        PriorityQueue<Integer> pq=new PriorityQueue<>(new Descending());
        pq.offer(10);
        pq.offer(20);
        pq.offer(5);
        pq.offer(0);
        pq.offer(50);

        ArrayList<Integer> al=new ArrayList<>();
        int index=0;
        while(!pq.isEmpty()){
             if(index==2)
                break;
             al.add(pq.poll());
            index++;
        }
    }
}

In the above code, we are passing new Descending() as argument hence it will overide natural behavior, and it will sort in Descending Order

The same code can also be written by using lambda expression

PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->b-a);

By using the above lambda expression we are sorting in Descending order

Total ordering is given priority over Natural Ordering

The same can be applied to customized class . if we want to sort in a particular field

class Student implements Comparable<Student>
{
    private int Maths;
    private int Physics;
    private int chemistry;
    public int compareTo(Student o){
        return o.physics-this.physics;
    }
}

class Descending implements Comparator<Student>
{
    public int compare(Student I1,Student I2){
        if(I1.getMaths()<I2.getMaths())
          return 1;
        else if(I1.getMaths()>I2.getMaths())
          return -1;
        else
          return 0;
    }
}
class main{
    public static void main(String args[]){
        PriorityQueue<Integer> pq=new PriorityQueue<>(new Descending());
        pq.offer(10);
        pq.offer(20);
        pq.offer(5);
        pq.offer(0);
        pq.offer(50);

        ArrayList<Integer> al=new ArrayList<>();
        int index=0;
        while(!pq.isEmpty()){
             if(index==2)
                break;
             al.add(pq.poll());
            index++;
        }
    }
}

In the above example, Natural ordering is based on Physics Marks in Descending order but we have overwritten in Total order by using Maths Marks in Ascending order

Sets :

Set is collection of elements which does not allow duplicates , if we try to add duplicates also it does not print

Set<Integer> hs=new HashSet<>();
hs.add(10);
hs.add(20);
hs.add(30);
hs.add(10);
System.out.println(hs)
hs.remove(20) // it will remove element from the set
// Out put wont contain duplicates

Sets contain following methods :

1. a.containsAll(b)

2. a.addAll(b)

3. a.removeAll(b)

4. a.retainAll(b)

5. a.clear()

public static void main(String[] args) {
        System.out.println("Hello World");
        Set<Integer> hs1=new HashSet<>();
        hs1.add(10);
        hs1.add(20);
        hs1.add(30);

        System.out.println(hs1);

        Set<Integer> hs2=new HashSet<>();
        hs2.add(10);
        hs2.add(20);
        hs2.add(50);

        hs1.retainAll(hs2); // It will give intersection in hs1
        System.out.println(hs1);

         hs1.addAll(hs2); // It will give Union in hs1
        System.out.println(hs1);

    }

Linked Hash Set :

The linked Hash set is extension of Hash set. if we traverse the Linked hash set insertion order is maintained

public class Main
{
    public static void main(String[] args) {
        System.out.println("Hello World");
        Set<Integer> hs1=new LinkedHashSet<>();
        hs1.add(10);
        hs1.add(20);
        hs1.add(30);
        hs1.add(10)
        System.out.println(hs1);
    }
}

What if we add Customized objects to hashSet

The basic principle of hashmap is doesn't allow duplicate but if we add same customized object twice it will allow because it has diffrent address, for that we will override Hashcode and equals method

  import java.util.*;
class Student
{
    int id;
    int age;
    String name;
    Student(int id,int age,String name){
        this.id=id;
        this.age=age;
        this.name=name;
    }
    public int hashCode(){
        return this.id+this.age+this.name.hashCode();
    }
    public boolean equals(Object s1){
        return this.id==((Student)s1).id && 
        this.age==((Student)s1).age && 
        this.name.hashCode()==((Student)s1).name.hashCode();
    }
}
public class Main
{
    public static void main(String[] args) {

        HashSet<Student> hs=new HashSet<>();
        hs.put(new Student(101,23,"Sunil"));
        hs.put(new Student(101,23,"Sunil"));
        hs.put(new Student(101,23,"Sunil"));
        hs.put(new Student(101,23,"Sunil"));

        for(Student s:hs){
            System.out.println(hs)
        }
    }
}

Sorted Set :

1. the sorted set interface extends the set interface to provide the functionality for Handling sorted sets

2. Since elements are sorted, traversing the set either using the for(:) loop or an iterator will access the elements according to the ordering used by the set

E first()

E last()

Navigable Set Interface :

Extends the SortedSet Interface with navigation methods to find the closest match for specific search targets

pollFirst()

pollLast()

E celing(); // for closest match

E floor();

Tree set :

Tress Set will sort in Ascending order by default , if we want any customized sorting we will pass that in total ordering

Map Interface:

Basically Map stores values in form of Keys and Values,

Hash Map allows one null key , it does not allow duplicates

Tree Map Sorts the records in the ascending order of keys , if we sort in customized order we need to pass in total ordering

We cant iterate through Map as it doesnt iterate Iterable

By using Map.Entry we will process the records

if a Map has customized object as key, then we can insert a duplicate as it has a different base address, Then we will override Model class hasCode and Equals method

Example

import java.util.*;
class Student
{
    int id;
    int age;
    String name;
    Student(int id,int age,String name){
        this.id=id;
        this.age=age;
        this.name=name;
    }
    public int hashCode(){
        return this.id+this.age+this.name.hashCode();
    }
    public boolean equals(Object s1){
        return this.id==((Student)s1).id && 
        this.age==((Student)s1).age && 
        this.name.hashCode()==((Student)s1).name.hashCode();
    }
}
public class Main
{
    public static void main(String[] args) {

        HashMap<Student,Integer> hm=new HashMap<>();
        hm.put(new Student(101,23,"Sunil"),1);
        hm.put(new Student(101,23,"Sunil"),2);
        hm.put(new Student(101,23,"Sunil"),3);
        hm.put(new Student(101,23,"Sunil"),4);

        System.out.println("The final values in the map is");
        for(Map.Entry<Student,Integer> me: hm.entrySet()){
            System.out.println(me.getKey().name+" "+me.getKey().age+" "+ me.getKey().id+" "+me.getValue());
        }
        System.out.println("The final size of the map is");
        System.out.println(hm.size());
    }
}