Fail Fast And Fail Safe Iterator In Java

In this post we will be discussing about fail-fast and fail-safe iterators present in java.

Sections in this post: 

1. Concurrent Modification
2. Fail Fast Iterator
3. How Fail Fast Iterator works
4. Fail Safe Iterator
5. Examples
6. Difference between fail fast and fail safe iterator

What is Concurrent Modification?

When one or more threads are iterating over a collection and in between, one of the thread changes the structure of the collection (either adding the element to the collection or by deleting the element from the collection or by updating the value at particular position in the collection) is known as Concurrent Modification.

Fail fast Iterator

While iterating through the collection, Fail fast iterators instantly throws Concurrent Modification Exception if there is structural modification  of the collection. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

How  Fail  Fast Iterator  come to know that the internal structure is modified ?

Fail Fast Iterators read underlying collection object data directly. The internal data should not be modified while iterating through the collection. To ensure this it maintains an internal  flag "modCount". Iterator checks the "modCount" flag whenever it gets the next value (using hasNext() method and next() method). Value of mods flag changes whenever there is an structural modification. Thus indicating iterator to throw "ConcurrentModificationException".

Fail safe Iterator

Fail Safe Iterator makes a copy of the underlying collection object and iterates over the copied collection object. Any structural modification done to the iterator affects the copied data structure so, original data structure remains  structurally unchanged. Hence, no ConcurrentModificationException is thrown by the fail safe iterator.

Two  issues associated with Fail Safe Iterator are :

2. Overhead of maintaining the copied data structure i.e memory. 
3. Fail safe iterator does not guarantee that the data being read is the latest data from the underlying original collection object.

Lets see a fail fast iterator example:

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class FailFastExample
{
    public static void main(String[] args)
    {
        Map<string,String> premiumPhone =  
                       new HashMap<string,String>();
        premiumPhone.put("Apple", "iPhone");
        premiumPhone.put("HTC", "HTC one");
        premiumPhone.put("Samsung","S5");
        
        Iterator iterator = premiumPhone.keySet()
                                         .iterator();
        
        while (iterator.hasNext())
        {
            System.out.println(premiumPhone.get(
                                    iterator.next()));
            premiumPhone.put("Sony", "Xperia Z");
        }
    }
}

Output:                                                  
                    ================================================================

      iPhone 

      Exception in thread "main" java.util.ConcurrentModificationException

      at java.util.HashMap$HashIterator.nextEntry(Unknown Source)

      at java.util.HashMap$KeyIterator.next(Unknown Source)

      at FailFastExample.main(FailFastExample.java:20)

We can see that as soon as we try to  put a new entry ("Sony", "Xperia Z"), fail-fast iterator immediately throws ConcurrentModificationException.

lest's see Fail Safe Iterator Example now :

import java.util.concurrent.ConcurrentHashMap;
import java.util.Iterator;

public class FailSafeExample
{
    public static void main(String[] args)
    {
        Map<string,String> premiumPhone = 
                     new ConcurrentHashMap<string,String>();
        premiumPhone.put("Apple", "iPhone");
        premiumPhone.put("HTC", "HTC one");
        premiumPhone.put("Samsung","S5");
        
        Iterator iterator = premiumPhone.keySet()
                                          .iterator();
        
        while (iterator.hasNext())
        {
            System.out.println(premiumPhone
                               .get(iterator.next()));
            premiumPhone.put("Sony", "Xperia Z");
        }
    }
}

Output:

=============================================

S5

HTC one

iPhone

Below table summarizes major differences between fail-fast and fail-safe iterator.

	Fail Fast Iterator	Fail Safe Iterator
Throw ConcurrentModification Exception	Yes	No
Clone object	No	Yes
Memory Overhead	No	Yes
Examples	HashMap,Vector,ArrayList,HashSet	CopyOnWriteArrayList, ConcurrentHashMap

Stack of Strings Implemented in Java

In my previous post we talked about stack implementation using character array.

In this post I will be sharing my code for a stack implementation which can hold String values in other words stack implemented using array of String in java.

Sections in this post: 

