collection in java

What is hierarchy of ArrayList in java?

-java.lang.Object

-java.util.AbstractCollection

 -java.util.AbstractList

  -java.util.ArrayList

java.util.ArrayList

java.util.ArrayList is Resizable-array implementation of the java.util.List interface. As ArrayList uses array it is index based structure in java.

java.util.ArrayList implements RandomAccess(Marker interface) to indicate that they support fast random access (i.e. index based access) in java.

java.util.ArrayList extends AbstractList (abstract class) which provides implementation to  List interface to minimize the effort required to implement this interface backed by RandomAccess interface in java.

public void add(E value)	Add objects in ArrayListCustom
public E get(int index)	Method returns element on specific index.
public Object remove(int index)	Method returns removedElement on specific index, else it throws IndexOutOfBoundException if index is negative or greater than size of size.
public void display()	-Method displays all objects in ArrayListCustom. -Insertion order is guaranteed.
private void ensureCapacity()	Method increases capacity of list by making it double.

Custom ArrayList in java::

class ArrayListCustom<E> {

  

 private static final int INITIAL_CAPACITY = 10;

 private Object elementData[]={};

 private int size = 0;

 /**

 * constructor.

 */

 public ArrayListCustom() {

   elementData = new Object[INITIAL_CAPACITY];

 }

 /**

  * method adds elements in ArrayListCustom.

  */

 public void add(E e) {

   if (size == elementData.length) {

     ensureCapacity(); //increase current capacity of list, make it double.

   }

   elementData[size++] = e;

 }

 /**

  * method returns element on specific index.

  */

 @SuppressWarnings("unchecked")

 public E get(int index) {

   if ( index <0 || index>= size) {  //if index is negative or greater than size of size, we throw Exception.

     throw new IndexOutOfBoundsException("Index: " + index + ", Size " + index);

   }

   return (E) elementData[index]; //return value on index.

 }

 /**

  * method returns removedElement on specific index.

  * else it throws IndexOutOfBoundException if index is negative or greater than size of size.

  */

 public Object remove(int index) {

   if ( index <0 || index>= size) {  //if index is negative or greater than size of size, we throw Exception.

     throw new IndexOutOfBoundsException("Index: " + index + ", Size " + index);

   }

  

   Object removedElement=elementData[index];

   for(int i=index;i<size;i++){

      elementData[i]=elementData[i+1];

   }

   size--;   //reduce size of ArrayListCustom after removal of element.

  

   return removedElement;

 }

 /**

  * method increases capacity of list by making it double.

  */

 private void ensureCapacity() {

   int newIncreasedCapacity = elementData.length * 2;

   elementData = Arrays.copyOf(elementData, newIncreasedCapacity);

 }

 /**

  * method displays all the elements in list.

  */

 public void display() {

     System.out.print("Displaying list : ");

     for(int i=0;i<size;i++){

            System.out.print(elementData[i]+" ");

     }

 }

}

/**

* Main class to test ArrayListCustom functionality.

*/

public class ArrayListCustomApp {

    

     public static void main(String...a) {

          ArrayListCustom<Integer> list = new ArrayListCustom<Integer>();

    list.add(1);

    list.add(2);

    list.add(3);

    list.add(4);

    list.add(1);

    list.add(2);

   

    list.display();

    System.out.println("\nelement at index "+1+" = "+list.get(1));

    System.out.println("element removed from index "+1+" = "+list.remove(1));

   

    System.out.println("\nlet's display list again after removal at index 1");

   

    list.display();

   

    //list.remove(11);  //will throw IndexOutOfBoundsException, because there is no element to remove on index 11.

    //list.get(11);   //will throw IndexOutOfBoundsException, because there is no element to get on index 11.

   

     }

    

}

/*Output

Displaying list : 1 2 3 4 1 2

element at index 1 = 2

element removed from index 1 = 2

let's display list again after removal at index 1

Displaying list : 1 3 4 1 2

*/

Complexity of methods

