5-Collections

-------------------------------------------------------------------------------------------------------------------------

Set : (HashSet, LinkedHashSet, TreeSet)

3 general implementations of Set:

• To retrieve elements from the Set, we can either use Iterator or for-each loop.
• Random access to an element in a set not allowed.

HASHSET(unsortedSet):

• does not guarantee any insertion and iteration orders.
• Is a hash-based implementation and internally it
• uses HashMap which is one of the Map implementations.
• (Applies to all other sub Sets-----------------------------------------------------)
• Different ways of implementing::
• Set empty = new HashSet(); //{}
• Set even = new HashSet(Arrays.asList(0,2,4)); //{0, 2, 4} -- (*)
• Set copy = new HashSet(even); //create from existing Set
• Set blank = new HashSet(8); //initial capacity 8
• Set nullSet = new HashSet(8, 1); //initial capacity 8, load factor 1
• Add an element : even.add(6); //{0, 2, 4, 6}----(*)
• Add all of element of S2 to S3: s3.addAll(s2); //s3 = {1, 2, 3, 4, 5}
• Remove an element: even.remove(4); //{0, 2, 6, 8}
• Remove All: even.clear(); //{}
• Remove elements common in S2 AND S3 from S3: s3.removeAll(s2); //s3 = {1}
• Existence of an element: boolean c1 = even.contains(6); //c1 = true
• Check for Emptiness: boolean e1 = even.isEmpty(); (or) if(blank.size() == 0) ;
• To Array from elements : Object[] a = even.toArray();
• Retain only s2 elements in s3: s3.retainAll(s2); //s3 = {2, 3}
• Synchronize a Hashset using Collections: Set syncSet = Collections.synchronizedSet(new HashSet());
• (Applies to all other sub Sets-----------------------------------------------------)

LinkedHASHSET(unsortedSet):

• Unlike Hashset, LinkedHashset is ordered.
• It is an extension to HashSet and uses linked list and hash table internally.
• As it maintains a linked list, it exhibits slightly slower performance than HashSet.
• SAME operation APIs as Hashset
• Synchronized same as Hashset: Set syncSet = Collections.synchronizedSet(new LinkedHashSet());

TreeSet(sortedSet):

• does natural ordering on its elements. Also accepts a custom comparator for custom ordering.
• log(n) time cost for the basic operations such as add(), remove() and contains().
• SAME operation APIs as Hashset. Note that adding occurs in a sorted order. So, if u add an element, it is placed at the sorted location.
• let, SortedSet ss = new TreeSet(Arrays.asList(2,3,5)); //{2,3,5}
• ss.add(1); //ss = {1, 2, 3, 5}
• ss.add(4); //ss = {1, 2, 3, 4, 5}
• Synchronized same as Hashset: Set syncSet = Collections.synchronizedSet(new TreeSet(Arrays.asList(2,3,5)));
• Additional Methods for a TreeSet are:
• Object fe = ss.first(); //fe = 1
• Object le = ss.last(); //le = 5
• SortedSet s1 = ss.headSet(3); //s1 = {1, 2}-- returns all elements < "3"
• SortedSet s2 = ss.tailSet(3); //s2 = {3, 4, 5}--returns elements >="3"
• SortedSet s3 = ss.subSet(2, 5); //s3 = {2, 3, 4}-- >=2 and <5

***

Iterator:are APIs used to Iterate over SET implementations.we can either use Iterator or for-each loop to retrieve elements from a set.

• hasNext() – Returns true if there are more elements in the collection; false otherwise
• next() – Returns the next element
• remove() – Deletes the last element returned from the collection

Example of Iterating over Set using Iterator API:

Iterator i = setImplementatiomVariable.iterator();

while(i.hasNext()) System.out.print(i.next()+" ");

(or)

for(Iterator i = even.iterator();i.hasNext();)

System.out.print(i.next()+" ");

-------------------------------------------------------------------------------------------------------------------------

List : (ArrayList, LinkedList, Vector)

3 general implementations of List:

• Unlike sets, lists are ordered collection and
• allow duplicate elements.
• In addition to normal Iterator, List interface provides a special iterator, called a ListIterator, that unlike Iterator allows insertion and replacement of elements. Allows bidirectional traversal of the list,element.
• ListIterator li = l.listIterator(); //sets cursor at the begining
• while(li.hasNext()) System.out.print(li.next()+" ");
• O/P: 2->3->4->2
• 
  
• while(li.hasPrevious()) System.out.print(li.previous()+" ");
• O/P: 2->4->3->2

ArrayList:

• As elements are added and removed, its capacity grows or shrinks automatically.
• a high capacity may be specified using ensureCapacity(), to reduce incremental reallocation.
• List el = new ArrayList(); //empty list
• List l = new ArrayList(Arrays.asList(2,3)); //l = 2->3
• List l1 = new ArrayList(10); //empty, initial capacity 10
• Add elements using the index(if given, else append at the end)
• l.add(2); //append, l = 2->3->2
• l.add(2, 4); //insert 4 at index 2, l = 2->3->4->2
• Update :
• l.set(0, 4); //l = 4->2
• Remove:
• l.remove(2); //remove element from index 2, l = 2->3->2
• l.remove(new Integer(3)); //remove the element 2, l = 2->2
• Remove All: l.clear(); //l=
• retrieve : Object obj = l.get(1); //obj = 3
• retrieve sublist: List sl = l.subList(1, 3); //sl = 3->4
• retrieve based on index:
• int first = l.indexOf(2); //first = 0;
• int last = l.lastIndexOf(2); //last = 1;
• Check for Emptiness: boolean e1 = l.isEmpty(); (or) if(l.size() == 0) ;
• Synchronize a ArrayList using Collections: Set syncSet = Collections.synchronizedSet(new ArrayList());

