COLLECTION FRAMEWORK


JAVA COLLECTION

“Collection” and “Collections” both are part of java collection framework, but both serve different purpose.

Collection is a top level interface of java collection framework(the root of the collection hierarchy. A collection represents a group of objects known as its elements.)whereas Collections is an utility class.

A Collection is a group of individual objects represented as a single unit.
Java provides Collection Framework which defines several classes and interfaces to represent a group of objects as a single unit. Some types of collections allow duplicate elements, and others do not. Some are ordered and others are unordered.

The Collection interface (java.util.Collection) and Map interface (java.util.Map) are the two main “root” interfaces of Java collection classes.

Need for Collection Framework:

Before Collection Framework (or before JDK 1.2) was introduced, the standard methods for grouping Java objects (or collections) were Arrays or Vectors or Hashtables. All of these collections had no common interface.








Collection Interface:
    

 

Collection interface is a member of java.util package.

Set -a collection that cannot contain duplicate elements

List- an ordered collection (sometimes called a sequence). Lists can contain duplicate elements. The user of a List generally has precise control over where in the list each element is inserted and can access elements by their integer index (position).

Queue -a collection used to hold multiple elements prior to processing. Besides basic Collection operations, a Queue provides additional insertion, extraction, and inspection operations.
Queues typically, but do not necessarily, order elements in a FIFO (first-in, first-out) manner. Among the exceptions are priority queues, which order elements according to a supplied comparator or the elements’ natural ordering.

Map- an object that maps keys to values. A Map cannot contain duplicate keys; each key can map to at most one value. If you’ve used Hashtable, you’re already familiar with the basics of Map.

Collection is a root level interface of the Java Collection Framework. Most of the classes in Java Collection Framework inherit from this interface.

          ---List
          ---Set
          ---Queue are main sub interfaces of this interface.

JDK doesn’t provide any direct implementations of this interface.
JDK provides direct implementations of it’s sub interfaces.

ArrayList, Vector, HashSet, LinkedHashSet, PriorityQueue are some indirect implementations of Collection interface.




LEGACY CLASSES

Early version of java did not include the Collections framework. It only defined several classes and interfaces that provide methods for storing objects. When Collections framework were added in J2SE 1.2, the original classes were reengineered to support the collection interface. These classes are also known as Legacy classes. All legacy classes and interface were redesign by JDK 5 to support Generics. In general, the legacy classes are supported because there is still some code that uses them.

The following are the legacy classes defined by java.util package

·       Dictionary
·       HashTable
·       Properties
·       Stack
·       Vector

There is only one legacy interface called Enumeration

NOTE: All the legacy classes are synchronized

JAVA LIST INTERFACE

List Interface is the subinterface of Collection.
A List is an ordered Collection (sometimes called a sequence).
Lists may contain duplicate elements.
Elements can be inserted or accessed by their position in the list, using a zero-based index.

List Interface declaration

public interface List<E> extends Collection<E>  

Java generics have type parameter naming conventions like following:

T - Type
E - Element
K - Key
N - Number
V – Value

For example take the following scenario

public class Node<E>{
   E elem;
   Node<E> next, previous;
}
class Test{
   Node<String> obj = new Node<>();
}
For the above scenerio, in background the Node class 'E' will reference the String type and class will be look like following

public class Node<String>{
   String elem;
   Node<String> next,previous;
}

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:

·       Java ArrayList class can contain duplicate elements,including null.
·       Java ArrayList class maintains insertion order.
·       Java ArrayList class is non synchronized.
·       Java ArrayList allows random access because array works at the index basis.
·       In Java ArrayList class, manipulation is slow because a lot of shifting needs to occur if any element is removed from the array list.

ARRAY VS ARRAYLIST IN JAVA
·       Array is a fixed length data structure whereas ArrayList is a variable length Collection class.
·       We cannot change length of array once created in Java but ArrayList can be changed.
·       We cannot store primitives in ArrayList, it can only store objects. But array can contain both primitives and objects in Java.
·       Since Java 5, primitives are automatically converted in objects which is known as auto-boxing.

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:
·       Java LinkedList class can contain duplicate elements (including null).
·       Java LinkedList class maintains insertion order.
·       Java LinkedList class is non synchronized.
·       In Java LinkedList class, manipulation is fast because no shifting needs to occur.
·       Java LinkedList class can be used as a list, stack or queue.

