Category Archives: Generics and Collections

Misc Questions in Collections

Posted on by

1.Why we are unable to add primitives as generic type
Allowed

 List<Integer> arrAges = new ArrayList<Integer>();

Not allowed

 List<int> arrAges = new ArrayList<int>();

This is to maintain backwards compatibility with previous JVM runtimes in the sense it could be referred by parent class instance Object. Generics in Java are encountered at compile time The compiler converts from generic type to right type as shown in the example below

List<ClassA> list = new ArrayList<ClassA>();
list.add(new ClassA());
ClassA a = list.get(0);

will be turned in to

List list = new ArrayList();
list.Add(new ClassA());
ClassA a = (ClassA)list.get(0);

So anything that is used as generics has to be convert able to Object (in this example get(0) returns an Object), and the primitive types aren’t. So they can’t be used in generics.

2.How to have a Ordered Collections

  1. keep the insertion order: LinkedHashSet and CopyOnWriteArraySet (thread-safe)
  2. keep the items sorted within the set: TreeSet, EnumSet (specific to enums) and ConcurrentSkipListSet (thread-safe)

Everything about Tree

Posted on by

Similarities between TreeMap and TreeSet in Java

  1. Both TreeMap and TreeSet are sorted data structure, which means they keep there element in predefined Sorted order. Sorting order can be natural sorting order defined by Comparable interface or custom sorting Order defined by Comparator interface. Both TreeMap and TreeSet has overloaded constructor which accept a Comparator, if provided all elements inside TreeSet or TreeMap will be compared and Sorted using this Comparator.
  2. Both TreeSet and TreeMap implements base interfaces e.g. TreeSet implements Collection and Set interface so that they can be passed to method where a Collection is expected and TreeMap implements java.util.Map interface, which means you can pass it when a Map is expected
  3. TreeSet is practically implemented using TreeMap instance, similar to HashSet which is internally backed by HashMap instance.
  4. Both TreeMap and TreeSet are non synchronized Collection, hence can not be shared between multiple threads. You can make both TreeSet and TreeMap synchronized by wrapping them into Synchronized collection by calling Collections.synchroinzedMap() method.
  5. Iterator returned by TreeMap and TreeSet are fail-fast, means they will throw ConcurrentModificationException when TreeMap or TreeSet is modified structurally once Iterator is created.
  6. Both TreeMap and TreeSet are slower than there Hash counter part like HashSet and HashMap and instead of providing constant time performance for add, remove and get operation they provide performance in O(log(n)) order.

TreeSet vs TreeMap

  1. Major difference between TreeSet and TreeMap is that TreeSet implements Set interface while TreeMap implements Map interface in Java.
  2. TreeMap and TreeSet is the way they store objects. TreeSet stores only one object while TreeMap uses two objects called key and Value. Objects in TreeSet are sorted while keys in TreeMap remain in sorted Order.
  3. former implements NavigableSet while later implements NavigableMap in Java.
  4. duplicate objects are not allowed in TreeSet but duplicates values are allowed in TreeMap.

Everything about HashMap

Posted on by

1.How to get elements from HashMap

public static void printMap(Map mp) 
{
    Iterator it = mp.entrySet().iterator();

    while (it.hasNext()) 
    {
        Map.Entry pairs = (Map.Entry)it.next();
        System.out.println(pairs.getKey() + " = " + pairs.getValue());

        //Avoids a ConcurrentModificationException
        it.remove(); 
    }
}

2.Adding keys to HashMap Finding Next Key
To find the next key while using HashMap with Integer as Key the following function can be used.

  1. Iterate through List of Keys
  2. Sort the Keys
  3. Find the Highest value by looking into Key at size-1
  4. The next key to be used is received by adding 1 to Key(lastMaxElem) at size-1 
private Integer getNextKey()
{
    List<Integer> keyList = new ArrayList<Integer>();
    int lastMaxElem = 0;
		
    HashMap WaterfallHM = (HashMap) getFromWorkFlowScope("WaterfallHM");		
    Set<Integer> keys = WaterfallHM.keySet();
        
    for ( Integer key : keys) {
	keyList.add(key);
    }
		
    Collections.sort(keyList); // Sort the arraylist
    lastMaxElem = keyList.get(keyList.size() - 1);
    lastMaxElem++; 
		
    return new Integer(lastMaxElem);
}

3.How to Initialize a Constants in HashMap

public class Test 
{
    private static final Map<Integer, String> MY_MAP = createMap();

