import java.util.*;
public class singlelinklist
{

private static class node
{
private int data;
private node next;

public node(int data)
{
this.data=data;
this.next=null;
}
}
public void display(node head)//traversal of single link list....
{
if(head==null)
{
return;
}
node current=head;
while(current!=null)
{
System.out.print(current.data+"--->");
current=current.next;
}
System.out.print(current);
}
public int length(node head)//count the number of node by iterative method....
{
if(head==null)
{
return 0;
}
int count=0;
node current=head;
while(current!=null)
{
count++;
current=current.next;
}
return count;
}
public int getlength(node head)//count the number of node using recursion....
{
if(head==null)
{
return 0;
}
return(1+getlength(head.next));
}
public node insertAtBeginning(node head,int data)//insert node at beginning....
{
node newnode=new node(data);
if(head==null)
{
return newnode;
}
newnode.next=head;
head=newnode;
return head;
}
public node insertAtEnd(node head,int data)//insert node at end....
{
node newnode=new node(data);
if(head==null)
{
return newnode;
}
node current=head;
while(current.next!=null)
{
current=current.next;
}
current.next=newnode;
return head;
}
public void insertAfter(node previous,int data)//insert node after given position....
{
if(previous==null)
{
return;
}
node newnode=new node(data);
newnode.next=previous.next;
previous.next=newnode;
}
public node insertAtPosition(node head,int data,int pos)//insert node at given position....
{
int size=length(head);
if(pos<1||pos>size+1){
System.out.println("invalid");
return head;
}
node newnode=new node(data);
if(pos==1)
{
newnode.next=head;
return newnode;
}
else
{
node previous=head;
int count=1;
while(count<pos-1)
{
previous=previous.next;
count++;
}
node current=previous.next;
newnode.next=current;
previous.next=newnode;
return head;
}
}
public node deletFirst(node head)//delete the first node....
{
if(head==null)
{
return head;
}
node temp=head;
head=head.next;
temp.next=null;
return head;
}
public node deleteLast(node head)//delete the last node....
{
if(head==null)
{
return head;
}
node previous=head;
node current=head.next;
while(current.next!=null)
{
current=current.next;
previous=previous.next;
}
previous.next=null;
return head;
}
public node deleteAtPosition(node head,int pos)//delete the node at any position....
{
int size=length(head);
if(pos<1||pos>size+1)
{
System.out.println("invalid");
return head;
}
if(pos==1)
{
node temp=head;
head=head.next;
temp.next=null;
return head;
}
else{
int count=1;
node current=head;
while(count<pos-1)
{
current=current.next;
count++;
}
node temp=current.next;
current=temp.next;
temp.next=null;
return head;
}
}
public boolean search(node head,int searchkey)//serch the element in link list....
{
if(head==null)
{
return false;
}
node current=head;
while(current!=null)
{
if(current.data==searchkey)
return true;
current=current.next;
}
return false;
}

public node reverse(node head)//recursive method to reverse the link list...
{
node previous;
node current;
if(head==null)
{
return head;
}
previous=head;
current=previous.next;
if(current==null)
{
return head;
}
current=reverse(current);
previous.next.next=previous;
previous.next=null;
return current;
}
public node reverser(node head)//iterative method to reverse a link list.....
{
node prev,curr,next;
if(head==null)
{
return head;
}
prev=null;
curr=head;
while(curr!=null)
{
next=curr.next;
curr.next=prev;
prev=curr;
curr=next;
}
return prev;
}
public void sort(node head)//sort the list...
{
node p,q;
if(head==null)
{
return;
}
for(p=head;p.next!=null;p=p.next)
{
for(q=p.next;q!=null;q=q.next)
{
if(p.data>q.data)
{
int temp=p.data;
p.data=q.data;
q.data=temp;
}
}
}
}
public static void main(String args[])
{
node head=new node(10);
node second=new node(8);
node third=new node(1);
node fourth=new node(5);

head.next=second;
second.next=third;
third.next=fourth;
singlelinklist ob=new singlelinklist();
System.out.println("enter choice");
Scanner sc=new Scanner(System.in);
int ch=sc.nextInt();
switch(ch)
{
case 1:
ob.display(head);
System.out.println();
System.out.print("length of link list is--> "+ob.length(head));
System.out.println();
System.out.println("the length of link list is--->"+ob.getlength(head));
break;
case 2:
node newhead=ob.insertAtBeginning(head,15);
ob.display(newhead);
System.out.println();
System.out.print("After inserting the node at beginning the length of link list is--> "+ob.length(newhead));
System.out.println();
break;
case 3:
node newhead1=ob.insertAtEnd(head,20);
ob.display(newhead1);
System.out.println();
System.out.print("After inserting the node at end the length of link list is--> "+ob.length(newhead1));
System.out.println();
break;
case 4:
ob.insertAfter(second,100);
ob.display(head);
System.out.println();
System.out.print("After inserting node the length of link list is--> "+ob.length(head));
break;
case 5:
node newhead2=ob.insertAtPosition(head,50,4);
ob.display(newhead2);
System.out.println();
System.out.print("the length of link list is--->"+ob.length(newhead2));
break;
case 6:
node first=ob.deletFirst(head);
ob.display(first);
System.out.println();
System.out.print("the lengthof link list is--->"+ob.length(first));
break;
case 7:
node last=ob.deleteLast(head);
ob.display(last);
System.out.println();
System.out.print("the lengthof link list is--->"+ob.length(last));
break;
case 8:
node position=ob.deleteAtPosition(head,1);
ob.display(position);
System.out.println();
System.out.print("the length of link list is--->"+ob.length(position));
break;
case 9:
if(ob.search(head,8))
{
System.out.println("element found");
}
else{
System.out.println("element not found");
}
break;
case 10:
node head1=ob.reverse(head);
ob.display(head1);
System.out.println();
System.out.println("the length of link list is--->"+ob.getlength(head1));
break;
case 11:
node head2=ob.reverse(head);
ob.display(head2);
System.out.println();
System.out.println("the length of link list is--->"+ob.getlength(head2));
break;
case 12:
ob.sort(head);
ob.display(head);
break;
}
}
}