Operation/ method	Worst case	Best case
add	O(n), when array is full it needs restructuring, operation runs in amortized constant time.	O(1), when array does not need any restructuring.
remove	O(n), when removal is done from between restructuring is needed.	O(1), when removal is done at last position, no restructuring is needed.
get	O(1), it is index based structure. So, complexity of  get operation is always done in O(1).	O(1) it is index based structure. So, complexity of  get operation is always done in O(1).
display	O(n), because iteration is done over each and every element.	O(n), because iteration is done over each and every element.

iterator() method returns iterator to iterate over elements in ArrayList in java.

 Iterator important methods :

hasNext() method returns true if the iteration has more elements. (Traversing/Iteration is  done in forward direction).

next() method - returns next element in iteration.

if the iteration has no more elements than NoSuchElementException is thrown.

remove() method - removes last element returned by iterator.

making list unmodifiable using Collections.unmodifiableList

public class ArrayListTest {

   public static void main(String args[]) {

          // creates array with initial capacity of 10.

          List<String> arrayList = new ArrayList<String>();

          arrayList.add("ankit");

          arrayList.add("javaMadeSoEasy");

          // getting unmodifiable list

          List<String> unmodifiableList = Collections.unmodifiableList(arrayList);

         

          /*

           * Now any attempt to modify list will throw java.lang.UnsupportedOperationException

           */

          unmodifiableList.add("mittal");

   }

}

/*OUTPUT

Exception in thread "main" java.lang.UnsupportedOperationException

   at java.util.Collections$UnmodifiableCollection.add(Unknown Source)

   at arrayListUnModifiable.ArrayListTest.main(ArrayListTest.java:24)

*/

HashSet

java.util.HashSet is implementation of the java.util.Set interface.

java.util.HashSet enables us to store element, it does not allow us to store duplicate elements in java. 

Features of java.util.HashSet

1.            HashSet  is implementation of the java.util.Set interface in java.

2.            HashSet is internally implemented using java.util.HashMap in java.

3.            Duplicate elements - HashSet does not allows to store duplicate elements in java.

4.            Null elements - One null element can be added in HashSet in java.

5.            Insertion order - HashSet  does not maintains insertion order in java.

Let’s say we add 3 elements in hashSet

hashSet.add("ind");    

hashSet.add("aus");    

hashSet.add("sa");

On displaying insertion order will not be maintained i.e.

sa

aus

ind

6.            synchronized - HashSet is not synchronized (because 2 threads on same HashSet object can access it at same time) in java.

7.            Performance - HashSet is not synchronized, hence its operations are faster as compared to some other synchronized implementation of Set interface in java.

When to use java.util.HashSet >

1.            HashSet can be used when we don’t want to store duplicate elements in java.

2.            HashSet can be used when we want to store only one null in java.

3.            We must prefer HashSet for when add and remove operations are more as compared to get operations in java, and

4.            HashSet can be used when we are not working in multithreading environment in java. 

What is Load Factor in java ?

Default load factor is 0.75

That means when set will be 75% filled,  it’s capacity will be doubled.

Example in java >

Initially when number of elements is 0,  default capacity =16, Load Factor =0.75, HashSet is 0% full.

number of elements	capacity of HashMap	Load factor	HashSet filled in %age
0	16	0.75	0%
4	16	0.75	25%
8	16	0.75	50%
11	16	0.75	68.7%

When next element will be added (i.e. 12th element), hashSet will be 75% filled and capacity will be doubled i.e. from 16 to 32.

12

32

0.75

37.5%

java.util.HashMap in java

java.util.HashMap is implementation of the java.util.Map interface.

java.util.HashMap enables us to store data in key-value pair form. Insertion order of key-value pairs is not maintained.

In an HashMap, two keys k1 and k2 are equal if and only if (k1==null ? k2==null : k1.equals(k2))

Understanding (k1==null ? k2==null : k1.equals(k2)) >

If k1 is null, check k2==null, if k2 is also null then k1 and k2 are equal else they are not equal.

