Collection Framework

Programming Reference

Collections (DurgaSoft Notes)

Arrays and ArrayList (Strengths and Limitations)

  • Arrays –> Homogeneous data elements (Resolve by using Object.arrays)
Object[] o = new Object[1000]; //FIXED SIZE!!
  • Arrays are not implemented on any standard data structure and hence no readymade method support
9 Interfaces (6 in Collection, 3 in Map).
Screen Shot 2015-01-24 at 4.15.39 PM
Maps are not the Part of Collection Framework

Screen Shot 2015-01-24 at 4.16.11 PM

  1. Collection (Interface) : Most Common method
    • Collections is a utility Class
    • Collection is an interface
    • An interface give high level view of all the methods (no implementation).
  2. List
    • Child Interface if Collection
    • Duplicate values are allowed
    • Insertion Order is preserved
    • Screen Shot 2015-01-24 at 3.37.19 PM
    • Vectors and Stack are called Legacy Classes as they are from older version
  3. Set
    • Duplicates are not allowed
    • Insertion Order not Preserved
    • Set →HashSet →LinkedHashSet
  4. SortedSet (I)
    • Collection →Set →SortedSet → NavigableSet (TreeSet class is the implementation) (v 1.2)
    •  Elements are inserted in sorted order
  5. NavigableSet (I)
    • Child Interface of Sorted Set
    • TreeSet Class Provides the Implementation
  6. Queue (I)
      • Screen Shot 2015-01-24 at 3.57.26 PM

    All Above keeps groups of objects. For Key value pairs, Maps(I) is used. (Not in Collection Framework)

  7. Map (I), not in Collection
    • key –> Duplicate not Allowed
    • Value –> Duplicates allowed
    • Screen Shot 2015-01-24 at 4.07.33 PM
  8. SortedMap(I)
    • Map(I) →SortedMap
  9. NavigableMap
    • Map(I) →SortedMap → NavigableMap(I) (TreeMap is the Implementation Class)
    • Screen Shot 2015-01-24 at 4.13.07 PM

Cursors in Java

  1. Enumeration
  2. Iterator
  3. List Iterators

Sorting

  1. Comparable(I) : Default natural sorting order
  2. Comparator(I) : Customized Sorting

Utility Classes

  1. Collections
  2. Arrays

Collection(I)

  • Collection(I) is the root interface of Collection Framework.
  • Collection(I) defines the most common methods which are applicable for any collection object.
    • boolean add(Object o) , addAll(Collection c)
    • boolean remove(Object o) , removeAll(Collection c)
    • void clear()
    • boolean retainAll(Collection c) To remove all objects except those present in c
    • boolean contains(Object o), containsAll(Collection c)
    • boolean isEmpty()
    • int size(); be careful..not length()
    • Object[] toArray(); Object is the return type
    • Iterator iterator(); it take one by one
    • Since Collections are meant to be transfered over network, thus each collection implements Serializable & Cloneable Interface
  • Collection Interface DOES NOT contain any method to retrieve objects. There is no concrete class which implements collection class directly.

1. List(I)

  • All the methods of Collection(I) are available
  • addAll(int index, Collection c) //Add a list from index i onwards
  • indexOf(Object o); first occurrence (Just like Arrays)
  • get(int index)
  • ListIterator listIterator()
  • set(int index, Object o)

A. ArrayList(Implementation Class of List)

  • Underlying Data Structure : Resizable Array ()
  • Heterogeneous Objects are allowed
  • Only TreeSet and TreeMap does not allow heterogeneous objects as the Objects are in sorted order which is achieved after COMPARING homogeneous objects

Constructors

  • ArrayList al = new ArrayList();
    //Creates an empty arraylist with initial capacity of 10 elements. after that

new capacity = current capacity * (3/2) + 10

  • ArrayList al = new ArrayList(int initial_capacity)
  • ArrayList al = new ArrayList(Collection c)
  • sop(i) == sop(l.toString) ==> o/p [A, 10, A, null]

Only ArrayList and Vector classes implements RandomAccess Interface (java.util) (so that any random element can be accessed in same time/speed). RandomAccess doesn’t contain any method. Its a Marker Interface

