My notes on Collections framework

Java Collections Framework :

1] ArrayList

  • Usage : List<Integer> list = new ArrayList<Integer>();
  • You can specify initial size of arraylist. But by default it’s 10.
  • In ArrayList, elements are stored in array internally. [0][1][2][3][4][5][6] …
  • If initially you have created array list of size 10. And you try to add 11th item in the list, it will internally create new array of twice the size and copy all the old elements in new array.
  • Removing elements from the end of an ArrayList is quick because it just decrements the size of array internally. If removing elements from the beginning or the middle of the list, it copies subsequest elements one step back. And this adjustment of indexes causes the removal operation slow.
  • Adding elements to the beginning of array list will be slow.
  • If you want to add elements and remove from the end of the list, use array list.

2] LinkedList :

  • Usage : List<Integer> list = new LinkedList<Integer>();
  • LinkedList contains elements where each element has reference to previous and next element.
    [0]->[1]->[2]->[3] …
    <- <- <-
  • Getting elements from linked list or traversing linked list is slow because every element has to get reference to next item and so on till you reach the desired index.
  • This collection is heavyweight and consumes more memory than ArrayList.
  • If there is need to add / remove elements from list from the beginning or middle, consider using other lists LinkedList.
  • Adding new element in the linkedlist creates a new node and points it with the next node and previous node is pointed to new node.
  • Removing element from linked list removes the previous and next references of node / element.

3] HashMap :

  • Usage : Map<String, Integer> map = new HashMap<String, Integer>();
  • Maps store pair of values. One member is called ‘Key’ and other one is called ‘Value’. Map is basically a lookup table.
  • You can use anything as key of map. But while using your custom object as map key, that object should have hashCode and equals methods implemented.
  • Though we provide wrapper or non-premitive type while declaring map, for e.g. Integer. But while putting elements in map, premitives are avoid because java automatically auto box them to non-premitive.
  • If you try to get the value that doesn’t exist in your map, it returns null.
  • If you try to add duplicate key into map, it overrides the previous entry.
  • Iterating a map :
  • for(Map.Entry entry : map.entrySet()) {
    String key = entry.getKey();
    int value = entry.getValue();
    }

  • Another way is :
  • for(String key : map.keySet()) { // map.keySet() method returns the collections of keys in the form of Set (Collection).
    int value = map.get(key);
    }

  • HashMap is not sorted in any way. It does maintain order.

4] LinkedHashMap :

  • HashMap does not maintain order, so if you want elements to be in order as they are put in you can use LinkedHashMap.
  • LinkedHashMap manages doubly linked list connecting the entries. This allows the elements to be in order as they are put in.

5] TreeMap :

  • TreeMap sorts the keys in natural order. Natural order for integers is numerical order (1, 2, 3, ….) and for Strings it is alphabetical order (a,b,c,d, …). You can define natural order for your custom objects also.

6] HashSet :

  • Usage : Set<String> set = new HashSet<String>();
  • Set is a collection which stores only unique elements.
  • Sets manages arrays internally. HashSet is lightweight.
  • Adding duplicate elements in set has no effect. Adding duplicate items does nothing. (HashMap overrides old entry with the new one.)
  • HashSet does not retain order. It can and will spotaneously rearrange themselves according to the no particular logic.
  • Iterating all kinds of sets :
  • for(String item : set) {
    Sysout(item);
    }

  • We can check if given item is there in set or not quickly. Sets are optimized to do this. Use set.contains() method. Returns either true or false.

7] LinkedHashSet :

  • LinkedHashSet remembers the order of elements put in.
  • This manages doubly linked list internally, where each element has reference to previous and next element. Which makes this collection to maintain order of elements.

8] TreeSet :

  • If you want added elements to be sorted in their natural order, use TreeSet.
  • For Strings natural order is alphabetical order whereas for integers it is numeric.

9] Using custom objects in sets and maps :

  • Not implementing hashCode and equals methods in class which you are going to use as key for map, will not allow all the objects regardless of their equality. So to make it clear which objects are equal, we need to implement these methods. The same applies for sets as well.
Advertisements

2 thoughts on “My notes on Collections framework

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s