import java.util.Scanner;
class Node{
protected int data;
protected Node link;
public Node(){
link = null;
data = 0;
}
public Node(int d, Node n){
data = d;
link = n;
}
public void setLink(Node n){
link = n;
}
public void setData(int d){
data = d;
}
public Node getLink(){
return link;
}
public int getData(){
return data;
}
}
class LinkedList{
protected Node start;
protected Node end;
public int size;
public LinkedList(){
start = null;
end = null;
size = 0;
}
public boolean isEmpty(){
return start == null;
}
public int getSize(){
return size;
}
public void insertAtStart(int val){
Node nptr = new Node(val, null);
size++;
if(start == null){
start = nptr;
end = start;
}else{
nptr.setLink(start);
start = nptr;
}
}
public void insertAtEnd(int val){
Node nptr = new Node(val, null);
size++;
if(start == null){
start = nptr;
end = start;
}else{
end.setLink(nptr);
end = nptr;
}
}
public void insertAtPos(int val, int pos){
Node nptr = new Node(val, null);
Node ptr = start;
pos = pos - 1;
for(int i = 1; i< size; i++){
if(i == pos){
Node tmp = ptr.getLink();
ptr.setLink(nptr);
nptr.setLink(tmp);
break;
}
ptr = ptr.getLink():
}
size++;
}
public void deleteAtPos(int pos){
if(pos == 1){
start = start.getLink();
size--;
return;
}
if(pos == size){
Node s = start;
Node t = start;
while(s != end){
t = s;
s = s.getLink();
}
end = t;
end.setLink(null);
size--;
return;
}
Node ptr = start;
pos = pos - 1;
for(int i = 1; i < size -1; i++){
if(i == pos){
Node tmp = ptr.getLink();
tmp = tmp.getLink();
ptr.setLink(tmp);
break;
}
ptr = ptr.getLink();
}
size--;
}
public void display(){
System.out.print("\nSingly linked list = ");
if(size == 0){
System.out.print("empty\n");
return;
}
if(start.getLink() == null){
System.out.println(start.getData());
return;
}
Node ptr = start;
System.out.print(start.getData() + "->");
ptr = start.getLink();
while(ptr.getLink() != null){
System.out.print(ptr.getData() + "->");
ptr = ptr.getLink();
}
System.out.print(ptr.getData() + "\n");
}
}
public class SinglyLinkedDriver{
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
LinkedList list = new LinkedList();
System.out.println("Singly linked list test: \n");
char ch;
do{
System.out.println("\nSingly linked list operations\n");
System.out.println("1. insert at the beginning");
System.out.println("2. insert at the end");
System.out.println("3. insert at position");
System.out.println("4. delete at position");
System.out.println("5. check empty");
System.out.println("6. get size");
int choice = scan.nextInt();
switch(choice){
case 1:
System.out.println("Enter integer element to insert");
list.insertAtStart(scan.nextInt());
break;
case 2:
System.out.println("Enter integer element to insert");
list.insertAtEnd(scan.nextInt());
break;
case 3:
System.out.println("Enter integer element to insert");
int num = scan.nextInt();
System.out.println("Enter position");
int pos = scan.nextInt();
if(pos <= 1 || pos > list.getSize()){
System.out.println("Invalid position\n");
}else{
list.insertAtPos(num, pos);
}
break;
case 4:
System.out.println("Enter position");
int p = scan.nextInt();
if(p < 1 || p > list.getSize()){
System.out.println("Invalid position\n");
}else{
list.deleteAtPos(p);
}
break;
case 5:
System.out.println("Empty status = "+ list.isEmpty());
break;
case 6:
System.out.println("Size = "+ list.getSize()+" \n");
break;
default:
System.out.println("Wrong entry. \n");
break;
}
list.display();
System.out.println("\nDo you want to continue (Type y or n) \n");
ch = scan.next().charAt(0);
}while(ch == 'Y' || ch == 'y');
}
}