1. String Array Based Implementation of stack.

 Let see the code directly as it is self explanatory

public class StackOfStrings {
 // Every stack has a maximum capacity i.e. number of objects it can hold, 
 private static final int CAPACITY = 10;
 // Top will always point to most recently added element in stack 
 //therefore top = -1 implies stack is empty 
 private int top = -1;
 //array to hold stack elemnts.lt is initialized to capacity of stack
 private String[] stackArray = new String[CAPACITY];

 public static void main(String[] args) {
  StackOfStrings stack = new StackOfStrings();
  stack.pop();
  stack.push("aa");
  stack.push("bb");
  stack.push("cc");
  stack.push("dd");
  stack.push("ee");
  stack.printStack();
  System.out.println("=============================");
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
 }

 public boolean isEmpty() {
  return top == -1;
 } 

 public boolean push(String data) {
  
   // Check if stack is full
   // If it is full then we show Stack overflow message
   
  if (isFull()) {
   System.out.println("Stack overflow");
   return false;
  } else {
   stackArray[++top] = data;
   return true;
  }
 }

 public String pop() {
  
   // Check if stack is empty
   //  If it is empty then we show Stack underflow message
   
  if (isEmpty()) {
   System.out.println("Stack underflow");
  } else {
   // decrementing top by one to sake second element from top as top
   top--;
   // we will be returning top+1 value from array 
   //as we have already made top to point second element in stack
   return stackArray[top + 1];
  }
  return null;
 }

 public String peek() {
  // we implement peek by first popping top element then pushing it back
  String element = null;
  if (!isEmpty()) {
   element = pop();
   push(element);
  }
  return element;
 } 

 public boolean isFull() {
  return top == CAPACITY - 1;
 }

 
  // this method just gives view of the stack.
  // As there are only two operation for stack 
  // i.e. push and pop so in theory we can never print a stack
  // without calling those two methods
  
 public void printStack() {
  System.out.print("[");
  for (int i = top; i >= 0; i--) {
   System.out.print(" " + stackArray[i]);
  }
  System.out.println(" ]");
 } 
}

 If we run the program we will get output like this:

Output

================================================================================

Stack underflow
[    ee    dd    cc    bb    aa    ]
=============================
ee
dd
cc
bb
aa
Stack underflow
null
Stack underflow
null

 

Please share your comments if you find anything incorrect, or you want to share more information about the topic discussed above.

 

For further reading:

practice questions on stack

Stack Implementation using int array

Stack Implementation using char array

Stack implementation using link list 

Stack implementation by link list node, 

Stack implementation using doubly link list 

Stack implementation by doubly link list node . 

For complete listing see data structure and algorithm page

Stack Implementaion in Java Using Character Array

In my previous post we talked about basic stack terminologies and simple stack implementation using integer array.

In this post I will be sharing my code for a stack implementation which can hold char values in other words stack implemented using char array in java.

Sections in this post:  

1. char Array Based Implementation of stack. 

 Let see the code directly as it is self explanatory

public class StackUsingCharArray {


    // Every stack has a maximum capacity i.e. number of objects it can hold,
    private static final int CAPACITY = 10;
    
    // Top will always point to most recently added element in stack therefore 
    // top = -1 implies stack is empty
     private    int top = -1;
       //array to hold stack elemnts.lt is initialized to capacity of stack
    private    char[] stackArray = new char[CAPACITY];

