Recent Posts

Tuesday, 26 July 2016

Collection Framework Tutorial Part 2


1. Collection interface
* If we want to represent a group of individual objects as a single entity then we should go for Collection interface.

* Collection interface defines the most common general methods which can be applicable for any Collection object.

* The following is the list of methods present in Collection interface.

1.  boolean add(Object o);
2.  boolean addAll(Collection c);
3.  boolean remove(Object o);
4.  boolean removeAll(Object o);
5.  boolean retainAll(Collection c); // To remove all objects except those present in c.
6.  void clear();
7.  boolean contains(Object o);
8.  boolean containsAll(Collection c);
9.  boolean isEmpty();
10. int size();
11. Object[] toArray();
12. Iterator iterator();

     There is no concrete class which implements Collection interface directly.

2 List interface
* It is the child interface of Collection.

* If we want to represent a group of individual objects as a single entity where duplicates are allow and insertion order is preserved. Then we should go for List.

* Insertion order will be preserved by means of Index.

* We can differentiate duplicate objects and we can maintain insertion order by means of index hence "index play very important role in List".

* List interface defines the following specific methods.

1. boolean add(int index,Object o);
2. boolean addAll(int index,Collectio c);
3. Object get(int index);
4. Object remove(int index);
5. Object set(int index,Object new); //to replace
6. int indexOf(Object o); // Returns index of first occurrence of "o".
7. int lastIndexOf(Object o);
8. ListIterator listIterator();

* List interface contains 4 classes
1. ArrayList
2. LinkedList
3. VectorList
4. Stack

1. ArrayList
* Uses a dynamic array for storing the elements. It extends AbstractList class and implements List interface.

* ArrayLists are created with an initial size, when this size is exceeded, it gets enlarged automatically.

* Can contain duplicate elements.

* Maintains insertion order.

* Not synchronized.

* Random access because array works at the index basis.

* Manipulation slows because a lot of shifting needs to be occurred if any element is removed from the array list.

* null insertion is possible.

* Heterogeneous objects are allowed.

Constructors
1. ArrayList a=new ArrayList();
     Creates an empty ArrayList object with default initial capacity "10" if ArrayList reaches its max capacity then a new ArrayList object will be created with
             New capacity=(current capacity*3/2)+1

2. ArrayList a=new ArrayList(int initialcapacity);
     Creates an empty ArrayList object with the specified initial capacity.

3. ArrayList a=new ArrayList(collection c);
     Creates an equivalent ArrayList object for the given Collection that is this constructor meant for inter conversation between collection objects. That is to dance between collection objects.
E.g
package com.ashok.collections;

import java.util.*;

