Feb 23, 2014

Reverse a singly linked list in Java - Recursive and Iterative approach

Linked list reversal is common interview question. Linked list can be reverse in both iterative and recursive way. Recursive way is little bit difficult to code compare to iterative one.Iterative one is memory efficient when dealing with large number of nodes.In this post first we will first write sample code for linked list in recursive way and followed by the iterative approach. Download complete program.
Recursive approach :- When we think of reversal of linked list by recursion, the very first thing comes in mind - reach at end of list and come back to starting point. Lets write the sample code and understand each steps involved from associated in-line comments.
/* Reverse a singly linked list using recursion */
static public Node reverseLinkedListUsingRecursion(Node head) {
/* Return null , if list is empty or head if head.next = null */
if (head == null || head.getNext() == null) {
return head;
} else {
/* Store next node of list */
Node nextNode = head.getNext();
/* For storing reference of last node of list */
Node retHead = reverseLinkedListUsingRecursion(nextNode);
/* Set next reference of the given node to null, breaking the chain */
head.setNext(null);
/* Add next reference in reverse order */
nextNode.setNext(head);
/* Return last node of the given list */
return retHead;
}
}

Iterative approach :- 
Writing iterative code is memory efficient and easy to understand.Below is the sample code for the same.Go through the in-line comments associated with each step.
/* Reverse a singly linked list */
static public Node reverseLinkedListIterative(Node head) {
/* Return null , if list is empty or head if head.next Is null */
if (head == null || head.getNext() == null) {
return head;
} else {
Node previous = null;
Node current = head;
Node curNext;
/* Iterate linked list and reverse the next reference for each node */
while (current != null) {
curNext = current.getNext();// Store next node for iteration
current.setNext(previous); // set current next as previous
/* store current in previous, for next iteration */
previous = current;
current = curNext;
}
/*
* Once we complete the list iteration, previous refers to last
* node, so assign that to head
*/
head = previous;
}
return head;
}

Here is the complete sample program for the reversal of linked list using recursive and Iterative approach:-
package com.devinline.linkedlist;

