Looping ArrayList

Here are the three ways to loop through the ArrayList.

import java.util.*;
import java.lang.*;

class Rextester
{ 
    public static void main(String args[])
    {
        List<Integer> list = new ArrayList<Integer>();
        list.add(10);
        list.add(20);
       
        for(int i=0;i<list.size();i++)
        {
            System.out.println(list.get(i));
        }
       
        for(Integer num : list)
        {
            System.out.println(num);
        }
       
        Iterator<Integer> it = list.iterator();
        while(it.hasNext())
        {
            System.out.println(it.next());
        }
    }
}

ArrayList Vs Vector

1) Synchronization: ArrayList is non-synchronized which means multiple threads can work on ArrayList at the same time. For e.g. if one thread is performing an add operation on ArrayList, there can be an another thread performing remove operation on ArrayList at the same time in a multithreaded environment
while Vector is synchronized. This means if one thread is working on Vector, no other thread can get a hold of it. Unlike ArrayList, only one thread can perform an operation on vector at a time.
2) Resize: Both ArrayList and Vector can grow and shrink dynamically to maintain the optimal use of storage, however the way they resized is different. ArrayList grow by half of its size when resized while Vector doubles the size of itself by default when grows.
3) Performance: ArrayList gives better performance as it is non-synchronized. Vector operations gives poor performance as they are thread-safe, the thread which works on Vector gets a lock on it which makes other thread wait till the lock is released.
4) fail-fast: First let me explain what is fail-fast: If the collection (ArrayList, vector etc) gets structurally modified by any means, except the add or remove methods of iterator, after creation of iterator then the iterator will throw ConcurrentModificationException. Structural modification refers to the addition or deletion of elements from the collection.
As per the Vector javadoc the Enumeration returned by Vector is not fail-fast. On the other side the iterator and listIterator returned by ArrayList are fail-fast.
5) Who belongs to collection framework really? The vector was not the part of collection framework, it has been included in collections later. It can be considered as Legacy code. There is nothing about Vector which List collection cannot do. Therefore Vector should be avoided. If there is a need of thread-safe operation make ArrayList synchronized as discussed in the next section of this post or use CopyOnWriteArrayList which is a thread-safe variant of ArrayList.
There are few similarities between these classes which are as follows:

1. Both Vector and ArrayList use growable array data structure.
2. The iterator and listIterator returned by these classes (Vector and ArrayList) are fail-fast.
3. They both are ordered collection classes as they maintain the elements insertion order.
4. Vector & ArrayList both allows duplicate and null values.
5. They both grows and shrinks automatically when overflow and deletion happens.

When to use ArrayList and when to use vector?

It totally depends on the requirement. If there is a need to perform “thread-safe” operation the vector is your best bet as it ensures that only one thread access the collection at a time.
Performance: Synchronized operations consumes more time compared to non-synchronized ones so if there is no need for thread safe operation, ArrayList is a better choice as performance will be improved because of the concurrent processes.
How to make ArrayList synchronized?
As I stated above ArrayList methods are non-synchronized but still if there is a need you can make them synchronized like this –

//Use Collecions.synzhonizedList method
List list = Collections.synchronizedList(new ArrayList());
...

//If you wanna use iterator on the synchronized list, use it
//like this. It should be in synchronized block.
synchronized (list) {
  Iterator iterator = list.iterator();
  while (iterator.hasNext())
      ...
      iterator.next();
      ...
}

This content is from : http://beginnersbook.com/2013/12/difference-between-arraylist-and-vector-in-java/ 

ArrayList Vs LinkedList

1) Search: ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).
Reason: ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.
2) Deletion: LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in worst case (while removing first element) and O(1) in best case (While removing last element).
Conclusion: LinkedList element deletion is faster compared to ArrayList.
Reason: LinkedList’s each element maintains two pointers (addresses) which points to the both neighbor elements in the list. Hence removal only requires change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.
3) Inserts Performance: LinkedList add method gives O(1) performance while ArrayList gives O(n) in worst case. Reason is same as explained for remove.
4) Memory Overhead: ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes hence the memory consumption is high in LinkedList comparatively.
There are few similarities between these classes which are as follows:

1. Both ArrayList and LinkedList are implementation of List interface.
2. They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List.
3. Both these classes are non-synchronized and can be made synchronized explicitly by using Collections.synchronizedList method.
4. The iterator and listIterator returned by these classes are fail-fast (if 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).

When to use LinkedList and when to use ArrayList?

1) As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)). Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice.
2) Search (get method) operations are fast in Arraylist (O(1)) but not in LinkedList (O(n)) so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

Got this information from : http://beginnersbook.com/2013/12/difference-between-arraylist-and-linkedlist-in-java/

Interface Vs Abstract Class

Abstract class Interface 1) Abstract class can have abstract and non-abstract methods. Interface can have only abstract methods. 2) Abstract class doesn't support multiple inheritance. Interface supports multiple inheritance. 3) Abstract class can have final, non-final, static and non-static variables. Interface has only static and final variables. 4) Abstract class can have static methods, main method and constructor. Interface can't have static methods, main method or constructor. 5) Abstract class can provide the implementation of interface. Interface can't provide the implementation of abstract class. 6) The abstract keyword is used to declare abstract class. The interface keyword is used to declare interface. 7) Example: public class Shape{ public abstract void draw(); } Example: public interface Drawable{ void draw(); }

