TreeSet Quick Reference

TreeSet elements are sorted according to their natural ordere if created using default constructor( new TreeSet()), or by a  Comparator if TreeSet object is created by passing Comparator to  constructor ( new TreeSet(comparator))
·         If TreeSet object is created using default constructor then all elements inserted into the set must implement the Comparable interface else you will get exception while adding elements to TreeSet instance.
java.lang.ClassCastException: xxxx cannot be cast to java.lang.Comparable
·         All elements inserted into the set must be of same type. e.g. you can not add String into a set whose elements are Integers
·         provides guaranteed log(n) time cost for the contains, add and remove operations.
·         Does not allows null element. If null element is added then it will throw NullPointerException at runtime. Whereas, hashset allows one null value
·         A TreeSet is not synchronized. Means it's methods are not synchronized.
·         In multi-threaded environment, to prevent accidental unsynchronized access to the TreeSet to a thread that can modify this set, wrap TreeMap instance using Collections.synchronizedSortedSet method
                SortedMap m = Collections.synchronizedSortedSet(new TreeSet(...));
·         The iterators returned by this class's iterator methods are fail-fast. If the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException.
·         Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. But one must not write program that depends on this behaviour.
·         add(E e) method returns false if set already contains the element e

TreeMap Quick Reference

·         TreeMap object is sorted according to the natural ordering of its keys if created using default constructor( new TreeMap()), or by a  Comparator if TreeMap object is created by passing Comparator to  constructor ( new TreeMap(comparator))

·          Provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.

·         If TreeMap object is created using default constructor then all keys inserted into the map must implement the Comparable interface else you will get exception while adding key-values to TreeMap instance.

java.lang.ClassCastException: xxxx cannot be cast to java.lang.Comparable

·         All keys inserted into the map must be of same type. e.g. you can’t add integer as a key into a map whose keys are String

·         Does not allows null keys, valuse can be null.

·         A TreeMap is not synchronized. Means its methods are not synchronized.

·         In multi-threaded environment, to prevent accidental unsynchronized access to the TreeMap that can modify it, wrap TreeMap using Collections.synchronizedSortedMap method

               SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

·         The iterators returned by this class's iterator methods are fail-fast. If the map is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException.

·         Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. But one must not write program that depends on this behaviour.

·         There are multiple ways to iterate over TreeMap

//create TreeMap instance

    TreeMap treeMap = new TreeMap();

    //add key value pairs to TreeMap

    treeMap.put("1","A");

    treeMap.put("2","B");

    treeMap.put("3","C");

1. Iterator using Collection values() - only iterate TreeMap's values

Collection c = treeMap.values();

Iterator itr = c.iterator();

while(itr.hasNext())

      System.out.println(itr.next());

2. Iterator using entrySet() - iterate TreeMap's keys and values in map form

for (Map.Entry entry : treeMap.entrySet()) {

        V value = entry.getValue();

        K key = entry.getKey();

   }

3. Iterator using keySet() - iterate TreeMap's keys which can be used to get values

Set keys = map.keySet();

   for (Iterator i = keys.iterator(); i.hasNext();) {

     Integer key = (Integer) i.next();

     String value = (String) map.get(key);

   }