    public static void main(String[] args) {
        StackUsingCharArray stack = new StackUsingCharArray();
        stack.pop();
        stack.push('a');
        stack.push('b');
        stack.push('c');
        stack.push('d');
        stack.push('e');
        stack.printStack();       
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
    public boolean isEmpty() {
        return top == -1;
    }

    public boolean push(char data) {
        
         //Check if stack is full
         //If it is full then we show Stack overflow message
         
        if(isFull()) {
            System.out.println("Stack overflow");
            return false;
        }

        else {
            stackArray[++top] =data;
            return true;
        }
    }
    public Character pop() {
        
         // Check if stack is empty
         //If it is empty then we show Stack underflow message 
         
        if(isEmpty()) {
            System.out.println("Stack underflow");
            return null;
        }
        else {
            //decrementing top by one to make second element from top as top element
            top --;
            //we will be returning top+1 value from array as we have already made 
            //top to point second element in stack
            
            return stackArray[top+1];
        }
    }
    public Character peek() {
        // we implement peek by first popping top element then pushing it back
        Character element = null ;
        if(!isEmpty()){
            element = pop();
            push(element);
        }
        return element;
    }
    
    // this method just gives view of the stack. 
    //As there are only two operation for stack i.e. push and pop
    //so in theory we can never print a stack 
    //without calling those two methods
     
    public void printStack() {
        System.out.print("[");
        for(int i = top; i>=0;i--){
            System.out.print("    "+stackArray[i]);
        }
        System.out.println("    ]");
    }
   
    public boolean isFull() {
        return top == CAPACITY -1;
    }
} 

 If we run the program we will get output like this:

Output

================================================================================

Stack underflow
[    e    d    c    b    a    ]
e
d
c
b
a
Stack underflow
null
Stack underflow
null

 

Please share your comments if you find anything incorrect, or you want to share more information about the topic discussed above.

 

For further reading:

practice questions on stack

Stack Implementation using int array

Stack Implementation using array of strings

Stack implementation using link list 

Stack implementation by link list node, 

Stack implementation using doubly link list 

Stack implementation by doubly link list node . 

For complete listing see data structure and algorithm page

Stack Implementaion in Java Using Integer Array

This is my first post on stack data structure. In this post I am sharing my code of a simple Stack of integers which is internally implemented using integer array.

Stack

A stack is a basic data structure that can be logically thought as linear structure represented by a real physical stack or pile, a structure where insertion and deletion of items takes place at one end called top of the stack. The basic concept can be illustrated by thinking of your data set as a stack of plates or books where you can only take the top item off the stack in order to remove things from it. 

                          

Sections in this post: 

1. Basic stack operations. 
• Push and Pop
• peek
• is Full and is Empty
2. My Stack Interface.
3. Array Based Implementation.

Basic stack Operations:

 

Push and Pop

 

A stack has two fundamental operations - Push and Pop.

The Push operation stores something on the top of the stack and the Pop operation retrives something from the top of the stack. 

Peek

 

Peek operation  returns top element from the stack without removing it from the stack. Peek is not a fundamental stack operation but it is usually implemented in stack ADT.

Is Empty and Is Full 

When stack is empty and pop operation is called then stack should throw "Stack underflow error" and if stack is already full and pop operation is called then we should throw "Stack overflow error".

So as to avoid these two errors we implement Is Empty and Is Full methods. Similar to peek, "Is Empty" and "Is Full" are also not fundamental stack operation.

My Stack Interface 

I am creating Stack interface for my Stack ADT. Lets see the code:

public interface StackInterface {
 
  //Method to push data onto stack
  
 public boolean push(int data);
 
  //Method to pop topmost element from stack or most recently added element in stack
  
 public Integer pop();
 
  // This is not a basic stack operation
  // This method should allow a user to see the top most element in stack
  // it is similar to popping and pushing element again.
  
 public Integer peek();
 
  //method should return true if stack is empty else false
  
 public boolean isEmpty();
 
  //Method should return true if stack is full else false

 public boolean isFull();
}

Array Based Implementation

 In an array-based implementation we maintain the following fields:

1.  an array A of a default size (≥ 1),
2. the variable top that refers to the top element in the stack and
3.  the capacity that refers to the array size. 

We say that a stack is empty when top = -1, and the stack is full when top = capacity-1. The variable top changes from -1 to capacity - 1.

              

                                               

Below is my code for implementing integer stack using array:

public class StackUsingIntArray implements StackInterface {
    // Every stack has a maximum capacity i.e. number of objects it can hold.
     private static final int CAPACITY = 10;
 
    //Top will always point to most recently added element in stack therefore
    //top * -1 implies stack is empty
  
    private int top = -1;
    // array to hold stack elemnts.lt is initialized to capacity of stack 
     private int[] stackArray = new int[CAPACITY];        
        
