Frequently Performed Operations in List

Frequently Performed Operations in List

In our previous article, we had discussed about List interface, types of lists, internal working along with their advantages and disadvantages. (Please read here).

In this article we can discuss some of the most frequently performed list operations and which has to be remembered at all times.

Arrays.asList:

When we use Arrays.asList, it converts the array elements into a fixed size list. Let us see an example,

Now we have a fixed size list -> stringList.

What will be the output?

Now let us try to add an element “Echo” to the above list,

As a common expectation it should add the element to the list, But unfortunately we will get an exception when we try to add an element to the above list,

We will get the same exception when we try to remove an element from the above list, but why?

But, Why?

When we use Arrays.asList -> it returns a fixed size list which limits to perform add / remove operations.

Updating is possible:

Even if we have the limitation to add / remove an element, we can still update the list as the list size is not going to change.

Here is the sample code,

Now for other examples, let us create 2 lists,

We have 2 lists where 5 and 11 are common elements and we have 2 elements 90 in second list as duplicates.

Max and Min in the list:

How to find the maximum element and minimum element in the list ?

We can use ,

What is the list is empty or if it is a generic list when trying Collections to get min or max?

If the list is empty we will get NoSuchElementException and if the list is generic (list contains mix of string, integers etc…) it will throw ClassCastException.

How can we concatenate or add two lists?

Example, if we can to add both the lists intList1 and intList2 , we can use

This will combine all the elements to both lists together.

How to Concatenate or Add two lists avoiding duplicates?

There are two ways of doing this,

Type 1:

We can use streams to get distinct elements,

Type 2:

 

Replacing all the occurrences of a element in the list:

Consider in the intList2, we have element 90. Now if we want to replace all the occurrences of element 90 with 100 in list2, how can this be done?

This will replace element 90 to 100 in intList2.

How can we make a list Synchronized?

The lists are not thread-safe by default, suppose if we want to make the list threadsafe, we can use

SingletonList vs UnmodifiableList:

We have Collections.singletonList and Collections.unmodifiableList. So what is the difference between these two?

Collections.singletonList:  will take single element or object and makes it an immutable list with that single element or object.

Collections.unmodifiableList: Will make the list as an read-only list, when any add or remove operations are performed, it will throws UnSupportedOperationException

 

 

Read More

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.

Read More

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:

Read More

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.

 

Read More

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.

Read More