Note : If the TreeMap is modified while an iteration over the collection/set is in progress (except through the iterator's own remove operation, the results of the iteration are undefined.The collection/set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.remove, removeAll, retainAll, and clear operations.  It does not support the add or addAll operations.

·         put(K key, V value) method returns previous value associated with key, or null if there was no mapping for key. If the map previously contained a mapping for the key, the old value is replaced with new value.

HashSet Quick Reference

• Backed by a hash table (actually a HashMap instance)
• While iterating HashSet the order of elements are not guaranteed
• Offers constant time performance for the basic operations add, remove, contains and size
• In multi-threaded environment, to prevent accidental unsynchronized access to the HashSet that can modify HashSet, wrap HashSet using Collections.synchronizedSet method

      Set s = Collections.synchronizedSet(new HashSet(...));

• The iterators returned by this class's iterator methods are fail-fast. If the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException.
• Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. But one must not write program that depends on this behaviour.
• iterator()method returns an iterator over the elements in this set. The elements are returned in no particular order.
• boolean add(E e) method Adds the specified element e to this set if it is not already present and return true. If this set already contains the element e then the set remains unchanged and method returns false.
• Hashset allows one null value

LinkedList Quick Reference

• Doubly-linked list implementation of the List and Deque interfaces.
• Can be used in implementing Stack and Queue as it has methods/operations like peek, poll, offer, push, pop
• In multi-threaded environment, to prevent accidental unsynchronized access to the LinkedList that can modify LinkedList structurally, wrap ArrayList using Collections.synchronizedList method
List list = Collections.synchronizedList(new LinkedList(...));

• The iterators returned by this class's iterator and listIterator methods are fail-fast if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException.
• Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. But one must not write program that depends on this behaviour.
• boolean add(E e) method Appends the specified element e to the end of this list and after addition return true
• boolean remove(Object o) method Removes the first occurrence of the specified element from this list and returns true if this list contained the specified element, else return false. Whereas, remove(int index) method removes the element at the specified position in this list and returns the removed element

ArrayList Quick Reference

• It’s a Resizable-array implementation of the List interface
• permits all elements, including null
• equivalent to Vector, except that it is unsynchronized( i.e. it’s methods are unsynchronized)
• Following operations run in constant time – get, set, iterator, listIterator
• In case of add operation, adding n elements requires O(n) time
• In multi-threaded environment, to prevent accidental unsynchronized access to the ArrayList  that can modify ArrayList structurally, wrap ArrayList using Collections.synchronizedList
List list = Collections.synchronizedList(new ArrayList(...));
• The iterators returned by this class's iterator() and listIterator(int) methods are fail-fast if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove() or add(Object) methods, the iterator will throw a ConcurrentModificationException.
• Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. But one must not write program that depends on this behaviour.
• ArrayList internally implements growable dynamic array which means it can increase and decrease its size automatically. If we try to add an element to a already full ArrayList then it automatically re-sized internally to accommodate the new element
• Consider a scenario when there is a need to add huge number of elements to an already full ArrayList, in such case ArrayList has to be resized several number of times which would result in a poor performance. For such scenarios ensureCapacity() method of ArrayList class is very useful as it increases the size of the ArrayList by a specified capacity.
public void ensureCapacity(int minCapacity)

• toArray() mathod returns an array containing all of the elements in this list in proper sequence (from first to last element).So, this method acts as bridge between array-based and collection-based APIs.
• remove(int index) method removes the element at the specified position(index) in this list. Shifts any subsequent elements to the left and return the element that was removed from the list
• remove(Object o) method removes the first occurrence of the specified element from this list, if it is present and return true if this list contained the specified element else return false.

HashMap Quick Reference

• Permits multiple null values and one null key

• Equivalent to Hashtable, except that it is unsynchronized( i.e. it’s methods are unsynchronized) and permits nulls (Hashtable does not allows null keys or values)

• Does not guarantee that the order of map will remain constant over time.

• Provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets.

• Iteration time is proportional to the "capacity" of the HashMap instance plus its actual size

• In multi-threaded environment, to prevent accidental unsynchronized access to the map that can modify HashMap structurally, wrap HashMap using Collections.synchronizedMap

Map m = Collections.synchronizedMap(new HashMap(...));

• Iterators of HashMaps are fail-fast

• Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. But one must not write program that depends on this behaviour.

• get() method returns the value to which the specified key is mapped, or null if this map contains no mapping for the key. However, null does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to null.

• When duplicate key put into HashMap, put() method overrides old value with new value and returns the old value. put() method returns null if this map contains no mapping for the key. However, a return value of null does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to null.