DIFFERENCE BETWEEN ARRAYLIST AND LINKEDLIST

ArrayList and LinkedList both implements List interface and maintains insertion order.Both are non synchronized classes.
However, there are many differences between ArrayList and LinkedList classes that are given below.

ArrayList
LinkedList
1) ArrayList internally uses a dynamic array to store the elements.
LinkedList internally uses a doubly linked list 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.
Manipulation with LinkedList is faster than ArrayList because it uses a doubly linked list, so no bit shifting is required in memory.
3) An ArrayList class can act as a list only because it implements List only.
LinkedList class can act as a list and queue both because it implements List and Deque interfaces.
4) ArrayList is better for storing and accessing data.
LinkedList is better for manipulating data.

DIFFERENCE BETWEEN ARRAYLIST AND VECTOR

·       ArrayList and Vector both implements List interface and maintains insertion order. Vector is similar to ArrayList which represents a dynamic array.

·       There are two differences between Vector and ArrayList. First, Vector is synchronized while ArrayList is not, and Second, it contains many legacy methods that are not part of the Collections Framework.

·       With the release of JDK 5, Vector also implements Iterable. This means that Vector is fully compatible with collections, and a Vector can have its contents iterated by the for-each loop.

However, there are many differences between ArrayList and Vector classes that are given below.

ArrayList
Vector
1) ArrayList is not synchronized.
Vector is synchronized.
2) ArrayList increments 50% of current array size if the number of elements exceeds from its capacity.
Vector increments 100% means doubles the array size if the total number of elements exceeds than its capacity.
3) ArrayList is not a legacy class. It is introduced in JDK 1.2.
Vector is a legacy class.
4) ArrayList is fast because it is non-synchronized.
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.
5) ArrayList uses the Iteratorinterface to traverse the elements.
A Vector can use the Iterator interface or Enumeration interface to traverse the elements.

import java.util.*;
public class Test
{
  public static void main(String[] args)
   {
      Vector ve = new Vector();
       ve.add(10);
       ve.add(20);
       ve.add(30);
       ve.add(40);
       ve.add(50);
       ve.add(60);

       Enumeration en = ve.elements();

       while(en.hasMoreElements())
       {
           System.out.println(en.nextElement());
       }
   }

}

10
20
30
40
50
60

STACK CLASS

·       Stack class extends Vector.
·       It follows last-in, first-out principle for the stack elements.
·       It defines only one default constructor
·       Stack() //This creates an empty stack
·       If you want to put an object on the top of the stack, call push() method.
·       If you want to remove and return the top element, call pop() method.
·       An EmptyStackException is thrown if you call pop() method when the invoking stack is empty.
·       You can use peek() method to return, but not remove, the top object.
·       The empty() method returns true if nothing is on the stack.
·       The search() method determines whether an object exists on the stack and returns the number of pops that are required to bring it to the top of the stack.

JAVA QUEUE INTERFACE

Java Queue interface orders the element in FIFO(First In First Out) manner. In FIFO, first element is removed first and last element is removed at last.
Queue Interface declaration:
public interface Queue<E> extends Collection<E>  

Methods of Java Queue Interface:

Method
Description
boolean add(object)
It is used to insert the specified element into this queue and return true upon success.
boolean offer(object)
It is used to insert the specified element into this queue.
Object remove()
It is used to retrieves and removes the head of this queue.
Object poll()
It is used to retrieves and removes the head of this queue, or returns null if this queue is empty.
Object element()
It is used to retrieves, but does not remove, the head of this queue.
Object peek()
It is used to retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.

PriorityQueue class

The PriorityQueue class provides the facility of using queue. But it does not orders the elements in FIFO manner. It inherits AbstractQueue class.

PriorityQueue class declaration

Let's see the declaration for java.util.PriorityQueue class.
public class PriorityQueue<E> extends AbstractQueue<E> implements Serializable  
NOTE : The elements in PriorityQueue must be of Comparable type. String and Wrapper classes are Comparable by default. To add user-defined objects in PriorityQueue, you need to implement Comparable interface.