 @Override
 public boolean push(int data) {
  
    //Check if stack is fullIf it is full then we show Stack overflow message
   
     if (isFull()) {
         System.out.println("Stack overflow");
         return false;
     } else {
         stackArray[++top] = data;
         return true;
     }
 }

 @Override
 public Integer pop() {
  
   //Check if stack is empty If it is empty then we show Stack underflow message
   
  if (isEmpty()) {
     System.out.println("Stack underflow");
  } else {
   
    //decrementing top by one to make second element from top as top
   
     top--;

    //we will be returning top+1 value from array as we have already
    //made top to point second element in stack
    
     return (Integer) stackArray[top + 1];

  }
  return null;
 }

 @Override
 public Integer peek() {
     // we implement peek by first popping top element then pushing it back
      Integer element = null;
      if (!isEmpty()) {
         element = pop();
         push(element);
      }
       return element;
 } 
        
 @Override
 public boolean isEmpty() {
     return top == -1;
 }

 @Override
 public boolean isFull() {  
     return top == CAPACITY-1;
 }
        

  //This method just gives view of the stack. As there are only two operation
  //for stack i.e. push and pop so in theory we can never print a stack
  //without calling those two methods
  
 public void printStack() {
     System.out.print("[");
     for (int i = top; i >= 0; i--) {
        System.out.print(" " + stackArray[i]);
     }
     System.out.print(" ]");
 }
        
 public static void main(String[] args) {
  StackUsingIntArray stack = new StackUsingIntArray();
  stack.pop();
  stack.push(40);
  stack.pop();
  stack.push(50);
  stack.pop();
  stack.push(50);
  stack.push(11);
  stack.pop();
  stack.push(50);
  stack.push(32);
  stack.pop();
  stack.pop();
  stack.push(55);
  stack.pop();
  stack.push(68);
  stack.pop();
  stack.push(75);
  stack.push(-12);
  stack.printStack();
  System.out.println();
  System.out.println("=============================");
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  System.out.println(stack.pop());
  stack.push(1);
  stack.push(2);
  stack.push(3);
  stack.push(4);
  stack.push(5);
  stack.printStack();
 }
}

If we run the program we will get output like this:

Output

================================================================================

Stack underflow
[    -12    75    50    ]
====================

-12
75
50
Stack underflow
null
Stack underflow
null
Stack underflow
null
Stack underflow
null
[    5    4    3    2    1    ]

Please share your comments if you find anything incorrect, or you want to share more information about the topic discussed above.

 

For further reading:

Stack Implementation using char array

Stack Implementation using array of strings

Stack implementation using link list 

Stack implementation by link list node, 

Stack implementation using doubly link list 

Stack implementation by doubly link list node . 

For complete listing see data structure and algorithm page

 

Data structure Questions on Link List

In my previous posts we talked about single link list, doubly link list. In this post I am sharing my code solution for few practice question which are also frequently asked in interviews too.

Section in this post:

1. Get Nth node value from end of link list.
2. Print middle node value.
3. Get number of occurrence of a number in link list.
4. Detect loop  and print node where loop is  present in link list using Floyd Cycle-Finding Algorithm:
5. Detect loop using Richard Brent's algorithm:

Get Nth node value from end of link list

Given a Linked List and a number n, we need to write a method  that returns the value at the nth node from end of the Linked List.

Solution: We maintain two references say First and Second. First we move First to n nodes from head.After that we move both references one by one until First reaches end. Now Second will point to nth node from the end.

Lets see in the code now:

public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
  System.out.println("Nth element form last is: "+myProg.getNthFromLast(5));
      }

      public Integer getNthFromLast(int n) {
  // Check if list is already Empty
  if (myList.isEmpty()) {
   System.out.println("List is empty returning null;");
   return null;
  }
  Node firstNode, secondNode;
  firstNode = secondNode = myList.getHead();
  for (int i = 0; i < n; i++) {
   firstNode = firstNode.getNext();
   if (firstNode == null) {
    System.out.println("invalid number given returning null");
    return null;
   }
  }
  while (firstNode != null) {
   firstNode = firstNode.getNext();
   secondNode = secondNode.getNext();
  }
  return secondNode.getData();
 }
}

