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).
Maps are not the Part of Collection Framework
- 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).
- List
- Set
- Duplicates are not allowed
- Insertion Order not Preserved
- Set →HashSet →LinkedHashSet
- SortedSet (I)
- Collection →Set →SortedSet → NavigableSet (TreeSet class is the implementation) (v 1.2)
- Elements are inserted in sorted order
- NavigableSet (I)
- Child Interface of Sorted Set
- TreeSet Class Provides the Implementation
- Queue (I)
All Above keeps groups of objects. For Key value pairs, Maps(I) is used. (Not in Collection Framework)
- Map (I), not in Collection
- SortedMap(I)
- Map(I) →SortedMap
- NavigableMap
Cursors in Java
- Enumeration
- Iterator
- List Iterators
Sorting
- Comparable(I) : Default natural sorting order
- Comparator(I) : Customized Sorting
Utility Classes
- Collections
- 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
- Enumeration (Interface)
- Iterator (I)
- 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:
- public boolean hasNext();
- public Object next();
- 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
- TreeSet t = new TreeSet(); //Default Natural Sorting Order
- 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
- obj1.compareTo(obj2)
- 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);