JAVA DEQUE INTERFACE

Java Deque Interface is a linear collection that supports element insertion and removal at both ends. Deque is an acronym for "double ended queue".

Deque Interface declaration:

public interface Deque<E> extends Queue<E>  

Methods of Java Deque Interface:

Method
Description
boolean add(object)
It is used to insert the specified element into this deque and return true upon success.
boolean offer(object)
It is used to insert the specified element into this deque.
Object remove()
It is used to retrieves and removes the head of this deque.
Object poll()
It is used to retrieves and removes the head of this deque, or returns null if this deque is empty.
Object element()
It is used to retrieves, but does not remove, the head of this deque.
Object peek()
It is used to retrieves, but does not remove, the head of this deque, or returns null if this deque is empty.

ARRAYDEQUE CLASS

The ArrayDeque class provides the facility of using deque and resizable-array. It inherits AbstractCollection class and implements the Deque interface.
The important points about ArrayDeque class are:
  • Unlike Queue, we can add or remove elements from both sides.
  • Null elements are not allowed in the ArrayDeque.
  • ArrayDeque is not thread safe, in the absence of external synchronization.
  • ArrayDeque has no capacity restrictions.
  • ArrayDeque is faster than LinkedList and Stack.

ARRAYDEQUE HIERARCHY

The hierarchy of ArrayDeque class is given in the figure displayed at the right side of the page.

ARRAYDEQUE CLASS DECLARATION

Let's see the declaration for java.util.ArrayDeque class.
public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable  

Java ArrayDeque have offerFirst() and pollLast() methods

    Deque<String> deque=new ArrayDeque<String>();  
   deque.offer("vimal");  
    deque.add("mukul");  
    deque.offerFirst("jai");  
    //deque.poll();  
    //deque.pollFirst();//it is same as poll()  
    deque.pollLast();  

JAVA HASHSET CLASS
Java HashSet class hierarchy
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:
·       HashSet stores the elements by using a mechanism called hashing.
·       HashSet contains unique elements only.
·       HashSet allows null value.
·       HashSet class is non synchronized.
·       HashSet doesn't maintain the insertion order. Here, elements are inserted on the basis of their hashcode.
·       HashSet is the best approach for search operations.
·       The initial default capacity of HashSet is 16, and the load factor is 0.75.
DIFFERENCE BETWEEN LIST AND SET
A list can contain duplicate elements whereas Set contains unique elements only.
Hierarchy of HashSet class
The HashSet class extends AbstractSet class which implements Set interface. The Set interface inherits Collection and Iterable interfaces in hierarchical order.
HashSet class declaration
Let's see the declaration for java.util.HashSet class.
public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable   



JAVA LINKEDHASHSET CLASS
Java HashSet class hierarchy
Java LinkedHashSet class is a Hashtable and Linked list implementation of the set interface. It inherits HashSet class and implements Set interface.
The important points about Java LinkedHashSet class are:
·       Java LinkedHashSet class contains unique elements only like HashSet.
·       Java LinkedHashSet class provides all optional set operation and permits null elements.
·       Java LinkedHashSet class is non synchronized.
·       Java LinkedHashSet class maintains insertion order.
·       Hierarchy of LinkedHashSet class
·       The LinkedHashSet class extends HashSet class which implements Set interface. The Set interface inherits Collection and Iterable interfaces in hierarchical order.

LinkedHashSet class declaration
Let's see the declaration for java.util.LinkedHashSet class.

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, Serializable 

JAVA TREESET CLASS
TreeSet class hierarchy
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:
·       Java TreeSet class contains unique elements only like HashSet.
·       Java TreeSet class access and retrieval times are quiet fast.
·       Java TreeSet class doesn't allow null element.
·       Java TreeSet class is non synchronized.
·       Java TreeSet class maintains ascending order.
Hierarchy of TreeSet class
As shown in the above diagram, Java TreeSet class implements the NavigableSet interface. The NavigableSet interface extends SortedSet, Set, Collection and Iterable interfaces in hierarchical order.
TreeSet class declaration
Let's see the declaration for java.util.TreeSet class.
public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, Serializable 