LinkedList(implements two collection interfaces, List and Deque):

• SAME operation APIs as ArrayList.
• Synchronize a LinkedList using Collections: Set syncSet = Collections.synchronizedSet(new LinkedList());

-------------------------------------------------------------------------------------------------------------------------

Queue: (Queue,Stack) -casting LinkedList/ PriorityQueue

• Like List, it also represents an ordered collection of elements
• generally do not accept null elements.
• Queues implementations can order elements in 
• FIFO (queue), 
• LIFO (stack)
• and priority basis.
• provides two forms of methods for inserting, deleting and inspecting elements.
• One form throws an exception if the operation fails. 
• The other form returns a special value such as null or false, depending on the operation.

casting LinkedList to Queue(implements two collection interfaces, List and Deque):

• By default, queues are FIFO ordered-Queue
• ways to implement queues by casting to LinkedList:
• Queue empty = new LinkedList(); //empty queue
• Queue q = new LinkedList(Arrays.asList(1,3)); //q = 1->3
• Add:
• q.add(5); //q = 1->3->5
• q.offer(7); //q =  1->3->5->7
• Delete:
• q.remove(); //q = 3->5->7.. and returns 1(1st addede element)
• q.poll(); //q = 5->7
• Retrieve element at the head of the queue(without deleting):
• Object e = q.element(); //e = 5
• Object e1 = q.peek(); //e1 = 5
• a LIFO ordered queue (i.e. stack) may be created as follows:
• Queue lifo = Collections.asLifoQueue(new LinkedList());
• add and remove perform addition and removal in the opposite direction compared to queue.

casting PriorityQueue to Queue:

• least(element with lowest value) element always sits at the top (head). Refer add()
• Element’s class must implement Comparable interface which has comparison method compareTo().
• ways to implement queues by casting to PriorityQueue:
• Queue empty = new PriorityQueue(); //empty queue
• Queue q = new PriorityQueue(Arrays.asList(7,4,5)); //q = 7->4->5
• Add:
• q.add(3); //3 is at head
• q.add(6); //3 is still at head
• q.offer(2); //2 is at head
• Delete/Retrieve(same as casting to LinkedList): 
• Delete:
• q.remove(); 
• q.poll();
• Retrieve element at the head of the queue(without deleting):
• Object e = q.element(); 
• Object e1 = q.peek(); 

-------------------------------------------------------------------------------------------------------------------------

MAP: 

(HashMap, HashTable, TreeMap(implements SortedMap which inturn implements Map))

general implementations of MAP:

• This interface models a set of key-value pairs.
• The keys are unique and each key corresponds to one value.
• Common APIS for all MAP implementations:
• put() 
• get()
• remove("keyStr") - remove entry from map corresponsding to key value "keyStr"
• clear() -removes all the entries from the map.
• containsKey()
• containsValue()
• size()
• isEmpty()
• keySet() - returns a Set of all keys
• values() - returns a Collection of all values in the map
• entrySet(); - returns a set of Map.Entry objects each of which consists of a key and a value

HashMap:

• does not also ensure any ordering.
• Map syncMap = Collections.synchronizedMap(new HashMap());
• Alternatively, we may use java.concurrent.ConcurrentHashMap which is thread-safe version of HashMap. 
• ConcurrentHashMap also used instead of HashMap to obtain FailSafe condition(Failfast - exception thrown of new element added during iteration of the Map))
• offers constant time [i.e. O(1)]
• Each HashMap object is characterized by two parameters: capacity and load factor. The capacity is the number of buckets in the hash table. The load factor controls when to rebuild the internal data structures.
• Ways to implement HashMap:
• Map m = new HashMap(); //empty map
• Map m1 = new HashMap(8); //initial capacity 8
• Map m2 = new HashMap(6, 1); //initial capacity 6, load factor 1
• Map m3 = new HashMap(m); //m3 = m

LinkedHashMap:

• LinkedHashMap is ordered. It extends HashMap and uses a doubly linked list and hashtable internally.
• All others applies same as HashMap.

TreeMap(Implements SortedMap):

• entries are ordered wrt key in natural ordering (or) Comparator specified during map creation
• log2(n) time for get(), put(), remove() and containsKey() methods
• Ways to implement TreeMap:
• SortedMap sm = new TreeMap(); //empty map
• SortedMap sm1 = new TreeMap(sm); //create from existig sorted map
• get an unsorted Map implemenetaion sorted as below:
• Map m = new HashMap();
• m.put("uttam","uttam1"); //add some entries
• m.put("bibhas","bibhas1");
• m.put("parama","parama1");
• m.put("samiran","samiran1");
• sm = new TreeMap(m); //get sorted from unsorted one
• 
  
• This results in the following sorted order:
• bibhas->bibhas1
• parama->parama1
• samiran->samiran1
• uttam->uttam1
• The two special keys—the lowest (first) and the highest (last) keys are obtained as follows:
• String k1 = (String)sm.firstKey(); //k1 = "bibhas"
• String k2 = (String)sm.lastKey(); //k2 = "uttam"
• the head and tail views may be retrieved as:
• SortedMap hm = sm.headMap("samiran"); //hm = {bibhas=bibhas1, parama=parama1}
• SortedMap tm = sm.tailMap("samiran"); //tm = {samiran=samiran1, uttam=uttam1}

-------------------------------------------------------------------------------------------------------------------------

Reference of below screenshot: