Collection framework in Java

on
Collection Framework In Java

Overview:

  • Collection framework in java provides various ready to use classes and Interfaces along with their methods to use various data structures like List, Stack, Queue, etc. so we don't have to reinvent the wheel by implementing them from scratch.
  • The classes and Interfaces provided by Collection frameworks, use to create a single object that represent a group of data elements/objects, using that single object we can store, access and manipulate data elements/objects.
  • As we know in Java to use any predefine class or interface, we have to import it in our code using packages. so, to use Collection in our code we have to import java.util.Collection package.

Various classes and Interfaces provided by Collection framework are:

  Classes     Interfaces  
  ArrayList     Collection  
  LinkedList     List  
  Vector     Queue  
  Stack     Deque  
  PriorityQueue     Set  
  ArrayDeque     SortedSet  
  HashSet  
  LinkedHashSet  
  TreeSet  

Some Interesting points:

  • Map not comes under collection framework. Both Map and Collection are different from each other.
  • Collection Interface extends Iterable interface, this is why we can use for-each loop with various classes and interfaces comes under collection.

  • As shown in above diagram, Collection Interface is super interface, all classes and interface implements or extends it.
  • Collection Interface contains below methods so all sub classes implements all these methods according to their usage requirement.

  • All above are abstract methods and below are default methods introduces in Java 8.

List Interface

  • It extends Collection interface.
  • It is used to represent list data structure.
  • Store data/objects/elements in order.
  • It can have duplicate values.
  • It can be implemented by various Classes such as ArrayList, LinkedList, Vector, Stack.
  • It contains all the methods that Collection Interface have.

ArrayList

  • It implements List Interface by internally storing the elements in array.
  • ArrayList are dynamic in size, It will increase its size/capacity automatically whenever we add elements in it.
  • As we know array are of fixed length/size and ArrayList uses arrays but we are still saying it dynamic ,how?
    • The answer of this question is while we create an ArrayList object, it create an array of size 10.10 is default size. As we add more and more elements, the size/capacity of ArrayList increases by using Load factor (default load factor value is 0.75f).
    • So, how Load factor helps here. Using it we can calculate the threshold.
    • i.e. threshold = current capacity * Load factor.
    • Now, whenever we add elements to ArrayList It calculate the threshold and compare it with current size, if it found threshold < current size , it creates a new copy of array with size ((3 * old size)/2) and copy all elements in it.so, we already knows that It is not mandatory to give a intial storage size to List. But it will be consider as a good practice to give a initial size for efficient cpu memory utilizations.
  • Using ArrayList we can access elements randomly using their indexes so it is fast and acessing an element will have time complexity of O(1).
  • ArrayList is not synchronized. It means that multiple threads can access and modify it at same time. Unlikely, vector is synchronized and hence thread safe. It can also inferred a fact that ArrayList is fast as compare to vector.
  • ArrayList maintains the insertion order of elements.
  • If our application requirement is just to store elements and access elements based on indexes then ArrayList will be best choice.
  • ArrayList contains duplicate values and also can contains null value.

LinkedList

  • It implement List Interface to represent LinkedList datastructure (Linked List is linear data structure having group of nodes at random memory locations, each node refer its next neighbor node using pointer).
  • LinkedList Class internally uses DoublyLinked list to implement List interface.(Doubly Linked list is also linear data structure having group of nodes like LinkedList,but here each node can refer to its previous and next neighbour nodes.).In Java, Node is represented by a static class having 3 attributes that are value, left/previous pointer and right/next pointer where value store the data and pointers store the reference of nodes.
  • Like ArraysList, LinkedList can contain duplicate value, null value, not synchronize.
  • UnLike ArrayList, We can not access data randomly. but in LinkedList remove operation is very fast as compare to ArrayList (here in LinkedList it just a matter of changing pointer references rather than shifting elements from there positions).
  • LinkedList also have all operations that we have in ArrayList (I.e. add(), remove(), get()) but apart from these we have some additonal methods also in LinkedList that are,
    • addFirst() : add element at First position in LinkedList
    • addLast() : add element at Last position in LinkedList
    • getFirst() : get element from First position in LinkedList
    • getLast() : get element from Last position in LinkedList
    • removeFirst() : remove element from First position in LinkedList
    • removeLast() : remove element from Last position in LinkedList

    All the above method is due to DoublyLinked List and can be accessible only when we use below approach,

    LinkedList list = new LinkedList<>();
    list.add("ABC");
    list.addFirst("ABC");
    list.addLast("ABC");


    Not work if we try to access them using below approach,

    List list = new LinkedList<>();
    list.add("ABC"); // it will work
    list.addFirst("ABC"); // it will give error
    list.addLast("ABC"); // it will give error

    So using List Interface we can only access common methods.

  • Apart from List interface, LinkedList can also implement Queue, Dequeu Interface as well.
  • LinkedList will be best to use in such scenario where we require to use remove operation heavily.

Vector

  • Vector is one of legacy class in java and also conatins many methods that are not the part of collection framework.
  • It is almost similar to ArrayList with some differences as mentioned below.
  • Unlike ArrayList, Vector is synchronized. That is multiple threads can not access and manipulate the content at same time, hence it is called as thread safe.
  • So, It is advisable to use vector in case of synchronization only. Otherwise we should use ArrayList or LinkedList.
  • Vector have various signature for constuctors, all these LinkedList or ArrayList also have except below one.
    • new Vector(int capacity, int capacityIncrement); // using this we can define our own capacity and capacityIncrement size and thus we can control the amount of Incremental allocation.