Thus if frequent operation is RETRIEVAL, ArrayList is the best choice. For add, remove, its worst(lost of shifting if addition is done in the middle of ArrayList)

Difference between ArrayList and Vector

ArrayList Vector
all methods are non-synchronized most of the methods are synchronized
Not thread safe Thread safe (Only one thread can access)
Performance is relatively high Relatively Low Performance

Synchronized version of ArrayList Obj.

ArrayList al = new ArrayList();//non Synchronized
List l = Collections.synchronizedList(al);

public static List synchronizedList(List l)
public static Set synchronizedSet(Set s)
public static MAp synchronizedMap(Map m)

B. LinkedList (Detailed)

  • Underlying Data Structure : Doubly Linked List
  • frequent insertion or deletion [O(1)] //Best Choice
  • Worst for retrieval (due to linear probing of the list)
  • Implements Serializable and Cloneable but not RandomAccess Interface

Methods (Only for Linked List)

  • addFirst, removeFirst(), getFirst()
  • addLast(), removeLast(), getLast()
  • These methods can be used for Implementing Stack or Queue using Linked List

C. Vector

vector specific methods (long method name, the burden of Legacy class)

  • addElement(Object o)
  • removeElementAt(), removeAllElements
  • int capacity
  • initialized with 10 element, and then new capa = cc*2

D. Stack

  • Child of Vector
  • LIFO
  • Only one Constructor Stack s = new Stack();
  • Methods
    • push(Object o);
    • pop();
    • peek();
    • empty() [doe to Legacy, isEmpty() is not available]
    • boolean search(Object 0);//returns offset (return the no. from top), -1 for not found

Three cursors of JAVA

  1. Enumeration (Interface)
  2. Iterator (I)
  3. ListIterator (I)

1. Enumeration

Enumeration e = v.elements
**(v is vector, Only for Legacy Class)
**Has only two methods—boolean hasMoreElements(); & Object nextElement();(type casting is required)

  • Remove is not possible

2. Iterator

  • Universal Cursor (Applicable to any Collection Class)
  • read and remove both are possible

Iterator itr = c.iterator();
Where c is any collection object

Methods: 

  1. public boolean hasNext();
  2. public Object next();
  3. public void remove(); //not in Vector

Example : Program to remove odd elements from an ArrayList

ArrayList l =new ArrayList();
for (int i = 0; i < 10; i++){
     l.add(i);
}
Iterator itr = l.iterator();
while (itr.hasNext()){
   Integer n = (Integer)itr.next();//type casting is required as next() returns an Object type
   if(n%2 != 0)
    itr.remove();
}//end While

Limitation of Iterator

  • Only forward direction cursor
  • no replace and no addition of new object.

3. ListIterator (Child of Iterator, most powerful)

  • Bidirectional cursor
  • read, remove, replacement, addition of new operation
  • ListIterator itr = l.listIterator(); l is any List Obj (AR, LL, Vector or Stack

Methods:(9 in total)

  • boolean hasNext(), Object next(), int nextIndex() //FORWARD DIRn
  • boolean hasPrevious, Object previous(), int previousIndex() //BACKWARD DIRn
  • public void remove()
  • public void set(Object new)
  • public void add(Object new)

ONLY APPLICABLE FOR LIST OBJECTS

Implementation class for the three cursors

Enumeration e = v.elements();

System.out.println(e.getClass().getName());//Vector $1 -> $ = inner class, 1 anonymous inner class

2. Set(I)

  • Duplicates are not allowed
  • Set Interface doesn’t contain any new methods. So Only Collection interface methods are to be used.

A. HashSet (Implementation Class)

  • Underlying DS – HashSet
  • No Duplicates allowed (No exception thrown, but add() method returns false)
  • Insertion order is not preserved. Saved based on Hash code.
  • Best Choice for Search operation

Constructor

  • HashSet h = new HashSet(); initial capa: 16 and field ratio/load factor 75%
  • Field Ratio (after filling 75% new HashSet will be created), can be set through a constructor

B. LinkedHashSet (Implementation Class)

  • Child class of HashSet.
  • Underlying Data Structure : Linked List + Hash Table
  • To preserve Insertion order
  • Cache based Application

 

C. SortedSet (Implementation Class)

Specific methods

  • first(), last() –> not in the normal set
  • headSet(Object o), elements lessthan 0
  • tailSet(Obj o)
  • subset(o1, o2))
  • Comparator comparator()