class MyArrayList {
   public static void main(String[] args) {
      ArrayList a=new ArrayList();
      a.add("Ashok");
      a.add(10);
      a.add("Ashok");
      a.add(null);
      System.out.println(a);//[Ashok, 10, Ashok, null]
      a.remove(2);
      System.out.println(a);//[Ashok, 10, null]
      a.add(2,"Vinod");
      a.add("Kimu");
      System.out.println(a);//[Ashok, 10, Vinod, null, Kimu]
   }
}
Note
* In every collection class toString(0 is overridden to return it's content directly in the following format.
[object1, object2, object3, ......]

* Usually we can use collection to hold and transfer objects from one tier to another tier. To provide support for this requirement every Collection class already implements Serializable and Cloneable interfaces.

* ArrayList and Vector classes implements RandomAccess interface so that any random element we can access with the same speed. Hence ArrayList is the best choice of "retrival operation".

* RandomAccess interface present in util package and doesn't contain any methods. It is a marker interface.
E.g
package com.ashok.collections;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.RandomAccess;

class Test {
   public static void main(String[] args) {
      ArrayList arrayList = new ArrayList();
      LinkedList linkedList = new LinkedList();

      System.out.println(arrayList instanceof Serializable); // true
      System.out.println(linkedList instanceof Cloneable); // true
   
      System.out.println(arrayList instanceof RandomAccess); // true
      System.out.println(linkedList instanceof RandomAccess); // false
   }
}
ArrayList Vs Vector

1. Synchronization
     ArrayList is non-synchronized which means multiple threads can work on ArrayList at the same time. For example if one thread is performing an add operation on ArrayList, there can be an another thread performing remove operation on ArrayList at the same time in a multithreaded environment.
 
    While Vector is synchronized. This means if one thread is working on Vector, no other thread can get a hold of it. Unlike ArrayList, only one thread can perform an operation on vector at a time.

2. Resize
     Both ArrayList and Vector can grow and shrink dynamically to maintain the optimal use of storage, however the way they resized is different. ArrayList grow by half of its size when resized while Vector doubles the size of itself by default when grows.

3. Performance
     ArrayList gives better performance as it is non-synchronized. Vector operations gives poor performance as they are thread-safe, the thread which works on Vector gets a lock on it which makes other thread wait till the lock is released.

How to get synchronized version of ArrayList object
   Collections class defines the following method to return synchronized version of List.
public static List synchronizedList(list l);
E.g

     Similarly we can get synchronized version of Set and Map objects by using the following methods.
1. public static Set synchronizedSet(Set s);
2. public static Map synchronizedMap(Map m);

* ArrayList is the best choice if our frequent operation is retrieval.

* ArrayList is the worst choice if our frequent operation is insertion (or) deletion in the middle because it requires several internal shift operations.
2. LinkedList
* The underlying data structure is double LinkedList

* Insertion order is preserved.

* Duplicate objects are allowed.

* Heterogeneous objects are allowed.

* null insertion is possible.

* Implements Serializable and Cloneable interfaces but not RandomAccess.

* If our frequent operation is insertion (or) deletion in the middle then LinkedList is the best choice.

* If our frequent operation is retrieval operation then LinkedList is worst choice.
  Usually we can use LinkedList to implement Stacks and Queues.
To provide support for this requirement LinkedList class defines the following 6 specific methods.

1. void addFirst(Object o);
2. void addLast(Object o);
3. Object getFirst();
4. Object getLast();
5. Object removeFirst();
6. Object removeLast();

We can apply these methods only on LinkedList object.

Constructors
LinkedList l=new LinkedList();
     Creates an empty LinkedList object.

LinkedList l=new LinkedList(Collection c);
     To create an equivalent LinkedList object for the given collection.
E.g
package com.ashok.collections;

import java.util.LinkedList;

class MyLinkedList {
   public static void main(String[] args) {
      LinkedList list = new LinkedList();
      list.add("Ashok");
      list.add(30);
      list.add(null);
      list.add("Ashok");
      System.out.println(list);// [Ashok, 10, null, Ashok]
      list.set(0, "Software");
      System.out.println(list);// [Software, 10, null, Ashok]
      list.set(0, "Vinod");
      System.out.println(list);// [Vinod, 10, null, Ashok]
      list.removeLast();
      System.out.println(list);// [Vinod, 10, null]
      list.addFirst("Dillesh");
      System.out.println(list);// [Dillesh, Vinod, 30, null]
   }
}
Inter conversion between collection objects
package com.ashok.collections.linkedlist;

import java.util.ArrayList;
import java.util.LinkedList;

public class MyCollectionsConversion {
   public static void main(String a[]) {
      ArrayList arrayList = new ArrayList();
      arrayList.add(10);
      arrayList.add(20);
      arrayList.add(30);
      System.out.println("l1--->" + arrayList);
   
      LinkedList linkedList = new LinkedList(arrayList);
      linkedList.add(1, 5);
      linkedList.add(3, 5);
      linkedList.add(5, 15);
      System.out.println("l2--->" + linkedList);
   
      ArrayList arrayList1 = new ArrayList(linkedList);
      System.out.println("l3--->" + arrayList1);
   }
}

Output
l1--->[10, 20, 30]
l2--->[10, 5, 20, 5, 30, 15]
l3--->[10, 5, 20, 5, 30, 15]

3. Vector Class
* The underlying Data structure for the vector is resizable array or growable array.

* Insertion order is preserved.

* Duplicate objects are allowed.

* ‘null’ insertion is possible.

* Heterogeneous objects are allowed.

* Best choice if the frequent operation is retrieval.

* Worst choice if the frequent operation is insertion or deletion in the middle.

* Vector class implemented serializable, cloneable and RandomAccess Interfaces.

* Every method present in Vector is synchronized and hence Vector is Thread safe.

Vector specific methods:
To add objects:
1. add(Object o);-----Collection
2. add(int index,Object o);-----List
3. addElement(Object o);-----Vector

To remove elements:
1. remove(Object o);--------Collection
2. remove(int index);--------------List
3. removeElement(Object o);----Vector
4. removeElementAt(int index);-----Vector
5. removeAllElements();-----Vector
6. clear();-------Collection

To get objects:
1. Object get(int index);---------------List
2. Object elementAt(int index);-----Vector
3. Object firstElement();--------------Vector
4. Object lastElement();---------------Vector

Other methods:
1. int size();//How many objects are added
2. int capacity();//Total capacity
3. Enumeration elements();

Constructors
1. Vector v=new Vector();
* Creates an empty Vector object with default initial capacity 10.

* Once Vector reaches its maximum capacity then a new Vector object will be created with double capacity. That is "newcapacity=currentcapacity*2".

2. Vector v=new Vector(int initialcapacity);

3. Vector v=new Vector(int initialcapacity, int incrementalcapacity);

4. Vector v=new Vector(Collection c);
E.g
package com.ashok.collections.linkedlist;

import java.util.Vector;

public class MyLinkedList {
   public static void main(String[] args) {
      Vector vector = new Vector();
      System.out.println(vector.capacity());// 10
      for (int i = 1; i <= 10; i++) {
         vector.addElement(i);
      }
      System.out.println(vector.capacity());// 10
      vector.addElement("Ashok");
      System.out.println(vector.capacity());// 20
      System.out.println(vector);// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, Ashok]
   }
}
4. Stack class
* It is the child class of Vector.

* Whenever last in first out(LIFO) order required then we should go for Stack.

Constructors
     Stack class contains one and only one constructor.
Stack s= new Stack();

Methods in Stack
1. Object push(Object o);
     To insert an object into the stack.

2. Object pop();
     To remove and return top of the stack.

3. Object peek();
     To return top of the stack without removal.
 
4. boolean empty();
     Returns true if Stack is empty.

5. int search(Object o);
     Returns offset if the element is available otherwise returns "-1"

E.g
package com.ashok.collections;

import java.util.Stack;

public class MyStack {
   public static void main(String[] args) {
      Stack stack = new Stack();
      stack.push("Ashok");
      stack.push("Vinod");
      stack.push("Naresh");
      
   System.out.println(stack);// [Ashok, Vinod, Naresh]
      System.out.println(stack.pop());// Naresh
      System.out.println(stack);// [Ashok, Vinod]
      System.out.println(stack.peek());// Vinod
      System.out.println(stack.search("Ashok"));// 2
      System.out.println(stack.search("Dillesh"));// -1
      System.out.println(stack.empty());// false
   }
}
Cursors Available in collection frame work
     From the collection object to retrieve object we can use the following 3 cursors.
1. Enumeration
2. Iterator
3. ListIterator

1. Enumeration
* This interface has introduced in 1.0 version it contains the following 2 methods.
public boolean hasMoreElements();
public Object nextElement();

* We can use Enumeration to get objects one by one from the legacy collection objects.

* We can create Enumeration object by using elements() method.
public Enumeration elements();
Enumeration e=v.elements(); //using Vector Object
E.g
package com.ashok.collections;

import java.util.*;

public class MyEnumaretion {
   public static void main(String arg[]) {
      Vector vector = new Vector();
      for (int i = 0; i <= 10; i++) {
         vector.addElement(i);
      }
      System.out.println(vector);
      Enumeration e = vector.elements();
      while (e.hasMoreElements()) {
         Integer i = (Integer) e.nextElement();
         if ((i % 2) == 0)
            System.out.println(i);
      }
      System.out.println(vector);
   }
}
Output
8
10
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Limitations of Enumeration
1. It is applicable only for legacy classes and it is not a universal cursor.
2. While iterating the elements by using enumeration we can perform only read operation and we can’t perform any modify/removal operations.
     To overcome these problems we should go for Iterator interface.

2. Iterator
* Introduced in 1.2 version.

* We can use Iterator to get objects one by one from any collection object.

* We can apply Iterator concept for any collection object and it is a universal cursor.

* While iterating the objects by Iterator we can perform both read and remove operations.
     This interface contains the following 3 methods.
boolean hasNext();
Object next();
void remove();
E.g
package com.ashok.collections;

import java.util.*;

public class MyIterator {
   public static void main(String arg[]) {
      ArrayList  arrayList = new ArrayList();
      for (int i = 0; i <= 10; i++) {
         arrayList.add(i);
      }
      System.out.println(arrayList);
      Iterator itr = arrayList.iterator();
      while (itr.hasNext()) {
         Integer i = (Integer) itr.next();
         if ((i % 2) == 0) {
            System.out.println(i);
         } else {
            itr.remove();
         }
      }
      System.out.println(arrayList);
   }
}
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
0
2
4
6
8
10
[0, 2, 4, 6, 8, 10]
Limitations of Iterator
* Both enumeration and Iterator are single direction cursors only. That is we can always move only forward direction and we can't move to the backward direction.

* While iterating by Iterator we can perform only read and remove operations and we can't perform replacement and addition of new objects.

* To overcome these limitations sun people introduced listIterator concept.

3. ListIterator
* ListIterator is the child interface of Iterator.

* By using listIterator we can move either to the forward direction (or) to the backward direction that is it is a bi-directional cursor.

* While iterating by listIterator we can perform replacement and addition of new objects in addition to read and remove operations
      By using listIterator method we can create listIterator object.
public ListIterator listIterator();
ListIterator itr=list.listIterator(); // Here list is any List object
    ListIterator interface defines the following 9 methods.
1. public boolean hasNext();
2. public Object next(); forward
3. public int nextIndex();
4. public boolean hasPrevious();
5. public Object previous(); backward
6. public int previousIndex();
7. public void remove();
8. public void set(Object new);
9. public void add(Object new);
E.g
package com.ashok.collections;

import java.util.LinkedList;
import java.util.ListIterator;

public class MyListIterator {
   public static void main(String[] args) {
      LinkedList list = new LinkedList();
      list.add("Ashok");
      list.add("Vinod");
      list.add("Dillesh");
      list.add("Thiru");
      System.out.println(list);
      ListIterator itr = list.listIterator();
      while (itr.hasNext()) {
         String s = (String) itr.next();
         if (s.equals("Vinod")) {
            itr.remove();
         }
      }
      System.out.println(list);
   }
}
Output
[Ashok, Vinod, Dillesh, Thiru]
[Ashok, Dillesh, Thiru]

Next Tutorial  Collection Framework Tutorial Part 3

Previous Tutorial  Collection Framework Tutorial Part 1

No comments:

Post a Comment