package com.java.linklist;
public class LinkedList<T> {
public static class Node<T> {
// reference to the next node in the chain, or null if there isn't one.
Node<T> next;
// data carried by this node. could be of any type you need.
T data;
// Node constructor
public Node(T dataValue) {
next = null;
data = dataValue;
}
// another Node constructor if we want to specify the node to point to.
public Node(T dataValue, Node<T> nextValue) {
next = nextValue;
data = dataValue;
}
// these methods should be self-explanatory
public T getData() {
return data;
}
public void setData(T dataValue) {
data = dataValue;
}
public Node<T> getNext() {
return next;
}
public void setNext(Node<T> nextValue) {
next = nextValue;
}
}
private Node<T> head;
private Node<T> tail;
public LinkedList() {
}
LinkedList(T data) {
Node<T> n1 = new Node<T>(data);
this.head = n1;
this.tail = n1;
}
/**
* appends the specified element to the end of this list.
*
* @param data
*/
public void add(T data) {
// if we have an empty list, create a new list
// and copy its head and tail into current object
if (this.head == null) {
LinkedList<T> linkList = (new LinkedList<T>(data));
this.head = linkList.head;
this.tail = linkList.tail;
return;
}
// we need to add this node 'n' to the end of the list
Node<T> n = new Node<T>(data);
Node<T> current = this.head, prev = null;
while (current != null) {
prev = current;
current = current.next;
}
prev.next = n;
this.tail = n; // update the tail info as well
}
public String toString() {
String output = "";
if (head != null) {
Node<T> n = head.getNext();
output += "[" + head.getData().toString() + "]-->";
//System.out.println("[" + head.getData().toString() + "]");
while (n != null) {
output += "[" + n.getData().toString() + "]-->";
//System.out.println("[" + n.getData().toString() + "]");
n = n.getNext();
}
}
return output;
}
/**
* introduces loop of given length at the end of the list.
*
* @param length
*/
public void introduceLoop(int length) {
if (this.head == null) {
System.out.println("Empty List. Loop can not be inserted");
return;
}
Node<T> p1 = this.head, p2 = this.head;
int count = 0;
while (count < length) {
if (p2 == null) {
System.out.println("Incorrect length of the loop given");
break;
}
p2 = p2.next;
count++;
}
Node<T> prevP2 = null;
while (p2 != null) {
prevP2 = p2;
p2 = p2.next;
p1 = p1.next;
}
prevP2.next = p1;
System.out.println("Loop or cycle Start of length " + length
+ " and the value of node is -->" + p1.data);
}
/**
* <ul>
* <li>The Tortoise (Slow ptr) and the Hare (fast ptr) start at the
* beginning of linked list.</li>
* <li>For each iteration, slow ptr moves one step and the fast ptr moves
* two steps.</li>
* <li>If there is a loop, fast ptr will go around the loop and meet with
* slow ptr.</li>
* <li>If there is no loop, the fast prt will get to the end of the list
* without meeting up with the slow ptr.</li>
* </ul>
*
* @return boolean
*/
public boolean ifLoopExists() {
Node<T> fastPtr = head;
Node<T> slowPtr = head;
while (slowPtr != null && fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next;
slowPtr = slowPtr.next;
if (slowPtr == fastPtr)
return true;
}
return false;
}
/**
* <ul>
* <li>The Tortoise (Slow ptr) and the Hare (fast ptr) start at the
* beginning of linked list.</li>
* <li>For each iteration, slow ptr moves one step and the fast ptr moves
* two steps.</li>
* <li>If there is a loop, fast ptr will go around the loop and meet with
* slow ptr.</li>
* <li>If there is no loop, the fast prt will get to the end of the list
* without meeting up with the slow ptr.</li>
* </ul>
* @return Node
*/
public Node<T> findStartNodeOfTheLoop() {
Node<T> fastPtr = head;
Node<T> slowPtr = head;
boolean loopExists = false;
while (fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next;
slowPtr = slowPtr.next;
if (slowPtr == fastPtr) {
loopExists = true;
break;
}
}
if (loopExists) {
slowPtr = head;
while (slowPtr != fastPtr) {
slowPtr = slowPtr.next;
fastPtr = fastPtr.next;
}
} else {
System.out.println("Loop does not exists");
slowPtr = null;
}
return slowPtr;
}
public static void main(String[] args) {
System.out.println("------------------Integer-------------------");
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(5);
list.add(6);
list.add(3);
list.add(1);
list.add(2);
System.out.println(list.toString());
list.introduceLoop(3);
System.out.println(list.ifLoopExists());
Node<Integer> startNode = list.findStartNodeOfTheLoop();
if (startNode != null) {
System.out.println("start Node of loop is for integer " + startNode.data);
}
System.out.println("------------------String-------------------");
LinkedList<String> list2 = new LinkedList<String>();
list2.add("Kartik");
list2.add("Mandal");
list2.add("Saharda");
list2.add("kharagpur");
list2.add("Westbengal");
list2.add("India");
System.out.println(list2.toString());
list2.introduceLoop(4);//loop
System.out.println(list2.ifLoopExists());//find out loop
Node<String> startNode2 = list2.findStartNodeOfTheLoop();//find out start point of loop
if (startNode != null) {
System.out.println("start Node of loop is for string " + startNode2.data);
}
}
}
Out put:
------------------Integer-------------------
[5]-->[6]-->[3]-->[1]-->[2]-->
Loop or cycle Start of length 3 and the value of node is -->3
true
start Node of loop is for integer 3
------------------String-------------------
[Kartik]-->[Mandal]-->[Saharda]-->[kharagpur]-->[Westbengal]-->[India]-->
Loop or cycle Start of length 4 and the value of node is -->Saharda
true
start Node of loop is for string Saharda
I am Kartik Chandra Mandal from Bangalore, India. Working as software engineer in Java technology. Have good knowledge of OWASP and CSRF in security for applications and it's implementation in Java technology.