public class ReverseSinglyLinkedlist {
static Node head = null;

/* Reverse a singly linked list using recursion */
static public Node reverseLinkedListUsingRecursion(Node head) {
/* Return null , if list is empty or head if head.next = null */
if (head == null || head.getNext() == null) {
return head;
} else {
/* Store next node of list */
Node nextNode = head.getNext();
/* For storing reference of last node of list */
Node retHead = reverseLinkedListUsingRecursion(nextNode);
/* Set next reference of the given node to null, breaking the chain */
head.setNext(null);
/* Add next reference in reverse order */
nextNode.setNext(head);
/* Return last node of the given list */
return retHead;
}
}

/* Reverse a singly linked list */
static public Node reverseLinkedListIterative(Node head) {
/* Return null , if list is empty or head if head.next Is null */
if (head == null || head.getNext() == null) {
return head;
} else {
Node previous = null;
Node current = head;
Node curNext;
/* Iterate linked list and reverse the next reference for each node */
while (current != null) {
curNext = current.getNext();// Store next node for iteration
current.setNext(previous); // set current next as previous
/* store current in previous, for next iteration */
previous = current;
current = curNext;
}
/*
* Once we complete the list iteration, previous refers to last
* node, so assign that to head
*/
head = previous;
}
return head;
}

private static Node createNewNode(int data) {
/*Inner class Object creation*/
return new ReverseSinglyLinkedlist().new Node(data);
}

/* Add New node at start of linked list */
private static void insertFirst(int data) {
Node newNode = createNewNode(data);
if (head == null) {
head = newNode;
} else {
newNode.setNext(head);
head = newNode;
}
}

/* Display data of nodes/iterate linked list */
private static void iterateLinedList(Node head) {
Node current = head;
if (head != null) {
System.out.print("[");
while (current != null) {
System.out.print(current.getData() + " ");
current = current.getNext();
}
System.out.print(" ]\n");
} else {
System.out.println("Linked list is empty.");
}

}

class Node {

private int data;
private Node next; // reference(handler) for next Node.

public Node(int data) {
this.data = data;
this.next = null;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public int getData() {
return data;
}

}

public static void main(String[] args) {
/* Setup a linked list */
insertFirst(142);
insertFirst(135);
insertFirst(141);
insertFirst(141);
insertFirst(145);
insertFirst(148);
insertFirst(145);
/* Original linked list display */
System.out.println("Original linked list ");
iterateLinedList(head);

/* Reverse a singly linked list using recursion and display the same */
Node newhead1 = ReverseSinglyLinkedlist
.reverseLinkedListUsingRecursion(head);
System.out.println("Reversed linked list(Recursive approach) ");
iterateLinedList(newhead1);

/* Reverse a singly linked list using iterative and display the same */
Node newhead2 = ReverseSinglyLinkedlist
.reverseLinkedListIterative(newhead1);
System.out.println("Reversed linked list(Iterative appraoch) ");
iterateLinedList(newhead2);
}

}
========Sample output==============
Original linked list
[145 148 145 141 141 135 142  ]
Reversed linked list(Recursive approach)
[142 135 141 141 145 148 145  ]
Reversed linked list(Iterative appraoch)
[145 148 145 141 141 135 142  ]
=================================

Feb 15, 2014

Find length of Linked list - Recursive and iterative approach

To find length of linked list is one of warm-up interview question. Idea here is to write sample program to find length of list using recursion, iterative way of finding is not a big deal(iterate linked list and maintains a counter & increment for each node).A better understanding of recursion is important to solve various Linked list problems and finding length is list one of the easy problem which gives an overview of recursion.
Using recursion:- Below is sample code line which calculates length of list recursively(Download complete sample program).
/* length of list by iterating list recursively */
public static int findLengthOfListRecursion(Node head) {
int length = 0;
/* If list is empty or we have reached at end of list */
if (head == null)
return 0;
else
/* call this method again with next node */
length = 1 + findLengthOfListRecursion(head.getNext());
return length;
}
Explanation:- For each recursive call, null check for head is performed, if head is null it indicates - we have reached at end of the list and it returns 0. Otherwise, else block is executed and length is incremented by 1 and recursive call is made for next node.

Using Iterative approach :- Below is sample code line which calculates length of list by traversing list (Download complete sample program).
/* length of list by iterating list */
public static int findLengthOfListIterative(Node head) {
int length = 0;
/* If list is empty, return length is 0 */
if (head == null) {
return length;
} else {
Node current = head;
/* Iterate list and increment length for each node */
while (current != null) {
length += 1;
current = current.getNext();
}
}
return length;
}
Explanation:- Iterate the list until we reaches at end of list and increment length for each node. Once we reach at end of list, we have length of list.

Below is the complete sample program for the length calculation using recursion and iterative approach:-
public class LengthOfLinkedlist {
static Node head;

/* length of list by iterating list recursively */
public static int findLengthOfListRecursion(Node head) {
int length = 0;
/* If list is empty or we have reached at end of list */
if (head == null)
return 0;
else
/* call this method again with next node */
length = 1 + findLengthOfListRecursion(head.getNext());
return length;
}

/* length of list by iterating list */
public static int findLengthOfListIterative(Node head) {
int length = 0;
/* If list is empty, return length is 0 */
if (head == null) {
return length;
} else {
Node current = head;
/* Iterate list and increment length for each node */
while (current != null) {
length += 1;
current = current.getNext();
}
}
return length;
}

/* Add New node at start of linked list */
private static void insertFirst(int data) {
Node newNode = createNewNode(data);
if (head == null) {
head = newNode;
} else {
newNode.setNext(head);
head = newNode;
}
}

private static Node createNewNode(int data) {
return new LengthOfLinkedlist().new Node(data);
}

class Node {

private int data;
private Node next; // reference(handler) for next Node.

public Node(int data) {
this.data = data;
this.next = null;
}

public Node getNext() {
return next;
}

public void setNext(Node next) {
this.next = next;
}

public int getData() {
return data;
}
}

public static void main(String[] args) {
/* Setup a linked list */
insertFirst(142);
insertFirst(135);
insertFirst(141);
insertFirst(141);
insertFirst(145);
insertFirst(148);
insertFirst(145);

/* Find length of linked list using recursive call */
int length = LengthOfLinkedlist.findLengthOfListRecursion(head);
System.out.println("length of list(recursion) : " + length);

/* Find length of linked list using recursive call */
int length2 = LengthOfLinkedlist.findLengthOfListIterative(head);
System.out.println("length of list(Iterative) : " + length2);
}
}
========Sample output========
length of list(recursion) : 7
length of list(Iterative) : 7
==========================

Some other linked list problems that use linked list iteration / length of linked list, try following questions:- 

1. Find sum of all elements of linked list.
2. Find mean of linked list, provided data is of number type.
3. Count number of odd and even numbers in the given linked list.
4.  Find middle element of  the linked list.(For even # of elements first node the two middle node is mean)
5. Check whether the given linked list is palindrome or not.

Feb 8, 2014

Textual description of firstImageUrl

Singly Linked list fundamentals and associated operations (Create, Insert, Delete, Iterate)

In Java, we create object dynamically using new operator and it is stored in heap memory location. Each object created is associated with a handler(a reference to that object, if not that object will be garbage collected).
Lets consider a scenario, all objects created on heap is not associated with reference(usually we do when object is created), instead each object has reference of another object and we have reference of only the very first object created.Refer the following diagram and understand how a collection of objects linked in specifies order form a new data structure.
A collections of objects(say nodes in linked list terminology) dynamically created and allocated chunk of memory “on the fly.” and all created nodes are linked together in some pattern,this entire structure is termed as Linked list.Linked list can be of Singly, Doubly or Double ended linked list.

Singly linked list - In singly lined list, the very first node has where about of second node and second node has where about of third node and so on.However, second node does not know about first node, so as third node does not know about second know. In other words, each node has only one reference, of next node. How do we define node in Java code:-
public class Node {
 private int data;
 private Node next; // reference(handler) for next Node.

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node getNextnode() {
  return nextnode;
 }

 public void setNextnode(Node nextnode) {
  this.nextnode = nextnode;
 }
}
Class Node has two fields, one primitive type(data) and another one of reference type(next). Since, only one reference for node type is present in Node class , we can reference only one node with that. that's why it is called singly liked list.
Singly Lined list - data and next as fields 
Doubly linked list - If we add one more reference type(previous) and it is used to reference previous node then that linked list pattern is termed as Doubly-linked list. Doubly-linked list Node class may be obtained by adding a reference type and its getter & setter as follows:-
public class Node {
 .....
 private Node previous;// reference(handler) for previous Node.
 
 public Node getPrevious() {
  return previous;
 }

 public void setPrevious(Node previous) {
  this.previous = previous;
 }
        ....
        ......
}
Doubly linked list - data, previous and previous as fields 
In following posts term linked list refers Singly linked list and we will use singly linked list for solving our most of the problems.As an introductory exercise we will write a sample program to create a linked list and write methods associated with it.
Hide code lines
package com.devinline.linkedlist;

public class SinglyLinkedListOperations {

 static Node head = null;

 private static Node createNewNode(int data) {
  return new Node(data);
 }

 /* Add New node at start of linked list */
 private static void insertFirst(int data) {
  Node newNode = createNewNode(data);
  if (head == null) {
   head = newNode;
  } else {
   newNode.setNext(head);
   head = newNode;
  }
 }

 /* Add New node at after a given node in Linked list */
 private static void insertAfterNode(Node node, int data) {
  Node newNode = createNewNode(data);
  Node current = head;
  if (head == null) {
   head = newNode;
  } else if (current.getData() == node.getData()) {
   newNode.setNext(current.getNext());
   current.setNext(newNode);
  } else {
   while (current != null) {
    if (current.getData() == node.getData()) {
     break;
    } else {
     current = current.getNext();
    }
   }
   if (current != null) {
    newNode.setNext(current.getNext());
    current.setNext(newNode);
   }

  }
 }

 /* Add New node at before a given node in Linked list */
 private static void insertBeforeNode(Node node, int data) {
  Node newNode = createNewNode(data);
  Node current = head;
  Node previousNode = null;
  if (head == null) {
   head = newNode;
  } else if (current.getData() == node.getData()) {
   newNode.setNext(current);
   head = newNode;
  } else {
   while (current != null) {
    if (current.getData() == node.getData()) {
     break;
    } else {
     previousNode = current;
     current = current.getNext();
    }
   }
   if (current != null) {
    previousNode.setNext(newNode);
    newNode.setNext(current);
   }

  }
 }

 /* Iterate linked list, reach at end and add new node */
 private static void insertLast(int data) {
  Node newNode = createNewNode(data);
  Node current = head;
  if (head == null) {
   head = newNode;
  } else {
   while (current.getNext() != null) {
    current = current.getNext();
   }
   current.setNext(newNode);
   newNode.setNext(null);
  }
 }

 /* Display data of nodes/iterate linked list */
 private static void iterateLinedList(Node head) {
  Node current = head;
  if (head != null) {
   System.out.print("Data in linkedlist:[");
   while (current != null) {
    System.out.print(current.getData() + " ");
    current = current.getNext();
   }
   System.out.print(" ]");
  } else {
   System.out.println("Linked list is empty.");
  }

 }

 /* Find node with given value */
 private static boolean findNode(int data) {
  Node current = head;
  if (head != null) {
   while (current != null) {
    if (current.getData() == data) {
     return true;
    }
    current = current.getNext();
   }
  }
  return false;
 }

 /* Delete a given node */
 private static boolean deleteNode(int data) {
  Node current = head;
  Node backupNode = null;
  if (head != null && head.getData() == data) {
   head = current.getNext();
   return true;
  }
  if (current != null) {
   while (current != null) {
    if (current.getData() == data) {
     break;
    } else {
     backupNode = current;
     current = current.getNext();
    }
   }
   if (current != null) {
    backupNode.setNext(current.getNext());
    current = null;// garbage collected
    return true;
   }

  }
  return false;
 }

 public static void main(String[] args) {
  /* Create Linked list */
  insertFirst(13);
  insertLast(23);
  insertFirst(14);
  insertFirst(134);
  insertLast(23);
  insertFirst(142);
  insertFirst(135);
  insertFirst(141);
  insertFirst(141);
  insertFirst(145);
  insertFirst(148);
  insertFirst(145);
  insertLast(124);

  /* Display data of list, iterate linked list */
  iterateLinedList(head);

  /* Find a node, if exist */
  Boolean found = findNode(14);
  System.out.println((found == true) ? "\nNode exist "
    : "\nNot does not exist  ");

  /* Delete a Node */
  Boolean delStat = deleteNode(141);
  System.out.println((delStat == true) ? "\nNode deleted "
    : "\nNot does not exist  ");
  iterateLinedList(head);

  /* insert After Node operation*/
  insertAfterNode(createNewNode(124), 237);
  System.out.println("\n\nlist after insert afterNode operation");
  iterateLinedList(head);

  /* insert Before Node operation */
  insertBeforeNode(createNewNode(13), 297);
  System.out.println("\n\nlist after insert beforeNode operation ");
  iterateLinedList(head);

 }
}
In above program, we have created several methods for the linked list like:
1. createNewNode(int data) - It creates a Node with value data and returns the same.
2. insertFirst(int data) - It creates a Node and add it to, start of linked list. If head is null then it means linkedlist is empty and head is pointing to newly created node. Otherwise, newly created node is added before first node of linked list and head point to newly created node.
3. insertLast(int data) - It creates a new node and add it to end of the list.Since, we do not have direct reference for last node, we need to traverse to the end of list and then add the node at the end. Here with while() loop, we are iterating the list and reaches at end of list.
4. insertAfterNode(Node node, int data) - In this method, first we check whether head is null or not, if null head points to newly created node. If head it self is that reference node, then add newly created node next to it. If reference node is in middle or some where, iterate list an find that node. Once we get that node, come out of loop and add newly created node.
5. insertBeforeNode(Node node, int data) - Here we need to maintain previous node because once we move on from a given node we do not have control over that and since we have to add node right before that current node, so we maintain previous node reference using previousNode. Adding of node is similar to above method.
6. iterateLinedList(Node head) - Here we iterate linked list using loop and display each data value until we reach at end of loop.
7. findNode(int data) - Similar to above method, iterate the list linked list and compare for the data value, if found return true.
8. deleteNode(int data) - here node with the given value is deleted. First check whether first node is that node to be deleted, if true , head start pointing to second node. Otherwise, if that node is in between somewhere, loop through linked list and find that node. If found, come out of the loop. In loop we maintain backupNode(a reference to previous node) so that after removing current node this node will have reference of next of current(node to be deleted).
=============Sample output================
Data in linkedlist:[145 148 145 141 141 135 142 134 14 13 23 23 124  ]
Node exist

Node deleted
Data in linkedlist:[145 148 145 141 135 142 134 14 13 23 23 124  ]

list after insert afterNode operation
Data in linkedlist:[145 148 145 141 135 142 134 14 13 23 23 124 237  ]

list after insert beforeNode operation
Data in linkedlist:[145 148 145 141 135 142 134 14 297 13 23 23 124 237  ]
=========================================

Feb 3, 2014

Display linked list in reverse order in Java

In order to display linked list in reverse order we can use fundamental of recursion - call method recursively and display node while returning from where it was called.
Sample code for displaying data in reverse order:
private void displayLinkedListInReverseOrder(Node head) {
 if (head == null)
  return;
 /* Recursive call for next node */
 displayLinkedListInReverseOrder(head.next);
 System.out.println(head.data);
}
Explanation :- Method displayLinkedListInReverseOrder(node) is called recursively for each node and when end of list or list is empty, method call simply returns to caller. While returning to caller head element is displayed.

Below is complete sample program for displaying linked list in reverse order:-
package com.devinline.linkedlist;

public class DisplayLinkedList {
 private void displayLinkedListInReverseOrder(Node head) {
  if (head == null)
   return;
  /* Recursive call for next node */
  displayLinkedListInReverseOrder(head.next);
  System.out.print(head.data + " ");

 }

 class Node {
  public int data;
  public Node next;

  public Node(int data) {
   this.data = data;
   this.next = null;
  }
 }

 public static void main(String[] args) {
  DisplayLinkedList cyc = new DisplayLinkedList();
  Node node1 = cyc.new Node(12);
  Node head = node1;
  Node node2 = cyc.new Node(18);
  Node node3 = cyc.new Node(172);
  Node node4 = cyc.new Node(62);
  Node node5 = cyc.new Node(632);
  Node node6 = cyc.new Node(192);
  head.next = node2;
  head.next.next = node3;
  head.next.next.next = node4;
  head.next.next.next.next = node5;
  head.next.next.next.next.next = node6;
  System.out.println("Original list is:  12 18 172 62 632 192");
  System.out.print("Display in reverse order : ");
  cyc.displayLinkedListInReverseOrder(head);

 }

}
=======Sample output==========
Original list is:  12 18 172 62 632 192
Display in reverse order : 192 632 62 172 18 12
============================

Read also :-
How to reverse a linked list using recursion.
Textual description of firstImageUrl

How generics works internally in java

Generics was added in java as part of JDK 5. It is one of the key area from where questions being asked at senior java developer level and expected to have solid understanding of generics fundamentals and its internal workings. The main agenda of this article to understand internal workings of Generics, click here for detailed discussion of generics fundamental.
Lets understand fundamental of generics with an example, followed by we will see the internal  of generics. What is generics in java - Generics provides a way for you to communicate the type of a collection to the compiler, so that compiler will verify whether you have used the collection consistently or not and provide tighter type checks at compile time to support generic programming. In other words, in order to avoid  run time failure of java program, generics provides a mechanism which force compiler to check for correctness of type (allowed object for placeholder). Lets see this sample code :
class GenericsSample<T extends Number> {
 private T data;
 private T[] intArray;
 public GenericsSample(T data){
  this.data = data;
 }
 
 // methods for finding sum of all numbers of intArray.
}
In the above sample code, class name has been appended with <T extends Number> i.e: GenericsSample <T extends Number>. By doing so, we instruct compiler that T is a placeholder and only acceptable values for this placeholder is of type Number(Integer,Float, Double,etc.). Please note, primitives are not allowed in generics, that's why Integer not int.
Why we need generics ? - generics gives developer an opportunity to fix java program problems at compile time rather than dragging it to run-time failure, as we know run-time failure is a nightmare.
Now come back to main agenda of this article, to understand the internal working of generics.Generic code had to be compatible with preexisting non-generic code(java 4 and before)., so how does backward compitablity has been maintained with generics introduction. The way Java implements generics while satisfying the constraint(to avoid breaking older code) is through the use of erasure. To implement generics, the Java compiler applies type erasure.
What is this erasure and how does it important for generics ?
Erasure is that entity which understand raw java code(embedded with generics syntax) and convert it into plain ordinary classes, interfaces, and methods at compile time,so that generics incur no run-time overhead.
How erasure makes generics embedded code compatible with older java code ?
1. First, when Java code is compiled, all generic type information is removed (erased) and type parameters is replaced with their bound type, which is Object if no explicit bound is specified.The produced byte-code, therefore, contains only ordinary classes, interfaces, and methods.
2. Insert type casts,  if necessary to preserve type safety.
3. Generate bridge methods to preserve polymorphism in extended generic types.
Lets consider the following two scenario to understand how a java class with generics syntax transformed independent of generics.
Case 1: Type parameter is unbounded-  Column 1 represents java class with generics syntax embedded and column 2 is compiled version after applying erasure:

Since the type parameter T is unbounded(not super class or subclass specified), the Java compiler replaces all placeholder T with Object(parent of all class).
Case 2: Type parameter is bounded- Column 1 represents java class with generics syntax embedded and column 2 is compiled version after applying erasure:
Here the type parameter T is bounded(String super class specified), the Java compiler replaces all placeholder T with java.lang.String.
Now we will see generics in class hierarchy(involved method overriding) and discuss the importance of Bridge method in it.Consider following example with Node as parent class and MyNode as child class extending parent class Node.
//parent class
public class Node<T> {
    public T data;
    public Node(T data) { 
      this.data = data; 
 }
    public void setData(T data) {
        System.out.println("Node.setData");
        this.data = data;
    }
}
//child class
public class MyNode extends Node<Integer> {
    public MyNode(Integer data) { 
    super(data); 
 }
    public void setData(Integer data) { // overrididng method 
        System.out.println("MyNode.setData");
        super.setData(data);
    }
}
After type erasure, the method signatures do not not match. The Node method becomes setData(Object) and the MyNode method becomes setData(Integer).
public void setData(T data) {  ....  } transformed  to 
                   public void setData(Object data) { ...  }
   and 
 public void setData(Integer data) { ... } tranformed to 
                      public void setData(Integer data) {...}
Therefore, the MyNode setData method does not override the Node setData method and  doesn't preserve the polymorphism of generic types. Here Bridge method comes for rescue, Java compiler generate bridge method in child class and ensure that subtyping works as expected.See below diagram, we have bridge method generated in child class  "setData(Object data) { }" overriding parent class method.
So, now bridge method delegates call to original setData(Integer) and maintains polymorphoism.
This is all about generics internal. Please refer this for understanding restriction in generics.

                                                 ==========End of article=========
Happy learning
Nikhil