If we run the program we will get output like this:

Output

========================================================================

List is: [    14    13    12    11    4    3    2    1    54    55    53    56    51    52    44    45    43    11    42    ]
Nth element form last is: 44

 

Print middle node value 

We traverse linked list using two pointers. Moving one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.

Lets see the code now:

public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
                myProg.printMiddle();
      }

      /* method to get the middle of the linked list */
 public void printMiddle() {
 /*
 * We will Traverse linked list using two reference namely fastRef and
 * slowRef Move one first by one and other by two.When the fast ref
 * reaches end slow ref will reach middle of the linked listCheck if
 * list is already Empty
 */

      if (myList.isEmpty()) {
          System.out.println("List is empty");
      }
      Node fastRef, slowRef;
      fastRef = slowRef = myList.getHead();
      while (fastRef != null && fastRef.getNext() != null) {
         fastRef = fastRef.getNext().getNext();
  slowRef = slowRef.getNext();
     }
     System.out.println("Middle node is: " + slowRef.getData()); 
   }
}

If we run the program we will get output like this:

Output

========================================================================

List is: [    14    13    12    11    4    3    2    1    54    55    53    56    51    52    44    45    43    11    42    ]
Middle node is: 55

 

Get number of occurrence of a number in link list 

We are require to find how many time a number is present in the list.

Lets see the code now:

public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
                System.out.println("occurrence is: "+myProg.getOccurrence(11));
      }

        /*
  * Counts the no. of occurrences of a node (search_for) in a linked list
  * (head)
  */
 Integer getOccurrence(int numTosearchFor) {
  // Check if list is already Empty
  if (myList.isEmpty()) {
   System.out.println("List is empty returning null;");
   return null;
  }
  Node currentNode = myList.getHead();
  int count = 0;
  while (currentNode != null) {
   if (currentNode.getData() == numTosearchFor) {
    count++;
   }
   currentNode = currentNode.getNext();
  }
  return count;
 }
}

If we run the program we will get output like this:

Output

========================================================================

List is: [    14    13    12    11    4    3    2    1    54    55    53    56    51    52    44    45    43    11    42    ]
occurrence is: 2

Floyd's Cycle-Finding Algorithm

Floyd's cycle-finding algorithm, also called the "tortoise and the hare algorithm" is a pointer algorithm that uses only two pointers, which move through the sequence at different speeds.

 

                                              

Traverse linked list using two pointers.  Move one pointer by one and other pointer by two.  If these pointers meet at some node then there is a loop.  If pointers do not meet then linked list doesn’t have loop.

Lets see the code now:

public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4); 

               /*
               * Adding two nodes to make a cycle
               */ 
               Node nodeForLoop1 = new Node(22);
        Node nodeForLoop2 = new Node(23);
        nodeForLoop2.setNext(nodeForLoop1); 
                
        myProg.myList.insertAtEnd(nodeForLoop1);
  myProg.myList.insertAtEnd(nodeForLoop2);
      }

      /* Floyd's Cycle-Finding Algorithm */
 public boolean detectloop() {
  /*
   * The fastest way to detect the loop is to use Floyd's Cycle-Finding
   * Algorithm Move one pointer by one and other pointer by two. If these
   * pointers meet at some node then there is a loop. If pointers do not
   * meet then linked list doesn't have loop.
   */

  // Check if list is already Empty
  if (myList.isEmpty()) {
   System.out.println("List is empty returning false:");
   return false;
  }
  Node fastRef, slowRef;
  fastRef = slowRef = myList.getHead();
  while (fastRef != null && fastRef.getNext() != null) {   
   fastRef = fastRef.getNext().getNext();
   slowRef = slowRef.getNext();   
   if (slowRef == fastRef) {
                                //Below method will print node where cycle is present
    getLoopStart(slowRef, fastRef);
    return true;
   }
  }
  return false;
 }

 private void getLoopStart(Node slowRef, Node fastRef) {
  /*
   * Move slowRef to Head. Keep fastRef at Meeting Point. Each are k steps
   * /* from the Loop Start. If they move at the same pace, they must *
   * meet at Loop Start.
   */
  slowRef = myList.getHead();
  while (slowRef != fastRef) {
   slowRef = slowRef.getNext();
   fastRef = fastRef.getNext();
  }
  // Now n2 points to the start of the loop.
  System.out.println("loop at: " + fastRef.getData());
 }
}