D. TreeSet

  • Underlying DS : balanced Tree
  • Sorting order
  • NULL Acceptance only once (as its a set)

Constructor

  1. TreeSet t = new TreeSet(); //Default Natural Sorting Order
  2. TreeSet t = new TreeSet(Comparator c)//Customized sorted order
  • To insert NULL in a non empty TreeSet –> NullPointerException (conparison fails)
  • Heterogeneous elements are not allowed because they can’t be compared.
  • Null Acceptance :
    • After adding some elements, null pointer exception (no comparison)
    • In the beginning (empty tree set), it can be, but other elements gives null pointer exception.

TreeSet Details

  • StringBuffer Objects are not comparable because it does not implements Comparable Interface. Thus cannot be used to insert elements into TreeSet with Default Natural sorting order.
  • String Class and all other Wrapper Classes implements comparable Interface.
  • Comparable Interface, present in lang Package, has only one method compareTo()
  • public int compareTo(Object obj)
    • obj1.compareTo(obj2)
      • -ve, iff obj1 comes before obj2 (Default Natural Sorting Order)
      • +ve, iff obj1 comes afterobj2
      • 0, iff both onjects are equal.
    • Example: sop(‘A’.compareTo(‘B’));//-25
  • JVM calls compareTo() method before inserting into TreeSet.
  • Comparator Interface is meant for CUSTOMIZED sorting order, while Comparable(I) id for DNSO

Comparator (I) :

  • Customized Sorting Oder
  • java.util Package
  • two methods compare() and equals()[Dummy method, present in Object Class, access through inheritance.
  • public int compare(Object obj1, Object obj2);
    • -ve, iff obj comes before obj2, 0 for equal, +ve otherwise
  • Example code for Implementing Comparator (Add ints in Decreasing order)
 
    class testComparator implements Comparator{
         public int compare(Object obj1, Object obj2){ //provide
             Integer i1 = (Integer) obj1;//type casting to be sure of int
             Integer i2 = (Integer) obj2;
             //For Strings
           /*String s1 = (String) obj1;//Type casting
             String s2 = obj1.toString();
             return -s1.compareTo(s2);//Reverse alphabetical order
             return s2.compareTo(s1);//Also Reverse sorted
           */
     //For decreasing order, return -ve when obj1 > obj2
             if (i1 > i2) 
                  return -1;
             else if (i1 < i2)
                  return 1;
             else
                 return 0;
         }
    // Tweek
    return i1.compatrTo(i2);// Ascending order
    return i2.compareTo(i1);// Decreasing order
    return -i1.compareTo(i2);// Decreasing Order
    return 1; // Insertion order
    return -1; //reverse insertion order
    return 0; //only first element is inserted and all other are considered as duplicates
    }

    TreeSet t = new TreeSet(new testComparator);
    t.add(100); t.add(20);
  • For StringBuffer Class (not comparable), a Comparator has to be defined.
  • For predefined comparable Classes, DNSO is already available. (Comparators can be used to custom sorting order)
  • For predefined non comparable Classes (like StringBuffer), compulsorily compactors to be used.
  • For our own classes, Developer is responsible for DNSO. For the users of the class, they can use compactor for customized sorting order.
Comparable Compartator
 java.lang (for DNSO)  java.util (Customised)
 one method compareTo()  two mwthods compare() and equals()
 All Wrapper + String Implements it  Collator and RuleBasedCollator (only two classes)
  • Generics included in Java 1.5 to provide safety and type casting problems.
  • Arrays are type safe by default but Collections object are not. No compile time errors if inserting int in  String arraylist defined without using Generics.
  • if Generics are not used, type casting is mandatory at the time of retrieval
ArrayList l = new ArrayList();
l.add("Nitin");
//String s = l.get(0);// incompatible type found exception
String s = (String) l.get(0);