Stack

  • It is subclass of Vector.
  • It represents Stack data structure, the linear data structure that uses the concept of LIFO (Last In First Out).
  • As it extends Vector so it contains all the method of Vector class. Apart from these it also have its own key methods, some of them mentioned below and are accessible by Stack class variable only not List interface variable.
    • push(Object obj) // It insert the object into stack.
    • pop() // it remove the top element or recently inserted element from the stack.
    • peek() // It just give the value of top element and not remove that.
    • empty() // return true if empty else return false
    • search(Object obj) // search for object in stack if found return its distance from top else will return –1. It consider top as at position 1 and not 0.
  • As Stack extends Vector and Vector is thread safe so Stack is also thread safe. so it will be inefficient in the environment where thread safety not require. so to overcome this problem we have an alternate of Stack that is Deque.

Queue

  • It extends Collection interface.
  • It represents Queue data structure, the linear data structure that works on the principle of FIFO (First In First Out).
  • Queue is an Interface and we can not create objects of Interface. so for its declaration we have to use concrete classes like PriorityQueue and LinkedList that implement it.

PriorityQueue

  • It implements Queue interface.
  • It represents Min Heap datastructure.Min heap is tree kind data structure (we can say complete binary tree) where each node value must be smaller or equal to its children node.
  • Using above point we can also say that the smallest element will be present at the top of PriorityQueue.
  • the order of elements or we can say the priority of elements in which they should arrange, we can define it using Comparator as well as Comparable Interface but here we used Comparator as shown below.
  • We can not add null values in PriorityQueue, otherwise it will throw java.lang.NullPointerException.

Deque (Double ended queue)

  • It is an interface that defines a blueprint to represent double ended queue data structure.
  • It extends Queue interface and It can be implemented by ArrayDeque or LinkedList.
  • Double ended queue data structure is a linear data structure where we can insert, remove and access elements from both ends. Where as In the Queue, we can insert element in the end and can remove from begining.
  • As, it is a kind of queue and extends Queue interface, so It have various methods of queue in it like
    • add()
    • offer()
    • peek()
    • poll()
    • remove()
  • Apart from this it have other methods also , some of them are mentioned below
    • addFirst()
    • addLast()
    • offerFirst()
    • offerLast()
    • peekFirst()
    • peekLast()
    • pollFirst()
    • pollLast()
    • removeFirst()
    • removeLast()
  • As mentioned earlier we can use Deque as Stack or we can say Deque is thread unsafe version of stack.

ArrayDeque

  • It provides implementation of the Deque Interface, also called as Resizable-array implementation of Deque.
  • It does not have any capacity restrictions.
  • It is not synchronized, it means it is not thread safe.
  • It will be faster then LinkedList when used as Queue. Also, faster than Stack when used as stack.

Set

  • It is an interface that extends Collection interface and used to represent group of items in which we can not have duplicates.
  • It not maintains the order of elements so we can say it is used to represent unordered set of elements.
  • As, it is an interface so we require some concrete classes to implement it. these concrete classes are: HashSet, LinkedHashSet and TreeSet;
  • Set can only have 1 null value.
  • Set also does not allow random access to its elements, it does not have any such method.

HashSet

  • It is a class that implement Set interface.
  • HashSet shows behaviour of set by internally using HashMap.
    • Whenever we add element using add() method in HashSet, internal it adding that element to HashMap using put() method having key as that element with its value as constant Object that is "Present".
    • so, How adding element to HashMap provide it uniqueness?
    • To answer this question we have to know the usage of put(key,value). so, whenever we add value to hashmap using put() then it will return the old value of that key else it just return null. Now, HashSet using it as advantage. so whenever put()==null it means this is unique element and hence HashSet add() will return true. Else, put()!=null, means element already exists and hence HashSet add() will return false and will not add that element in it.
  • We can add null value in HashSet.
  • HashSet does not guarantee the order of element in which they inserted.
  • It is not synchronize, that is multiple threads can access and manipulate the content at same time, hence it is called as thread unsafe.
  • The default initial capacity of HashSet is 16 and load factor is 0.75
  • so, whenever the number of elements in HashSet is greater than (initial capacity * load factor) then HashSet grows its size approximately to double.
  • We can also set value of initial capacity and load factor. using new HashSet(int initialCapacity, float loadFactor); Constructor
  • Some of its methods are mentioned below.
    • add(E e) // Add element to HashSet
    • remove(Object o) // Remove element From HashSet
    • size() // Return the size of set.
    • clear() // Remove all elements from set.

LinkedHashSet

  • It is a class that implement Set interface and extend HashSet.
  • Unlike HashSet, LinkedHashSet maintains order of the elements in which they inserted.
  • The insertion order is maintainable in LinkedHashSet because internally it maintains doubly linked list using LinkedHashMap, between all of its elements.
  • Like HashSet,
    • It contains only unique elements.
    • It is not synchronized.
    • It can contains null elements.
    • The default initial capacity is 16 and load factor is 0.75. It follows same approach to grow its size as HashSet uses.
    • All operation of LinkedHashSet are same as HashSet operations.
  • LinkedHashSet is a bit slower than HashSet because of the additonal cost of maintaining a LinkedList.




Note : Please comment below for any improvement , suggestions, regarding any wrong information present in this article. We will improve it so that only right information available in this article.




Some of other popular article you can give it a try.

Comments

Post a Comment