An Introduction to Collection

collection

collection is an interface that is used to represent a group of a homogeneous or heterogeneous object into a single unit. they are growable in nature. collection can hold only objects but not primitive data.

Collections

collections is a utility class that is used to present in java. util package to define several utility methods for collection objects.

collection framework

collection framework is used to define several classes and interfaces that are used to represent a group of objects as a single entity.

List

List is a child interface of the Collection interface. if we want to represent a group of an individual object into a single unit and duplicates objects is allowed then go for List interface. it supports the index-based search and elements can be easily inserted irrespective of position.it contains ordered elements.

ArrayList

ArrayList is a class that implements List interface and growable in nature and when ArrayList size is full it increases its size 50%. in Arraylist Null Insertion is possible. ArrayList is non-synchronized in nature.

import java.io.*;
import java.util.*;

class test {
    public static void main(String[] args)
    {

        List<Integer> list = new ArrayList<Integer>();

            list.add(1);
            list.add(2);
            list.add(6);
            list.add(4);

        System.out.println(list);

        list.remove(3);

        System.out.println(list);

        for (int i = 0; i < list.size(); i++)
            System.out.print(list.get(i) + " ");
    }
}

the time complexity of the common operations performed on Arraylist is—

add()- takes O(1) time to perform the add operation.

Add(index,element)- is always constant time O(1)to perform .

removes()- run in O(n) times take to remove an elements from ArrayList.

indexOf()- runs in linear times and takes O(n) time.

get()- is O(1) constant-time taken in get the element operations operation .

contains()- O(n) time is taken to check an item is present or not.

next()- O(1) time is taken to find next elements in ArrayList.

LinkedList

LinkedList class implements List and Deque interface.in LinkedList. this class is the implementation of the LinkedList data structure . in LinkedList data structure elements are not stored in contiguous memory locations and every element is an object with data part and address part known as a node. and objects are linked together with an address or pointer. it not supports accessed the objects randomly. using ListIterator we have to iterate the LinkedList elements.

the time complexity of the common operations —

Add(index, element)- is always constant time O(1) to add an element at a specific index.

removes()- to remove an element from the linked list in O(n) times.

get()- to get an element from specific index is O(1) constant-time operation.

contains()- o get an element from linked list take O(n) time complexity.

next()- O(1) time is taken to find the next elements in LinkedList.

import java.io.*;
import java.util.*;

class test {
    public static void main(String[] args)
    {

        List<Integer> ll = new LinkedList<Integer>();
            ll.add(1);
             ll.add(2);
             ll.add(7);
             ll.add(6);
             ll.add(1);


        System.out.println(ll);
        ll.remove(3);
        System.out.println(ll);
        
        for (int i = 0; i < ll.size(); i++)
            System.out.print(ll.get(i) + " ");
    }
}

Vector

Vector is a class that implements a list interface it is a legacy class that is present since JDK 1.0. it allowed Duplicates elements and insertion order is preserved. Vector is dynamic in size it doubles its capacity when vector size is full.it synchronized in nature (it allowed one thread at a time and others are in the waiting area).

import java.io.*;
import java.util.*;

class test {
    public static void main(String[] args)
    {
        List<Integer> v = new Vector<Integer>();

        v.add(1);
        v.add(2);
        v.add(5);
        v.add(19);
        v.add(1);

        System.out.println(v);

        v.remove(3);

        System.out.println(v);

        for (int i = 0; i < v.size(); i++)
            System.out.print(v.get(i) + " ");
    }
}

Stack

Stack is a child class of vector class. it is used to implements stack data structure. the Stack class is based on the first-in last-out principle. elements are added and removed both operations are from the rear end.

import java.io.*;
import java.util.*;

class test {
    public static void main(String[] args)
    {
        List<Integer> s = new Stack<Integer>();
            s.add(1);
            s.add(2);
            s.add(3);
            s.add(5);
        System.out.println(s);
        s.remove(3);

        System.out.println(s);

        for (int i = 0; i < s.size(); i++)
            System.out.print(s.get(i) + " ");
    }
}

Queue

Queue is a child interface of the Collection interface. usually, Queue follows first-in and the first-out approach but based on our requirements we can implement our own order. in Queue, elements are stored at the rear point and remove from the front end.

PriorityQueue

PriorityQueue is a class that implements Queue interface. it allows priority associated with each element. high priority element is stored before low priority elements irrespective of their insertion order.in priorityQueue insertion order is not preserved but all elements are stored according to some priority.

the time complexity of the common operations performed by PriorityQueue—

offer(E e)- insert the specific element in queue and time complexity isO(log n).

peak()-used to retrieve or fetch the first element of the Stack and time complexity is O(1).

poll()- removes the element at the front of the container and time complexity isO(1).

remove()- remove the elements and time complexity is O(h/n).

size()- return the size and time complexity is O(1).

import java.util.LinkedList;
import java.util.Queue;

public class test {

    public static void main(String[] args)
    {
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < 5; i++)
            q.add(i);

        System.out.println( q);
        int removedele = q.remove();
        System.out.println(removedele);

        System.out.println(q);

        int head = q.peek();
        System.out.println(head);

              int size = q.size();
        System.out.println( size);
    }
}

Deque

Deque is an interface that refers to the double-ended queue. it is a linear collection that allows the insertion and deletion of the element from both ends. it can either be used for the implementation of the stack or for the queue data structure.

ArrayDeque

ArrayDeque is a class that implements the Deque interface. it provides a way to make a resizeable array and there is no capacity restriction. they are not synchronized in nature.

the time complexity of the common operations —

offer(E e)- insert the specific element in queue and time complexity is O(1).