If k1 is not null, check  k1.equals(k2), if equals return true than k1 and k2 are equal else they are not equal.

-java.lang.Object

-java.util.AbstractMap

 -java.util.concurrent.HashMap

1.            HashMap enables us to store data in key-value pair form in java.

2.            HashMap is implementation of the java.util.map interface in java.

3.            Duplicate key- HashMap does not allows to store duplicate keys. If the map already contains a mapping for the key, the old value is replaced in java.

4.            Null elements - One null key can be added in HashMap. And null values are also allowed in HashMap in java.

Insertion order - HashMap does not maintains insertion order in 

Let’s say we add 3 elements in hashMap

hashMap.put(1,"ind");    

hashMap.put(2,"aus");    

hashMap.put(3,"sa");

On displaying insertion order will not be maintained i.e.

3,sa

2,aus

1,ind

6.            synchronized - HashMap is not synchronized (because 2 threads on same HashMap object can access it at same time) in java.

7.            Performance - HashMap is not synchronized, hence its operations are faster as compared to some other synchronized implementation of map interface in java.

What are differences between ArrayList and LinkedList in java?

	Property	java.util.ArrayList	java.util.LinkedList
1	Structure	java.util.ArrayList is index based structure in java.	A java.util.LinkedList is a data structure consisting of a group of nodes which together represent a sequence. node is composed of a data and a reference (in other words, a link) to the next node in the sequence in java.
2	Resizable	ArrayList is Resizable-array in java.	New node is created for storing new element in LinkedList in java.
3	Initial capacity	java.util.ArrayList is created with initial capacity of 10 in java.	For storing every element node is created in LinkedList, so linkedList’s initial capacity is 0 in java.
4	Ensuring Capacity/ resizing.	ArrayList is created with initial capacity of 10. ArrayList’s size is increased by 50% i.e. after resizing it’s size become 15 in java.	For storing every element node is created, so linkedList’s initial capacity is 0, it’s size grow with addition of each and every element in java.
5	RandomAccess interface	ArrayList implements RandomAccess(Marker interface) to indicate that they support fast random access (i.e. index based access) in java.	LinkedList does not implement RandomAccess interface in java.
6	AbstractList and AbstractSequentialList	ArrayList extends AbstractList (abstract class) which provides implementation to  List interface to minimize the effort required to implement this interface backed by RandomAccess interface.	LinkedList extends AbstractSequentialList (abstract class), AbstractSequentialList extends AbstractList. In LinkedList, data is accessed sequentially, so for obtaining data at specific index, iteration is done on nodes sequentially in java.
7	How get(index) method works? (Though difference has been discussed briefly in above 2 points but in this in point we will figure difference in detail.)	Get method of ArrayList directly gets element on specified index. Hence, offering O(1) complexity in java.	Get method of LinkedList iterates on nodes sequentially to get element on specified index. Hence, offering O(n) complexity in java.
8	When to use	Use ArrayList when get operations is more frequent than add and remove operations in java.	Use LinkedList when add and remove operations are more frequent than get operations in java.

What are differences between List and Set interface in java?

	Property	java.util.List	java.util.Set
1	Insertion order	java.util.List is ordered collection it maintain insertion order in java.	Most of the java.util.Set implementation does not maintain insertion order. HashSet does not maintains insertion order in java. Thought LinkedHashSet maintains insertion order in java. TreeSet is sorted by natural order in java.
2	Duplicate elements	List allows to store duplicate elements in java.	Set does not allow to store duplicate elements in java.
3	Null keys	List allows to store many null keys in java.	Most of the Set implementations allow to add only one null in java. TreeSet does not allow to add null in java.
4	Getting element on specific index	List implementations provide get method to get element on specific index in java. ArrayList, Vector, copyOnWriteArrayList and LinkedList provides - get(int index) Method returns element on specified index. Get method directly gets element on specified index. Hence, offering O(1) complexity.	Set implementations does not provide any such get method to get element on specified index in java.
5	Implementing classes	ArrayList, LinkedList, Vector, CopyOnWriteArrayList classes implements List interface in java.	HashSet, CopyOnWriteArraySet, LinkedHashSet, TreeSet, ConcurrentSkipListSet, EnumSet classes implements Set interface in java.
6	listIterator	listIterator method returns listIterator to iterate over elements in List in java. listIterator provides additional methods as compared to iterator like hasPrevious(), previous(), nextIndex(), previousIndex(), add(E element), set(E element)	Set does not provide anything like listIterator. It simply return Iterator in java.
7	Structure and resizable	List are Resizable-array implementation of the java.util.List interface in java.	Set uses Map for their implementation. Hence, structure is map based and resizing depends on Map implementation. Example > HashSet internally uses HashMap.
8	Index based structure /RandomAccess	As ArrayList uses array for implementation it is index based structure, hence provides random access to elements. But LinkedList is not indexed based structure in java.	Set is not index based structure at all in java.