Comparable Vs Comparator

Comparable :

 Comparable is implemented by a class in order to be able to comparing object of itself with some other objects. The class itself must implement the interface in order to be able to compare its instance(s). The method required for implementation is compareTo().

Comparator:

In some situations, you may not want to change a class and make it comparable. In such cases, Comparator can be used if you want to compare objects based on certain attributes/fields. For example, 2 persons can be compared based on `height` or `age` etc. (this can not be done using comparable.)
The method required to implement is compare(). Now let's use another way to compare those TV by size. One common use of Comparator is sorting. Both Collections and Arrays classes provide a sort method which use a Comparator.

In brief, a class that implements Comparable will be comparable, which means it instances can be compared with each other.
A class that implements Comparator will be used in mainly two situations: 1) It can be passed to a sort method, such as Collections.sort() or Arrays.sort(), to allow precise control over the sort order and 2) It can also be used to control the order of certain data structures, such as sorted sets (e.g. TreeSet) or sorted maps (e.g., TreeMap).

Example :

class Dog implements Comparator<Dog>, Comparable<Dog>{
   private String name;
   private int age;
   Dog(){
   }

   Dog(String n, int a){
      name = n;
      age = a;
   }

   public String getDogName(){
      return name;
   }

   public int getDogAge(){
      return age;
   }

   // Overriding the compareTo method
   public int compareTo(Dog d){
      return (this.name).compareTo(d.name);
   }

   // Overriding the compare method to sort the age 
   public int compare(Dog d, Dog d1){
      return d.age - d1.age;
   }
}

public class Example{

   public static void main(String args[]){
      // Takes a list o Dog objects
      List<Dog> list = new ArrayList<Dog>();

      list.add(new Dog("Shaggy",3));
      list.add(new Dog("Lacy",2));
      list.add(new Dog("Roger",10));
      list.add(new Dog("Tommy",4));
      list.add(new Dog("Tammy",1));
      Collections.sort(list);// Sorts the array list

      for(Dog a: list)//printing the sorted list of names
         System.out.print(a.getDogName() + ", ");

      // Sorts the array list using comparator
      Collections.sort(list, new Dog());
      System.out.println(" ");
      for(Dog a: list)//printing the sorted list of ages
         System.out.print(a.getDogName() +"  : "+
   a.getDogAge() + ", ");
   }
}

Parameter	Comparable	Comparator
Sorting logic	Sorting logic must be in same class whose objects are being sorted. Hence this is called natural ordering of objects	Sorting logic is in separate class. Hence we can write different sorting based on different attributes of objects to be sorted. E.g. Sorting using id,name etc.
Implementation	Class whose objects to be sorted must implement this interface.e.g Country class needs to implement comparable to collection of country object by id	Class whose objects to be sorted do not need to implement this interface.Some other class can implement this interface. E.g.-CountrySortByIdComparator class can implement Comparator interface to sort collection of country object by id
Sorting method	int compareTo(Object o1) This method compares this object with o1 object and returns  a integer.Its value has following meaning 1. positive – this object is greater than o1 2. zero – this object equals to o1 3. negative – this object is less than o1	int compare(Object o1,Object o2) This method compares o1 and o2 objects. and returns  a integer.Its value has following meaning. 1. positive – o1 is greater than o2 2. zero – o1 equals to o2 3. negative – o1 is less than o1
Calling method	Collections.sort(List) Here objects will be sorted on the basis of CompareTo method	Collections.sort(List, Comparator) Here objects will be sorted on the basis of Compare method in Comparator
Package	Java.lang.Comparable	Java.util.Comparator

 More info at : Click Here

 

Java Fail-Fast Vs Fail Safe

Here is a very good explanation on Fail-Fast Vs Fail Safe:  Click Here

Knapsack problem

Given n object with each with some weight and associated value. Find out the maximum value of knapsack if multiple objects with same weight are allowed.

Ex: Value = { 60,100,200}
      Weight = {10,20,30}


The idea is to start with the smallest weight and find out the total value of the knapsack for that and then continue with the next weight and consider the maximum value of either current object by adding the previous object value and the weight.



int _tmain(int argc, _TCHAR* argv[])
{
    int v[]={60,100,200};
    int w[]={15,20,30};

    int key = 50;

    int n;
   
    std::cout<<"Enter sum value :\n";
    std::cin>>n;
    int *sum;
    sum= new int[50];

    sum[0]=0; //base, coins to make a sum of zero.
    for(int i = w[0];i<=50;i++)
    {
        sum[i] = 0;
        for(int j=1;j<=3 ;j++)
        {
           
            if(w[j-1]<=i)
            {
                // Consider the case when you add two units and the value is more than the current unit   weight.
                sum[i] = v[j-1] + sum[i-w[j-1]] > v[j] ? v[j-1] + sum[i-w[j-1]] : v[j];
               
            }
        }
    }
    std::cout<<" Total value of kanpsack of weight "<< n << " is :"<<sum[n-1]<<std::endl;
}