MAP INTERFACE:

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.

Java Map Hierarchy

There are two interfaces for implementing Map in java: Map and SortedMap, and three classes: HashMap, LinkedHashMap, and TreeMap. The hierarchy of Java Map is given below:

              
A Map doesn't allow duplicate keys, but you can have duplicate values. HashMap and LinkedHashMap allow null keys and values, but TreeMap doesn't allow any null key or value.
A Map can't be traversed, so you need to convert it into Set using keySet() or entrySet() method.
Class
Description
HashMap is the implementation of Map, but it doesn't maintain any order.
LinkedHashMap is the implementation of Map. It inherits HashMap class. It maintains insertion order.
TreeMap is the implementation of Map and SortedMap. It maintains ascending order.

 

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

  • Java HashMap class contains values based on the key.
  • Java HashMap class contains only unique keys.
  • Java HashMap class may have one null key and multiple null values.
  • Java HashMap class is non synchronized.
  • Java HashMap class maintains no order.
  • The initial default capacity of Java HashMap class is 16 with a load factor of 0.75.

Hierarchy of HashMap class

As shown in the above figure, HashMap class extends AbstractMap class and implements Map interface.

HashMap class declaration

Let's see the declaration for java.util.HashMap class.
1.   public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable  

HashMap class Parameters

Let's see the Parameters for java.util.HashMap class.
  • K: It is the type of keys maintained by this map.
  • V: It is the type of mapped values.

Difference between HashSet and HashMap

HashSet contains only values whereas HashMap contains an entry(key and value).

JAVA LINKEDHASHMAP CLASS

Java LinkedHashMap class is Hashtable and Linked list implementation of the Map interface, with predictable iteration order. It inherits HashMap class and implements the Map interface.

Points to remember

  • Java LinkedHashMap contains values based on the key.
  • Java LinkedHashMap contains unique elements.
  • Java LinkedHashMap may have one null key and multiple null values.
  • Java LinkedHashMap is non synchronized.
  • Java LinkedHashMap maintains insertion order.
  • The initial default capacity of Java HashMap class is 16 with a load factor of 0.75.

LinkedHashMap class declaration

Let's see the declaration for java.util.LinkedHashMap class.
1.   public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>  

LinkedHashMap class Parameters

Let's see the Parameters for java.util.LinkedHashMap class.
  • K: It is the type of keys maintained by this map.
  • V: It is the type of mapped values.

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:
  • Java TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
  • Java TreeMap contains only unique elements.
  • Java TreeMap cannot have a null key but can have multiple null values.
  • Java TreeMap is non synchronized.
  • Java TreeMap maintains ascending order.

TreeMap class declaration

Let's see the declaration for java.util.TreeMap class.
1.   public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable  

TreeMap class Parameters

Let's see the Parameters for java.util.TreeMap class.
  • K: It is the type of keys maintained by this map.
  • V: It is the type of mapped values.

What is difference between HashMap and TreeMap?


HashMap
TreeMap
1) HashMap can contain one null key.
TreeMap cannot contain any null key.
2) HashMap maintains no order.
TreeMap maintains ascending order.

DIFFERENCE BETWEEN COMPARABLE AND COMPARATOR
Comparable and Comparator both are interfaces and can be used to sort collection elements.
However, there are many differences between Comparable and Comparator interfaces that are given below.
Comparable
Comparator
1) Comparable provides a single sorting sequence. In other words, we can sort the collection on the basis of a single element such as id, name, and price.
The Comparator provides multiple sorting sequences. In other words, we can sort the collection on the basis of multiple elements such as id, name, and price etc.
2) Comparable affects the original class, i.e., the actual class is modified.
Comparator doesn't affect the original class, i.e., the actual class is not modified.
3) Comparable provides compareTo() method to sort elements.
Comparator provides compare() method to sort elements.
4) Comparable is present in java.lang package.
A Comparator is present in the java.util package.
5) We can sort the list elements of Comparable type by Collections.sort(List) method.
We can sort the list elements of Comparator type by Collections.sort(List, Comparator) method.


Difference between array and arraylist

http://www.java67.com/2012/12/difference-between-array-vs-arraylist-java.html

Comments