Saturday, January 4, 2014

Basics of Collections in Java

Back to basics again. Let's see what Collections are about.
Collection is a set of object or group of objects and framework provides a defined set of functions to access or evolve. So, Collections Framework provides set of functions to manipulate set of objects.
Briefly, Collections consists of
  • Interfaces: Abstract datatypes which represents the collections.
  • Implementations: Classes which implements the above interfaces. 
  • Algorithms: Methods which performs the operations on the collections. 
Note: Map is not a collections but has the above features. Map is an object which stores the data in key/value pairs.
The below figure shows the brief overview of the Collections. [Green - Interfaces and Violet - Classes]

Explanation:

List: 

  • List allows the data to be stored in re-sizable container.
  • Elements can be accessed randomly by using position i.e index
  • Elements are sorted in order of insertion. 
  • List is an interface, it is implemented by 
    • ArrayList - In one word it's a re-sizable array. But it has one parameter intialCapacity - the number of elements it can hold maximum before it grows.
    • LinkedList - Its implemented as Double linked list. The performance of write operation is better than ArrayList.

Queue:

  • Queue stores a series of elements for processing. (In other words it's sorted list).
  • Queue has the special logic for insertion and removal of the elements 
  • Queue is implemented by
    • PriorityQueue - It imposes the ordering during construction of it or by using Comparator. It has special methods to access - poll, remove, peek, element
    • LinkedList - Linked list is also an implementation of Queue (also of List).

DeQueue:

  • Dequeue is Double ended Queue (It extends Queue). 
  • The operations can be performed from both the ends. 
  • Its implemented by ArrayDequeue
  • It has methods to perform- 
    • addFirst, removeFirst, pollFirst etc for the elements at the beginning
    • addLast, removeLast, pollLast etc for the elements at the end. 

Set:


  • Set interface works exactly same as mathematical Set. 
  • It cannot contain duplicate elements. 
  • Set is implemented by
    • HashSet - Its a plain vanilla implementation of Set. It doesn't guarantee the order of the elements stored but cannot contain duplicates. It used Hash table for storing the data.
    • LinkedHashSet - It also uses hash table but carries the insertion order like List.

SortedSet

  • SortedSet as the name explains it's a sorted implementation of set. (Extends Set)
  • SortedSet is implemented by
    • TreeSet - It stores the elements in order but performance is a bottle-neck. HashSet is much faster than TreeSet
Note: Basic data types like (int, char, double etc) cannot be used as type in Collections. Instead use Wrapper classes (Integer, Double etc).

Which Collection to Use

Based on the case we are implementing, the collections to be use will be changed.
  • Iterating: Each of the collections implements Iterable. So when iterate over all the elements.
  • Random Access: All the list implementation allows random access.
  • Duplicates: Sets dont allow duplicates whereas others allows.
  • Ordering: Each collection has it own way of ordering but explicit ordering can be using by using Comparator
    • Sorted Order - SortedSet, PriorityQueue has can impose ordering while creation
    • Insertion Order - List implements allows the ordering based on the insertion.
    • No ordering - Set, Queue (Other than PriorityQueue) doesn't impose any ordering
  • Key-Value pair: HashMap allows the key-value pair.
  • Operation Performance: Always the sorted collections are bit poor in performance. In addition to that, the above four selections also adds to it.
We will see more about features of Collections in future posts. Happy Learning!!!!