If we run the program we will get output like this:

Output

============================================================================

loop at: 22
Is loop present: true

 

Richard Brent's Cycle-Finding Algorithm

In 1980, Brent invented an algorithm that not only worked in linear time, but required less stepping than Floyd's Tortoise and the Hare algorithm (however it is slightly more complex). 

Brent's algorithm features a moving rabbit and a stationary, then teleporting, turtle. Both turtle and rabbit start at the top of the list. The rabbit takes one step per iteration. If it is then at the same position as the stationary turtle, there is obviously a loop. If it reaches the end of the list, there is no loop.

Of course, this by itself will take infinite time if there is a loop. So every once in a while, we teleport the turtle to the rabbit's position, and let the rabbit continue moving. We start out waiting just 2 steps before teleportation, and we double that each time we move the turtle.

Why move the turtle at all? Well, the loop might not include the entire list; if a rabbit gets stuck in a loop further down, without the turtle, it will go forever. Why take twice as long each time? Eventually, the length of time between teleportations will become longer than the size of the loop, and the turtle will be there waiting for the rabbit when it gets back.

Note that like Floyd's Tortoise and Hare algorithm, this one runs in O(N). However you're doing less stepping than with Floyd's (in fact the upper bound for steps is the number you would do with Floyd's algorithm). According to Brent's research, his algorithm is 24-36% faster on average for implicit linked list algorithms.

                               

Lets see the code now:

public class LinkListPrograms {
        //Refer my link list post for link list implementation details
 SLL myList = new SLL();

 public static void main(String[] args) {
  LinkListPrograms myProg = new LinkListPrograms();
                
                myProg.myList.insert(new Node(11),1);
  myProg.myList.insert(new Node(42),2);
  myProg.myList.insert(new Node(43),1);
  myProg.myList.insert(new Node(44),1);
  myProg.myList.insert(new Node(45),2);  

  myProg.myList.insert(51,1);
  myProg.myList.insert(52,2);
  myProg.myList.insert(53,1);
  myProg.myList.insert(54,1);
  myProg.myList.insert(55,2);
  myProg.myList.insert(56,4);

  myProg.myList.insertAtStart(1);
  myProg.myList.insertAtStart(2);
  myProg.myList.insertAtStart(3);
  myProg.myList.insertAtStart(4);

  myProg.myList.insertAtStart(new Node(11));
  myProg.myList.insertAtStart(new Node(12));
  myProg.myList.insertAtStart(new Node(13));
  myProg.myList.insertAtStart(new Node(14));
  myProg.myList.printList(myProg.myList.getHead());
                System.out.println(myProg.hasLLoop(myProg.myList.getHead()));
      }

     /*
  * Richard Brent's algo: Richard Brent described an alternative cycle
  * detection algorithm,which is pretty much like the hare and the tortoise
  * [Floyd’s cycle] except the slow node here doesn't move, but is later
  * " teleported" to the position of fast node at fixed intervals
  */
 public boolean hasLLoop(Node root) {
  if (root == null) {
   return false;
  }
  Node slow = root, fast = root;
  int taken = 0, limit = 2;
  while (slow.getNext() != null && fast.getNext() != null) {
   fast = fast.getNext();
   taken++;
   if (slow == fast) {
    return true;
   }

   if (taken == limit) {
    taken = 0;

    limit <<= 1; // equivalent to limit *= 2
    slow = fast; // teleporting the turtle to the hare's position
   }
  }
  return false;
 }
}

If we run the program we will get output like this:

Output

============================================================================

true

Please share your comments if you find anything incorrect, or you want to share more information about the topic discussed above.

I will keep adding more Question here :)