peak()- used to retrieve or fetch the first element of the Stack and time complexity is O(1).

poll()- removes the element at the front of the container and time complexity is O(1).

remove()- remove the elements and time complexity is O(h/n).

size()- return the size and time complexity is O(1).

import java.util.*;
public class test {
    public static void main(String[] args)
    {
        Deque<Integer> de= new ArrayDeque<Integer>();

        de.add(10);
        de.add(20);
        de.add(30);
        de.add(40);
        de.add(50);

        System.out.println(de);
        de.clear();
        de.addFirst(291);
        de.addLast(24);
        de.addLast(14);

        System.out.println(de);
    }
}

Set

Set is the child Interface of the collection framework. set does not allow duplicates elements and does not allow a defined order for the elements (insertion order is not preserved) hence index-based search is not allowed.

HashSet

HashSet is a class that implements the Set interface. the underlying data structure of the set is Hashtable. Set contains only unique elements and only one null value can be added. the insertion order is based on the hash code of objects.

the time complexity of the common operations performed in HashSet—

add()- takes O(1) time to add elements in set.

removes()- run in O(1) times to remove an elements.

size()- O(1) time complexity to find the size of the set.

contains()- O(1) time is taken in this operations .

next()- O(h/n) time is taken in this operation.

import java.util.*;

class test{

    public static void main(String[] args)
    {
        Set<String> h = new HashSet<String>();

        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");

        System.out.println(h);

        h.remove("Australia");
        System.out.println(h);
        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

LinkedHashSet

LinkedHashSet is a child class of HashSet. it is an ordered version of hashset which maintains a doubly-linked list across all elements.it preserved the insertion order of set elements.

the time complexity of the common operations in linkedlistset—

add()- takes O(1) time to add elements in set.

removes()- run in O(1) times to remove an elements.

size()- O(1) time complexity to find the size of the set.

contains()- O(1) time is taken in this operations .

next()- O(1) time is taken in this operation.

import java.util.*;

class test {

    public static void main(String[] args)
    {
        Set<String> h = new LinkedHashSet<String>();

        h.add("India");
        h.add("Australia");
        h.add("South Africa");
        h.add("India");

        System.out.println(h);

        h.remove("Australia");
        System.out.println(h);

        Iterator<String> i = h.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

SortedSet

SortedSet is a child interface of a set interface. in SortedSet a group of elements is present according to some sorting of order. the sorting order can be either natural sorting or customized sorting.

TreeSet

TreeSet is a class that implements the SortedSet interface. it is the underlying data structure for the balanced tree. in TreeSet duplicates elements are not allowed and insertion order is not preserved. insertion is based on some sorting order of elements.

the time complexity of the common operations in TreeSet—

add()- takes O(log n) time to add elements in set.

removes()- run in O(log n) times to remove an elements.

size()- O(1) time complexity to find the size of the set.

contains()- O(log n) time is taken in this operations .

next()- O(log n) time is taken in this operation.

import java.util.*;

class test {
    public static void main(String[] args)
    {
        Set<String> t= new TreeSet<String>();
        t.add("India");
        t.add("Australia");
        t.add("South Africa");
        t.add("India");

        System.out.println(t);
        t.remove("Australia");
        System.out.println(t);

        Iterator<String> i = t.iterator();
        while (i.hasNext())
            System.out.println(i.next());
    }
}

Map

Map is an interface it is not the child interface of collection and hence we can not apply collection interface methods on Map. Map represents a key-value pair of objects. The map can only contain a unique key but have duplicates value.

HashMap

HashMap is a class that implements the Map interface. the underlying data structure is hashtable. The map is non -synchronized in nature. only one null value is allowed for the key but multiple nulls is allowed for values.

the time complexity of the common operations for HashMap—

get()- O(1) time complexity to get an element.

ContainsKey()- O(1) time complexity to find that key contains or not.

next()- O(h/n) time is taken in this operation.

import java.util.*;

public class test {

    public static void main(String[] args)
    {
        Map<String, Integer> map = new HashMap<>();

        map.put("vishal", 10);
        map.put("sachin", 30);
        map.put("abhi", 20);

        for (Map.Entry<String, Integer> e : map.entrySet())
            System.out.println(e.getKey() + " "
                    + e.getValue());
    }
}

HashTable

HashTable is a class that is synchronized in nature and null is not allowed for both key and value. Retaviley performance-wise low then HashMap.

import java.util.*;

public class test{

    public static void main(String[] args)
    {
        Map<String, Integer> map = new LinkedHashMap<>();

        map.put("vishal", 10);
        map.put("shashank", 30);
        map.put("abhi", 20);

        for (Map.Entry<String, Integer> e : map.entrySet())
            System.out.println(e.getKey() + " "
                    + e.getValue());
    }
}

SortedSet

SortedSet is the child Interface of Map. SortedSet is used to represent a group of key-value pairs according to some sorting order of key. sorting is possible only based on the keys but not based on values.

TreeMap

TreeMap is a class that is used to implements the SortedSet interface. TreeMap implicitly implements the red-black tree. Duplicate keys are not allowed but the value can be Duplicates.

the time complexity of the common operations in TreeSet—

get()- O(log n) time complexity to get an element.

ContainsKey()- O(log n) time complexity to find that key contains or not.

next()- O(log n) time is taken in this operation.

import java.util.*;

public class test {

    public static void main(String[] args)
    {
        Map<String, Integer> map = new TreeMap<>();

        map.put("vishal", 10);
        map.put("samarth", 30);
        map.put("vaibhav", 50);

        for (Map.Entry<String, Integer> e : map.entrySet())
            System.out.println(e.getKey() + " " + e.getValue());
    }
}