What are differences between Iterator and ListIterator? in java

	java.util.ListIterator	java.util.Iterator
1	hasPrevious()  method returns true if this listIterator has more elements when traversing the list in the reverse direction.	No such method in java.util.Iterator.
2	previous()  returns previous element in iteration (traversing in backward direction). if the iteration has no previous elements than NoSuchElementException is thrown.	No such method in java.util.Iterator.
3	nextIndex()  method returns the index of the element that would be returned by a subsequent call to next() method. If listIterator is at the end of the list than method returns size of list.	No such method in java.util.Iterator.
4	previousIndex()  method returns the index of the element that would be returned by a subsequent call to previous() method. If listIterator is at the start of the list than method returns -1.	No such method in java.util.Iterator.
5	add(E element) Method inserts the specified element into the list. The element is inserted immediately before the element that would be returned by next (So, subsequent call to next would be unaffected), if any, and after the element that would be returned by previous (So,subsequent call to previous would return the new element), if any. If the list does not contain any element than new element will be the sole element in the list.	No such method in java.util.Iterator.
6	set(E element) Method replaces the last element returned by next() or previous() method with the specified element. This call can be made only if neither remove nor add have been called after the last call to next or previous. If call to set() method is followed up by any call made to remove() or add() method after next() or previous() than UnsupportedOperationException is thrown.	No such method in java.util.Iterator.

How do we override equals and hashcode method in java, write a code to use Employee as key in HashMap in java?

import java.util.HashMap;

class Employee {

  

   private Integer id;

   private String name;

  

   public Employee(Integer id, String name) { // constructor

          this.id = id;

          this.name = name;

   }

   @Override

   public String toString() {

          return "Employee[id=" + id + ", name=" + name + "] ";

   }

   @Override

   public boolean equals(Object obj){

         

          if(obj==null) //If obj is null, return without comparing obj & Employee class.

                 return false;

         

          if(this.getClass()!=obj.getClass())   //identifies whether obj is instance of Employee class or not.

                 return false;

  

          Employee emp=(Employee)obj; //type cast obj into employee instance.

          return (emp.id==this.id || emp.id.equals(this.id))

                              && (emp.name==this.name || emp.name.equals(this.name));       

   }

         

   @Override

   public int hashCode(){

          int hash=(this.id==null ? 0: this.id.hashCode() ) +

                       (this.name==null ? 0: this.name.hashCode() );

          return hash;     

   }

}

/** Copyright (c), AnkitMittal JavaMadeSoEasy.com */

public class EmployeeOverride {

   public static void main(String...a){

         

          HashMap<Employee, String> hm=new HashMap<Employee, String>();

          hm.put(new Employee(1,"sam"), "employee1 data");

          hm.put(new Employee(2,"amy"), "employee2 data");

         

          System.out.println("HashMap's data> "+hm);

          System.out.println(hm.get(new Employee(1,"sam")));

         

          hm.put(new Employee(1,"sam"), "employee1 data OVERRIDDEN");

          System.out.println("\nAgain display HashMap after overriding data "+

                       "of Employee with id=1 and name=’sam’\n");

         

          System.out.println("HashMap's data> "+hm);

          System.out.println(hm.get(new Employee(1,"sam")));

         

   }

}

