Java Collections

Proper understanding of the java collections framework is must for any java programmer.Be it for interview or coding.The following topic will focus on the available collection implementations and advantages/disadvantages of each.

Why Collections when you have arrays ?

1] Arrays are fixed length.Hence we need to know the maximum number of elements the array could hold i.e the length of the array or its capacity.When you need to add elements to an array you need to know how many elements you need to add to the array.You cannot add elements more than the length of the array in which case it would throw an exception,probably ArrayIndexOutOfBound. However if you want to add elements more than the capacity of the array its not a dead end for you :).You can still resize the length of the array to hold more elements as explained in the next step.

2] Incase you need to add elements more than the length of the array, you will need to do the following steps.

a) Create a new array with a new capacity.

b) Copy the elements of the old array to the new array.

c) Make the old array reference to point to the newly created array.

3] If you need to insert into the beginning or the middle of the array @ a particular position then you need to make room for the element by shifting all the existing elements one place to its right from the position where the elements needs to be inserted.

e.g. An array had the following elements -

| 1 | 2 | 3 | 5 | 6 | 7 | 8 | 9 |

Now if if you want to insert data 4 at position 3 (3 bcoz the index starts from 0..1..2..3) then i would need to shift 9 One Place To Right (OPTR), then 8 OPTR, 7 OPTR ..... and finally 5 OPTR.This makes a room for my new element 4 at position 3.

Thus inserting at the beginning or middle would take operations propertional to the length of the array from the position of insertion.Hence inserting at the very beginning would be least effecient than at the middle.

Also as discussed in 2] if the array is full then there would be another overhead of allocating new array, copying the old elements into the new array and then doing the insertion at a particular position which would take a lot of time.This is where the other data structure implementations of java comes to the rescue.

Java Collections

A Collection in java basically means collection of objects.There are 2 types of collections in java.

1] List & 2] Set.

Lists -

The elements added to the list need not be unique i.e you can add duplicates in a list.Also list allows you to add elements at a particular index.One need not worry about the reallocating memory as is the case in arrays.The List implementations takes care of it.

In Java there are 3 concrete implementation classes representing the List.All the 3 classes implements the List interface which in turn extends the Collection interface.

1] ArrayList - A list of elements which is not thread safe using resizable array concept.

2] Vector - A list of elements which is thread safe using resizable array concept.

3] LinkedList - A list of elements using the linked list concept.

Click here for details

Set -

Set on the other hand represents a mathematical set in which the elements are unique.

In Java there 3 concrete classes representing a set.All the 3 classes implements the Set interface which in turn extends the Collection interface.

1] HashSet - A set of unordered elements which uses hashing concept.

2] LinkedHashSet - A set of ordered elements which uses doubly linked list + hashing concept.

3] TreeSet - A set of elements whose ordering can be defined if required.

Click here for details