Java ArrayList vs CopyOnWriteArrayList

ArrayList:

ArrayList is a basic implementation of List interface in Collection framework.It extends AbstractList. ArrayList supports dynamic array that can grow as needed.

Some of the important methods in ArrayList are

void add(int index,Object element):add the element at the specified index.
void add(Object element): Add the element at the end of the list.
void  clear(): clears the list when called on the list.
Object remove(int index): Remove the element at the specified location

We need an iterator to iterate over the list. ArrayList iterator is fail-fast by design.That means as soon as the underlying data structure changes after creating iterator it will throw java.util.ConcurrentModificationException.


Internally when we create an array list, it will maintains a modCount variable which will keep track of the modification count and every time we use add, remove or trimToSize method, it increments. expectedModCount is the iterator variable that is initialized when we create iterator with same value as modCount. This explains why we don’t get exception if we use set method to replace any existing element.

So basically iterator throws ConcurrentModificationException if list size is changed.

Let's run the program to see 

 package misc;  
 import java.util.ArrayList;  
 import java.util.Iterator;  
 import java.util.List;  
 public class CopyOnArrayListExample {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           List<String> list = new ArrayList<String>();  
           list.add("James Gosling");  
           list.add("Brendan Eich");  
           list.add("Rod Johnson");  
           list.add("Gavin King");  
           list.add("Un Known");  
           Iterator<String> itr = list.iterator();  
           while (itr.hasNext()) {  
                String str = itr.next();  
                System.out.println(str);  
                if(str.equals("Un Known")) list.remove("Un Known");}  
      }  
 }  

Output:

Exception in thread "main" java.util.ConcurrentModificationException
at java.util.AbstractList$Itr.checkForComodification(AbstractList.java:372)
at java.util.AbstractList$Itr.next(AbstractList.java:343)
at misc.CopyOnArrayListExample.main(CopyOnArrayListExample.java:30)

As you can see, ArrayList iterator doesn't allow concurrent modification when we iterating.If we need to do concurrent modification then we need  CopyOnWriteArrayList.

Lets see CopyOnWriteArrayList in action.

package misc;  
 import java.util.Iterator;  
 import java.util.List;  
 import java.util.concurrent.CopyOnWriteArrayList;  
 public class CopyOnArrayListExample {  
      /**  
       * @param args  
       */  
      public static void main(String[] args) {  
           List<String> list = new CopyOnWriteArrayList<String>();  
           list.add("James Gosling");  
           list.add("Brendan Eich");  
           list.add("Rod Johnson");  
           list.add("Gavin King");  
           list.add("Un Known");  
           Iterator<String> itr = list.iterator();  
           while (itr.hasNext()) {  
                String str = itr.next();  
                System.out.println(str);  
                if(str.equals("Un Known")) list.remove("Un Known");}  
      }  
 }  

In above code, we just changed the class definition from ArrayList to CopyOnWriteArrayList and see the output below.

James Gosling
Brendan Eich
Rod Johnson
Gavin King
Un Known

As you can see, the above code doesn't throw any exception as this one is thread safe variant of ArrayList.

Few things about CopyOnWriteArrayList from official documentation

A thread-safe variant of ArrayList in which all mutative operations (add, set, and so on) are implemented by making a fresh copy of the underlying array.
This is ordinarily too costly, but may be more efficient than alternatives when traversal operations vastly outnumber mutations, and is useful when you cannot or don't want to synchronize traversals, yet need to preclude interference among concurrent threads. The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException. The iterator will not reflect additions, removals, or changes to the list since the iterator was created. Element-changing operations on iterators themselves (remove, set, and add) are not supported. These methods throw UnsupportedOperationException.

All elements are permitted, including null.

Memory consistency effects: As with other concurrent collections, actions in a thread prior to placing an object into a CopyOnWriteArrayList happen-before actions subsequent to the access or removal of that element from the CopyOnWriteArrayList in another thread.

Thanks for visiting my blog!!!!!!!!

Binary Search-Sample program in Java

What is Binary Search by the way?

A binary search or half-interval search algorithm finds the position of a specified input value (the search "key") within an array sorted by key value.[1][2] For binary search, the array should be arranged in ascending or descending order. In each step, the algorithm compares the search key value with the key value of the middle element of the array. If the keys match, then a matching element has been found and its index, or position, is returned. Otherwise, if the search key is less than the middle element's key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the search key is greater, on the sub-array to the right. If the remaining array to be searched is empty, then the key cannot be found in the array and a special "not found" indication is returned.
(Source: WikiPedia)

The requirement for binary search algo is the array should be sorted.We can use Quick Sort or Merge Sort for sorting the array.First we need to take mid element(if low=0 and high=array.length-1 then mid=low+high/2).If the middle element is the one which we are searching we return the index or we just print the element is found in the array at a specified index.

Lets say the element we are searching is less than the middle element then we will take the sub array by specifying high=mid-1 or if the searching element is greater than the middle element then our sub array becomes low=mid+1.This process will continue until we found the element we are searching.

Code:

/**
 * @author RameshM
 * 
 *         Sample program for Binary Search
 */
public class BinarySearchTest {

 public static boolean searchKey(int[] intArray, int element) {

  int low = 0;
  int high = intArray.length - 1;

  while (low <= high) {
   int middle = (low + high) / 2;
   if (element > intArray[middle]) {
    low = middle + 1;
   } else if (element < intArray[middle]) {
    high = middle - 1;
   } else {
    return true;
   }
  }
  return false;
 }

 public static void main(String args[]) {

  int[] intArray = { 2, 4, 5, 8, 9, 22, 44, 55, 66, 88, 100 };

  int element = 44;

  boolean result = searchKey(intArray, element);

  if (result) {
   System.out.println("The element found in the Array");
  } else {
   System.out.println("The element is not found in the Array");
  }

 }
}

Output:

The element found in the Array

Java 1.7 features

Below are the important features introduced in 1.7 in developers point of view.

1)Strings in switch statement
2)The try-with-resources Statement
3)Binary Literals
4)Underscores in numerical Literals
5)Catching Multiple Exception Types and Rethrowing Exceptions with Improved Type Checking
6)Type Inference for Generic Instance Creation

How can a class extends another class, extends Object? Is it not multiple inheritance which is not allowed in Java?

Let me explain

We know every class in java extends Object class.Lets say if you have a class Employee

public class Employee{  
 private String name;  
 // getters and setters  
 }  

Then this class implicitly like this

public class Employee extends Object{  
 private String name;  
 // getters and setters  
 }  

But if your class extends another class explicitly then 

 public class Employee extends BaseEmployee{  
 private String name;  
 // getters and setters  
 }  

Then your Employee class doesn't extends Objects class.Instead your BaseEmployee will extends Object class.

Hope you get it ;)

Java 1.5 features

Java 1.4 -> Java 1.5

These are the most important features added in Java 1.5

1)Generics
2)Enhanced for loop
3)Auto Boxing and Unboxing
4)Type Safe Enums
5)Varargs
6)Static Imports
7)Annotations or Metadata

There are other changes also but the above are the important from the developer's perspective.