    private static Map<Integer, String> createMap() {
        Map<Integer, String> result = new HashMap<Integer, String>();
        result.put(1, "one");
        result.put(2, "two");
        return Collections.unmodifiableMap(result);
    }
}

4.Why Map Interface doesnot extend Collections Framework
Collection assume elements of one value. Map assumes entries of key/value pairs. They could have been engineered to re-use the same common interface however some methods they implement are incompatible e.g.

Collection.remove(Object) - removes an element.
Map.remove(Object) - removes by key, not by entry.

There are some methods in common; size(), isEmpty(), clear(), putAll/addAll()

Collection interface is largely incompatible with the Map interface. If Map extended Collection, what would the add(Object) method do

5.Why need ConcurrentHashMap and CopyOnWriteArrayList
he synchronized collections classes, Hashtable, and Vector, and the synchronized wrapper classes, Collections.synchronizedMap() and Collections.synchronizedList(), provide a basic conditionally thread-safe implementation of Map and List. However, several factors make them unsuitable for use in highly concurrent applications, for example, their single collection-wide lock is an impediment to scalability and it often becomes necessary to lock a collection for a considerable time during iteration to prevent ConcurrentModificationException.ConcurrentHashMap(uses Segments) and CopyOnWriteArrayList implementations provide much higher concurrency while preserving thread safety, with some minor compromises in their promises to callers.

LinkedList

Posted on by

Why LinkedList is Faster than ArrayList?
Adding Element in middle of ArrayList requires reshuffling of other elements.Whereas in Linked list only two nodes(Nodes between which the element is added) needs to be changed.

Types of LinkedList?

  1. singly linked list
  2. doubly-linked list
  3. Circular linked list

singly linked list doubly-linked list
Pros:Simple in implementation, requires relatively lesser memory for storage, assuming you need to delete/insert (at) next node – deletion/insertion is faster. Can be iterated in forward as well as reverse direction. In case of needing to delete previous node, there is no need to traverse from head node, as the node to be deleted can be found from ‘.previous’ pointer.
Cons:Cannot be iterated in reverse, need to maintain a handle to the head node of the list else, the list will be lost in memory. If you’re deleting previous node or inserting at previous node, you will need to traverse list from head to previous node to be able to carry out those operations – O(N) time Relatively complex to implement, requires more memory for storage (1 ‘.previous’ pointer per node). Insertions and deletions are relatively more time consuming (assigning/reassigning ‘.previous’ pointer for neighbor nodes)

Time complexity of a linked list

Operation Metrics
Indexing O(n)
Inserting / Deleting at end O(1) or O(n)
Inserting / Deleting in middle O(1) with iterator O(n) with out

The time complexity for the Inserting at the end depends if you have the location of the last node, if you do, it would be O(1) other wise you will have to search through the linked list and the time complexity would jump to O(n).

How arrayList works Internally

Posted on by
  1. Internally an ArrayList uses an Object[] Array. 
           private transient Object[] elementData;
  2. As you add items to an ArrayList, the list checks to see if the backing array has room left. If there is room, the new item is just added at the next empty space. If there is not room, a new, larger, array is created, and the old array is copied into the new one.
  3. When we actually create an arrayList following piece of code is executed – 
      this.elementData=new Object[initial capacity];
  4. ArrayList can be created in two ways-

    List<String> myList=new ArrayList<String>();
  5. When we create an ArrayList in this way, default constructor is invoked and will internally create an array of Object with default size, which is 10.

    List<String> myList=new ArrayList<String>(5);

    When we create an ArrayList in this way, constructor with an integer argument is invoked and will internally create an array of Object with the size, specified in the constructor argument, which happens to be 5 in this case.

  6. Inside add() method Check is made, before adding element into the array it will check what is the current size of filled elements and what is the maximum size of the array. If size of filled elements is greater than maximum size of the array then size of the array must be increased. But we know that the size of the array cannot be increased dynamically.

    So what happens internally is a new Array is created with size 1.5*currentSize and the data from old Array is copied into this new Array.

Internally an ArrayList uses an Object[].

Capacity vs Size

The capacity is how many elements the list can potentially accommodate without reallocating its internal structures.

The size is the number of elements in the list

If you allocate a new array with arr = new Employee[100], the size of that array (arr.length) is going to be 100. It has 100 elements. All the elements are initially null (as this is an array of object references), but still, there are 100 elements.

