Java Collections – List – An Depth Analysis

Java Collections – List – An Depth Analysis

What is a List?

It is an ordered collection, which stores elements in a order. List can have duplicate elements.

Types of Lists:

  • LinkedList
  • ArrayList
  • Vector
  • CopyOnWriteArrayList

LinkedList:

It is a linear data structure where each element point to the next element.

What is the internal Implementation of List?
Internal implementation of LinkedList is – Doubly LinkedList.

So what is the difference between Single LinkedList and Doubly LinkedList?

Single Linked List:

In a single linked list, all the elements when inserted will point to the next node of the element and the last element will point to the first element. So whats is the draw back of this, we cant do reversal process, only one way access is possible. Example if we are at element 3, we cant go back to element 2. we need to pass to element 4, then element 1 and then to element 2.

 

Doubly Linked List:

In double linked list, all the nodes are interconnected and can do reversal operations. The last node is connected to first node and same way first one is connected to the last node.

Advantages of Doubly Linked List Over Single Linked List:

  • We can traverse in both the directions
  • We can easily insert a new node before the given node.

Disadvantages of Doubly Linked List over Single Linked List:

  • Extra space required for previous pointer (since it is interconnected one for previous and one for next required)
  • Insertion and deletion requires extra operation as previous pointer and next pointer has to be changed.

Advantages of LinkedList:

Linkedlist does not have initial capacity, the list grows as the elements are added to the list. Insertion and deletion are faster in linkedlist as it uses doubly linkedlist.

Why is Insertion and Deletion faster in LinkedList?

  • Insertion and deletion is faster in LinkedList cause, as we have to update the pointers of the node to the next node

Disadvantages of LinkedList:

  • There is no random access, only sequential access. i.e. if we try to find element “100” and the element “100” is in 20th position. List has to start looking from node 0.
  • More memory is required, as Linkedlist uses pointers to point to next node. Pointers itself will consume memory.

ArrayList:

What is the internal Implementation?

  • It uses Array as internal implementation
  • It has initial size capacity to 10.

Advantages of ArrayList:

  • Manipulation is faster in ArrayList (get operations).

Why get operation is faster in ArrayList?

  • ArrayList has direct references to every element in the list, so it can get the n-th element at constant time.

Disadvantages of ArrayList:

  • Insertion and deletion are more expensive, as all the elements needs to be shifted in the array
  • ArrayList initial size is 10, once the size is reached it will rebuild itself with 50% more space.

Let us see the Difference between – Array, ArrayList and LinkedList

Array

ArrayList

LinkedList

We need to give initial size and it will not grow dynamically

Internal implementation of Array, but grows itself to 50% when capacity is reached

Internal implementation is doubly LinkedList – no initial capacity, list grows as elements added

Get operation is faster in array list

Insertion and deletion is faster in LinkedList

Insertion and deletion is slower, as all the elements needs to be shifted when delete or insertion is happened

Manipulation is slower as it has to transverse starting from the first element

 

Vector:

Vector is similar to arrayList except this is synchronized. (thread-safe)

Note: ArrayList can also be synchronized using utils – Collection.SynchronizedList();

Whats the difference between Vector vs ArrayList?

ArrayList

Vector

When the list limit reached, it increases its size by one and half

When the list size is reached it increases its size by two times

It is not synchronized, but can be made synchronized using Collections.SynchronizedList(list)

By default it is synchronized

 

CopyOnWriteArrayList:

What is CopyOnWriteArrayList?

  • It is a synchronized collection, which allows multiple thread to read values at same time.

How does it work?

  • For every update operation, CopyOnWriteArrayList creates a cloned copy of list and will update and sync with the main list at a point of time as decided by JVM

  • very efficient if you have a List where Iteration outnumber mutation e.g. you mostly need to iterate the ArrayList and don’t modify it too often.

  • No concurrent modification exception thrown, when the data is modified. As the iterator works on list but the updates take place in cloned copy of list.

  • But when you try to remove an element during Iteration, it will throw UnsupportedOperationException.

Inner Classes In Java – Static, Non Static, Method Inner and Anonymous Classes

Inner Classes In Java – Static, Non Static, Method Inner and Anonymous Classes

What are inner classes?
A class which is defined within another class is the inner class.

What is the use of inner class?
The  inner class is mainly used as logically grouping classes at one place.If you have a class and that class is used only by one other class, then we can group the first class within another class.

There are two types of Inner class,

  • Static Nested Class
  • Non Static Nested Class
    • Method Local
    • Anonymous Inner Class

Static Nested vs Non-Static Nested Class:
Static Nested Class cannot access outer class variables and methods, where as Non Static nested class have full access to outer class variables and methods.


Static Nested Class:

Static class declared within the outer class.

To access the static inner class,
outerclass.innerclass innerclass = new outerclass.innerclass()

Output:

Non Static Nested Class:

Non Static class declared within the outer class.

outerclass.innerclass innerclass = new outerclass.innerclass()

Output:

Method Local Inner Class:

A class declared within a method and create object and call method within the same method.

Output:

Anonymous Nested Class:

In Anonymous inner class, we use the interface as nested class.

Interface cannot be initialized, so how are we using new keyword?

If we look through the code, we use new keyword for interface but we are not actually creating an object. We use new and implement the interface method and close the curly braces with colon.

Output:

Cloneable Interface – Shallow Copy and Deep Copy with Examples

