class Node
{
private int data;
private Node next;
public Node()
{
data=0;
next=null;
}
public Node(int data)
{
this.data=data;
next=null;
}
public void setData(int data)
{
this.data=data;
}
public int getData()
{
return data;
}
public void setNext(Node next)
{
this.next=next;
}
public Node getNext()
{
return next;
}
}
class LinkedList
{
private Node head;
private Node tail;
private int size;
public LinkedList()
{
head=null;
tail=null;
size=0;
}
public boolean isEmpty()
{
if(head==null)
{
return true;
}
else
{
return false;
}
}
public void insertAtFirst(int element)
{
Node node=new Node(element);
if(isEmpty())
{
head=node;
tail=node;
}
else
{
node.setNext(head);
head=node;
}
size++;
}
/*public void insertAtLast(int element)
{
//insert at last by using the tail...
Node node=new Node(element);
if(isEmpty())
{
head=node;
tail=node;
}
else
{
tail.setNext(node);
tail=node;
}
size++;
}
*/
public Node getHead()
{
return head;
}
public void insertAtLast(int element)
{
Node node=new Node(element);
Node temp;
temp=head;
if(!isEmpty())
{
while(temp.getNext()!=null)
{
temp=temp.getNext();
}
temp.setNext(node);
tail=node;
}
else
{
head=node;
tail=node;
}
size++;
}
public Node getLastNode()
{
Node temp;
temp=head;
if(!isEmpty())
{
while(temp.getNext()!=null)
{
temp=temp.getNext();
}
}
else
{
System.out.println("Sorry ! List is empty.");
}
System.out.print("\n"+"Last node is :"+" "+temp.getData()+" ");
return temp;
}
public int deleteFirstNode()
{
int response=0;
if(!isEmpty())
{
response=head.getData();
if(head==tail)//size==1
{
head=null;
tail=null;
}
else
{
head=head.getNext();
}
size--;
}
else
{
System.out.println("Sorry !,List is already empty.");
}
return response;
}
/*public int deleteLastNode()//by using only single pointer
{
int response=0;
if(!isEmpty())
{
response=tail.getData();
if(size==1)//head==tail
{
head=null;
tail=null;
}
//In case of multiple nodes
else
{
Node temp;
temp=head;
while(temp.getNext().getNext()!=null)
{
temp=temp.getNext();
}
temp.setNext(null);
tail=temp;
}
size--;
}
else
{
System.out.println("Sorry!,List is already empty.");
}
return response;
}*/
public int deleteLastNode()//by using two reference pointer nodes
{
int response=0;
if(!isEmpty())
{
response=tail.getData();
if(size==1)//head==tail
{
head=null;
tail=null;
}
//In case of multiple nodes
else
{
Node temp;
temp=head;
Node previous=null;
while(temp.getNext()!=null)
{
previous=temp;
temp=temp.getNext();
}
previous.setNext(null);
tail=previous;
}
size--;
}
else
{
System.out.println("Sorry!,List is already empty.");
}
return response;
}
public boolean searchData(int element)
{
boolean response=false;
if(!isEmpty())
{
Node temp=head;
while(temp!=null)
{
if(temp.getData()==element)
{
response=true;
break;
}
temp=temp.getNext();
}
}
else
{
System.out.println("Sorry!,List is already empty.");
}
return response;
}
public int occuranceElement(int element)
{
int count=0;
if(!isEmpty())
{
Node temp=head;
while(temp!=null)
{
if(temp.getData()==element)
{
count++;
}
temp=temp.getNext();
}
}
return count;
}
//Print linked list in reverse order by recursion
public void reverseTraverse(Node node)
{
if(node==null)
{
return;//transfer control
}
else
{
reverseTraverse(node.getNext());
System.out.print(" "+node.getData()+" ");
}
}
//node=head,previous=null;
public void reverse(Node node,Node previous)
{
if(node.getNext()==null)
{
tail=head;
head=node;
node.setNext(previous);
}
else
{
//previous=node
reverse(node.getNext(),node);
node.setNext(previous);
}
}
public void printLinkList()
{
System.out.println();
if(!isEmpty())
{
Node temp;
temp=head;
System.out.print("head"+" "+"---->"+" ");
while(temp!=null)
{
System.out.print(" "+temp.getData()+" "+temp.getNext()+" "+"---->");
temp=temp.getNext();
}
System.out.print("null");
}
else
{
System.out.println("Sorry !, Link list is empty. ");
}
}
}
class LinkListRun
{
public static void main(String args[])
{
LinkedList list=new LinkedList();
list.insertAtFirst(10);
list.insertAtFirst(20);
list.insertAtFirst(30);
list.insertAtFirst(40);
list.printLinkList();
System.out.println("\nPrinting a linked list in reverse order :");
list.reverseTraverse(list.getHead());
list.reverse(list.getHead(),null);
list.printLinkList();
//list.printLinkList();
/* //System.out.print(list.getLastNode());
System.out.println("\n First deleted node data is :"+list.deleteFirstNode());
list.printLinkList();
System.out.println("\n Last deleted node data is :"+list.deleteLastNode());
list.printLinkList();
System.out.println("\n 23 is coming "+list.occuranceElement(23)+"times");
*/
}
}
Expected Output :
0 Comments