If you do something like list = new ArrayList (100), and try to check list.size(), you’ll get 0. There are no elements in the list.

Internally, it’s true that the ArrayList allocates enough place to put 100 items before it needs to extend its capacity, but that’s an internal implementation detail, and the list presents its content to you as “no items stored”. Only if you actually do list.add(something), you’ll have items in the list.

So although the list allocates storage in advance, the API with which it communicates with the program tells you there are no items in it. The null items in its internal array are not available to you – you cannot retrieve them or change them.

An ArrayList is just one way to represent an abstract list, and the capacity of an ArrayList is an implementation detail of how the system implements the logical list.

An ArrayList stores the elements of a list by using an actual array “under the covers.” The actual realization of the array in computer memory has a certain size when it is allocated; this size is the ArrayList’s capacity. The ArrayList emulates a variable-sized list by storing the logical length of the list in addition to the fixed-length array. Thus if you have an ArrayList with a capacity 10 which contains 4 logical elements, the ArrayList can be represented as a length and an array

(4) | e1 | e2 | e3 | e4 | __ | __ | __| __ | __ | __ |

where the (4) is the logical length of the list and ‘__’ represent data that is ignored because it is not part of the logical list. If you attempt to access the 5th element of this ArrayList, it will throw an exception because it knows that the fifth element has not been initialized. If we then append an extra element e5 to the list, the ArrayList becomes

(5) | e1 | e2 | e3 | e4 | e5 | __ | __ | __ | __ | __ |

Note that the capacity has not changed, while the logical length has, because the underlying array is still able to handle all the data in the logical list.

If you manage to add more than ten elements to this list, the ArrayList will not break. The ArrayList is an abstraction meant to be compatible with all array operations. Rather, the ArrayList changes its capacity when its logical length exceeds its original capacity. If we were to add the elements (a1, a2, …, a7) to the above list, the resulting ArrayList might look like

(12) | e1 | e2 | e3 | e4 | e5 | a1 | a2 | a3 | a4 | a5 | a6 | a7 | __ | __ | __ | __ | __ | __ | __ | __ |

with a capacity of 20.

Once you have created an ArrayList, you can ignore the capacity in all programming that follows; the logic is unaffected. However, the performance of the system under certain kinds of operations can be affected. Increasing the capacity, for instance, might well involved allocating a larger array, copying the first array into the second and then performing the operations. This can be quite slow compared to, e.g. the same operation on a linked list. Thus it is sensible to choose the capacity of an ArrayList to be bigger than, or at least comparable to, the actual number of elements expected in the real runtime environment.

Is there a Way to Create ArrayList of Fixed size in Java

 List<String> fixedSizeList = Arrays.asList(new String[100]);

You cannot insert new Strings to the fixedSizeList (it already has 100 elements). You can only set its values like this:

fixedSizeList.set(7, "new value");

What would be the Output of the Following Code

List<Employee> employees = new ArrayList<>(100);
int size = employes.size();

size will be 0 while the initial capacity is 100.

Difference between modcount and size ArrayList

Posted on by

modcount of the list lets you know if there has been a structural modification made that might cause the current operation to give incorrect results.

  List<String> arrNames = new ArrayList<String>();
  arrNames.add("Mugil");
  arrNames.add("Vinu");
  arrNames.add("Bala");
  arrNames.add("Madhu");		
  arrNames.remove(0);		
  arrNames.add("Swathi");		
  arrNames.remove(1);

When the control reaches
Line 6 The Size and Modcount of the arrNames would be 4
Line 7 The Size and Modcount would be 5 and size would be 3
Line 7 The Size and Modcount would be 6 and size would be 4

Fine the Screenshots below for further Details

Set

Posted on by | Leave a reply

Set

  • Set prevents duplication.The common use of set is to check for duplication
  • Since its is helpful for lookups for duplicate value HashSet provides an optimized implementation
  • If you want the result to be sorted use TreeSet instead of HashSet
Posted in Set.

ArrayList vs LinkedList

Posted on by | Leave a reply

Why ArrayList Faster than LinkedList during Random Access?
ArrayList has direct references to every element in the list, so it can get the n-th element in constant time. LinkedList has to traverse the list from the beginning to get to the n-th element.