/*OUTPUT

HashMap's data> {Employee[id=1, name=sam] =employee1 data, Employee[id=2, name=amy] =employee2 data}

employee1 data

Again display HashMap after overriding data of Employee with id=1 and name=’sam’

HashMap's data> {Employee[id=1, name=sam] =employee1 data OVERRIDDEN, Employee[id=2, name=amy] =employee2 data}

employee1 data OVERRIDDEN

*/     

What classes should i prefer to use a key in HashMap in java? 

Answer. This collection framework interview question will check your in depth knowledge of Java’s Collection Api’s. we should prefer String, Integer, Long, Double, Float, Short and any other wrapper class. Reason behind using them as a key is that they override equals() and hashCode() method, we need not to write any explicit code for overriding equals() and hashCode() method in java.

What are differences between HashMap and Hashtable in java?

	Property	java.util.HashMap	java.util.Hashtable
1	synchronization	java.util.HashMap is not synchronized  (because 2 threads on same HashMap object can access it at same time) in java.	java.util.Hashtable is synchronized (because 2 threads on same Hashtable object cannot access it at same time) in java.
2	Performance	HashMap is not synchronized, hence its operations are faster as compared to Hashtable in java.	Hashtable is synchronized, hence its operations are slower as compared to HashMap in java. If we are working not working in multithreading environment jdk recommends us to use HashMap.
3	Null keys and values	HashMap allows to store one null key and many null values i.e. many keys can have null value in java.	Hashtable does not allow to store null key or null value. Any attempt to store null key or value throws runtimeException (NullPointerException) in java.
4	Introduced  in which java version	HashMap was introduced in second version of java i.e. JDK 2.0	Hashtable was introduced in first version of java i.e. JDK 1.0 But it was refactored in java 2 i.e. JDK 1.2 to implement the Map interface, hence making it a member of member of the Java Collections Framework.
5	Recommendation	In non-multithreading environment it is recommended to use HashMap than using Hashtable in java.	In java 5 i.e. JDK 1.5, it is recommended to use ConcurrentHashMap than using Hashtable.
6	Extends Dictionary (Abstract class, which is obsolete)	HashMap does not extends Dictionary in java.	Hashtable extends Dictionary (which maps non-null keys to values. In a given Dictionary we can look up value corresponding to key) in java.

Differences between java.util.HashSet vs java.util.LinkedHashSet vs java.util.TreeSet in java

	Property	java.util.HashSet	java.util.LinkedHashSet	java.util.TreeSet
1	Insertion order	java.util.HashSet does not maintains insertion order in java. Example in java > set.add("b"); set.add("c"); set.add("a"); Output >      No specific order	java.util.LinkedHashSet maintains insertion order in java. Example in java > set.add("b"); set.add("c"); set.add("a"); Output >      b c a	java.util.TreeSet is sorted by natural order in java. Example in java > set.add("b"); set.add("c"); set.add("a"); Output >      a b c
2	Null elements	HashSet allows to store one null in java.	LinkedHashSet allows to store one null in java.	TreeSet does not allows to store any null in java. Any attempt to add null throws runtimeException (NullPointerException).
3	Data structure internally used for storing data	For storing elements HashSet internally uses HashMap.	For storing elements LinkedHashSet internally uses  LinkedHashMap.	For storing elements TreeSet internally uses TreeMap.
4	Introduced  in which java version	java.util.HashSet was introduced in second version of java (1.2) i.e. JDK 2.0	java.util.LinkedHashSet was introduced in second version of java (1.4) i.e. JDK 4.0	java.util.TreeSet was introduced in second version of java (1.2) i.e. JDK 2.0
5	Implements which interface	HashSet implements java.util.Set interface.	LinkedHashSet implements java.util.Set interface.	TreeSet implements java.util.Set java.util.SortedSet java.util.NavigableSet interface.

Differences between java.util.Hash Map  and ConcurrentHashMap in java