Cloneable Interface – Shallow Copy and Deep Copy with Examples:
Cloneable means making an exact copy of original object.

Inorder to invoke objects clone method, it should have implemented Cloneable interface. If we try to invoke an object that haven’t implemented Cloneable interface will result in exception “CloneNotSupported”.

  • When a clone is made and if the class has only primitive types, then it will be cloned in new object and will give new references.
  • If there are any member variables present in the class, still object will be cloned but the member variables present in original object and cloned object will point to the same reference.

By default, object’s clone method uses Shallow Copy.

What is Shallow Copy?
It will have the exact copy of the object, if any fields of the object is an reference to another object only the reference address of the object is copied. (Only memory addresses are copied).i.e. If any change made in the field of an object will reflect in the cloned object too.

What is Deep Copy?
If any fields of the object is an reference of another field, It will have the new copy of referred object and not the referred address. So any change made in the original object will not reflect in cloned object.

 

Now let us see an example for Cloneable with ShadowCopy

Department.java

Student.java

We have implemented Cloneable interface and have overridden Clone() method.


From the output, we can see whenever a change is made in Department object and even though it is updated only in original object the change gets reflected in Cloned object too. This is Shallow Copy.

DeepCopy

We are overriding the Clone method for the deep copy to work. We are setting the variables separately so it does not impact the cloned object.

From the output, we can see when a change for Department object is made in original object it does not reflect in the cloned object.

 

Java Memory Model – Memory and Garbage Collection

Java Memory Model – Explained
Java memory model defines how the JVM works in our system. It is vital to understand how the Java memory model works to write the programs. Let us see in details about Java memory model

 

Difference between Heap and Stack

Heap Memory

Stack Memory

Store objects

Store local variables and function call

Has the actual object

Will have reference to the objects in the Heap Memory

OutOfMemory Error

StackOverFlow error when stack is full

All thread can access all objects in the Heap

Only owner thread can access the variables in the Stack

Young Generation:
The young generation is the place where all the new objects are created. When the young generation is filled, garbage collection is performed. This garbage collection is called Minor GC. Young Generation is divided into three parts – Eden Memory and two Survivor Memory spaces.

Important Points:
Most of the newly created objects are located in the Eden memory space.

  • When Eden space is filled with objects, Minor GC is performed and all the survivor objects are moved to one of the survivor spaces.

  • Minor GC also checks the survivor objects and move them to the other survivor space. So at a time, one of the survivor space is always empty.

  • Objects that are survived after many cycles of GC, are moved to the Old generation memory space. Usually, By setting an age for the young generation objects before they become eligible to promote to Old generation.

PermGen space:
Stores class related data, and is used to keep information for loaded classes and few other advanced features like StringPool.

MetaSpace: (From 1.8, instead of perm gen)

  • Are part of native memory – OS level
  • Metaspace by default increases its size , To the limit of OS, while PermGen always has a fixed maximum size.
  • No more out of memory error
  • We can set the size of metaspace and also it increases automatically, but permgen wont increase by itself
  • Garbage collection of the dead classes and classloaders is triggered once the class metadata usage reaches the MaxMetaspaceSize.

So where does static variables and static classes are stored? Is it heap or Permgen?

  • Since the heap has actual objects, static variables and static classes are stored in Permgen / Metaspace.

Eden and Survivor Space:

  • Most of the newly created objects are located in the Eden memory space.
  • When Eden space is filled with objects, Minor GC is performed and all the survivor objects are moved to one of the survivor spaces.
  • Minor GC also checks the survivor objects and move them to the other survivor space. So at a time, one of the survivor space is always empty.
  • Objects that are survived after many cycles of GC, are moved to the Old generation memory space. Usually, it’s done by setting a threshold for the age of the young generation objects before they become eligible to promote to Old generation.

Types of Garbage Collectors:

  • Serial Garbage Collector
  • Parallel Garbage Collector
  • CMS Garbage Collector
  • G1 Garbage Collector


Serial Garbage Collector:
A single thread is used for garbage collection and it will freeze all the application threads while performing GC (Garbage Collection).

Parallel Garbage Collection:
It uses multiple threads for garbage collection, this also freezes all the application threads while performing GC

CMS Garbage Collector:
Concurrent Marksweep Garbage collector, CMS scans the heap mark and mark the instances that requires to be removed and then will clear the marked instances

G1 Garbage Collector:
This will divide the heap memory into equal parts and will perform the GC on the part which has lesser live data.

What is the difference between CMS and G1GC?

Both are designed to minimize long pause when performing GC. But G1GC is used for larger heap that is more than 4GB.

CMS – Uses one or more thread to scan the memory periodically and remove the unused objects, where pause time is minimal but cpu time is more

G1GC – It divides the memory into equal parts and cleans old generation by copy from one part to another.

Callable and Runnable Examples – ExecutorService

ExecutorService – Callable and Runnable Example
In this article let us see an example using Runnable and Callable tasks using ExecutorService.

Please refer here for Overview of ExecutorService

Runnable Example
Runnable does not return any value and cannot throw checked exceptions

Output:

NOTE:
From the output, we can notice how the executorservice works. We haven’t used Synchronized keyword in any of our methods, but ExecutorService makes sure one thread accesses the methods at a time.

Callable Example
Callable can return Future objects and can throw checked exceptions

Output:

We  have used future object to return string, Future object can return Integer, Boolean etc.
Sample example of using Boolean for the above code,