Why LinkedList faster than ArrayList during Insertion/Deletion?
ArrayList is slower because it needs to copy part of the array in order to remove the slot that has become free. If the deletion is done using the ListIterator.remove() API, LinkedList just has to manipulate a couple of references; if the deletion is done by value or by index, LinkedList has to potentially scan the entire list first to find the element(s) to be deleted.

  • LinkedList takes constant-time insertions or removals. I can walk the list forwards or backwards, but grabbing an element in the middle takes time proportional to the size of the list.
  • ArrayLists allows random access, so I can grab any element in constant time. But adding or removing from anywhere but the end requires shifting all the latter elements over, either to make an opening or fill the gap. Also, if I add more elements than the capacity of the underlying array, a new array (twice the size) is allocated, and the old array is copied to the new one, so adding to an ArrayList is O(n) in the worst case but constant on average.
  • Iterating over both the Types is equally cheap.
  • If you have large lists, the memory usage is different. Each element of a LinkedList has more overhead since pointers to the next and previous elements are also stored

When should I use LinkedList?

  • When you need efficient removal in between elements or at the start.
  • When you don’t need random access to elements, but can live with iterating over them one by one

When should I use ArrayList?

  • When you need random access to elements (“get the nth. element”)
  • When you don’t need to remove elements from between others. It’s possible but it’s slower since the internal backing-up array needs to be reallocated.
  • Adding elements is amortized constant time (meaning every once in a while, you pay some performance, but overall adding is instantly done)
Operation Linked List Array List
Access O(n) O(1)
Insertion Access time + O(1) Access time + O(n)
Deletion Access time + O(1) Access time + O(n)

Iterator vs ListIterator

Posted on by | Leave a reply

When you are simple moving through List but you are not modifying the List object foreach is more efficient.In case you want to perform operations on each element of list individually taking out the element in such case use Iterator.

List<Fruits> arrFruits = new ArrayList<Fruits>();
Iterator<Fruits> itFrt = arrFruits.iterator();

while(itFrt.hasNext())
{
 Fruits frt = itFrt.next();
 System.out.println(frt);
}

ListIterator

  • While using Iterator in particular to List using a ListIterator is more powerful over Iterator.
  • ListIterator is bidirectional
  • It also keep track of Indexes of next and previous elements
  • It can replace last element it visited using set method
 List<fruits> arrFruits     = fruits.arrayList(5);
 ListIterator<fruits> itFrt = arrFruits.listIterator();

 while(itFrt.hasNext())
 {
   System.out.println(it.next()); 
   System.out.println(it.nextIndex()); 
   System.out.println(it.previousIndex()); 
 }

List Notes

Posted on by | Leave a reply
  • List maintains elements in Particular Sequence.
  • Two types of List 1.ArrayList and 2.LinkedList
  • ArrayList is faster while accessing elements but slower while Insertion and Deletion
  • LinkedList is slow in random access but faster during insertion and deletion

Operations in ArrayList

class Fruits
{	
  String Name = "Fruit";
}

class Apple extends Fruits
{	
 public Apple()
 {
   Name = "Apple";
 }
}

class Orange extends Fruits
{	
 public Orange()
 {
  Name = "Orange";
 }
}

class Mango extends Fruits
{	
 public Mango()
 {
  Name = "Mango";
 }
}

Adding Element – List.add()

List<Fruits> arrFruits = new ArrayList<Fruits>();
Fruits objApple  = new Apple();
Fruits objMango  = new Mango();
arrFruits.add(objApple);
arrFruits.add(objMango);

Removing Element – List.remove()

arrFruits.remove(objApple);

Removing by Index – List.remove()

arrFruits.remove(1);

Index of Element – List.indexOf()

arrFruits.indexOf(objMango);

Index of Element – List.indexOf()

arrFruits.indexOf(objMango);

SubList – List.subList(StartPOS, EndPOS)

List<Fruits> arrNewFruits = arrFruits.subList(0,2);

containsAll – NewList.containsAll(OrgList)

 arrNewFruits.containsAll(arrFruits);

set Value at Index

 arrNewFruits.set(1, new Orange());

removeAll

 arrFruits.removeAll(arrFruits);

addAll

 arrFruits.addAll(arrNewFruits);

retainAll – set Intersection Operation
retainAll performs set Interscetion Operation by taking Two ArrayList. It Retains Boolean true if intersection finds element false otherwise. 

List<Integer> arrNums1 = new ArrayList<Integer>();
arrNums1.add(1);
arrNums1.add(2);
arrNums1.add(3);
		
List<Integer> arrNums2 = new ArrayList<Integer>();
arrNums2.add(1);

System.out.println(arrNums1.retainAll(arrNums2));
System.out.println(arrNums1);