LINKED LIST IN JAVA (IMPLEMENTATION WITH INSERTION,DELETION AND UPDATION IN START, END AND MIDDLE)

 import java.util.Scanner;

class NodeImplemetation{

Node head;

int count=0;

int count2=0;

public void toAdd(int data){

Node newNode=new Node(data);

Node temp=head;

if(isEmpty()){

System.out.println("Initially List is empty. ");

head=newNode;

return;

}

while(temp.next!=null){

temp=temp.next;

}

temp.next=newNode;

}

public void toAddMid(int data,int count){

Node temp=head;

int index=0;

while(index<count/2){

temp=temp.next;

index++;

}

Node old=temp.next;

Node newNodeMid= new Node(data);

temp.next=newNodeMid;

newNodeMid.next=old;

}

public void toInsertStart(int data){

Node newStart=new Node(data);

Node temp=head;

newStart.next=temp;

head=newStart;

}

public int countTotal(){

Node temp=head;

while(temp!=null){

//System.out.println("Data is : "+temp.data);

temp=temp.next;

count++;

}

return count;

}

public int countTotal2(){

Node temp=head;

while(temp!=null){

//System.out.println("Data is : "+temp.data);

temp=temp.next;

count2++;

}

return count2;

}

public void toDel(){

if(isEmpty()){

System.out.println("Nothing can be deleted:");

return;

}

else{

Node temp = head;

while((temp.next).next!=null){

temp=temp.next;

}

temp.next=null;

}

}

public void toDelMid(int counter){

if(isEmpty()){

System.out.println("Nothing can be deleted:");

return;

}

else{

Node temp=head;

int index=0;

while(index<(counter/2)){

temp=temp.next;

index++;

}

Node old=temp.next.next;

temp.next=old;

}

}

public void toDelStart(int old_val){

Node temp=head;

while((temp.next).data!=old_val){

temp=temp.next;

}

Node second=temp.next.next;

temp.next.next=null;

temp.next=second;

}

public void update(int val){

Node temp=head;

while(temp.next!=null){

temp=temp.next;

}

temp.data=val;

}

public void toUpdMid(int counter,int valup){

Node temp=head;

int index=0;

while(index<(counter/2)-1){

temp=temp.next;

index++;

}

temp.data=valup;

}

public void toUpdStart(int old,int modify){

Node temp=head;

while(temp.data!=old){

temp=temp.next;

}

temp.data=modify;

}

boolean isEmpty(){

if(head==null){

return true;

}

else

return false;

}

void print(){

Node temp=head;

while(temp!=null){

System.out.println("Data is : "+temp.data);

temp=temp.next;

}

//System.out.println("Total Nodes: "+count);

}

static class Node{

int data;

Node next;

public Node(int data){

this.data=data;

next=null;

}

}

}

class LinkedList2{

public static void main(String arg[]){

NodeImplemetation obj=new NodeImplemetation();

Scanner sc=new Scanner(System.in);

int count1=0;

//TIME COMPLEXITY O(1) INSERTION LAST

System.out.println("Insertion of elements at last: ");

for(int i=0;i<11;i++){

obj.toAdd(i);

}

System.out.println("Printing of all nodes: ");

obj.print();

System.out.println("-------------------------------------------------------------------");

//TIME COMPLEXITY O(1) DELETION LAST

System.out.println("Deletion of last node: ");

obj.toDel();

System.out.println("List after deletion from end: ");

obj.print();

System.out.println("-------------------------------------------------------------------");

//TIME COMPLEXITY O(1) UPDATION LAST

System.out.println("Enter the new value for the last node: ");

int val=sc.nextInt();

obj.update(val);

obj.print();

count1=obj.countTotal();

System.out.println("Total Nodes Are: "+count1);

System.out.println("-------------------------------------------------------------------");

//TIME COMPLEXITY O(N) HALF LIST TRAVERSAL INSERTION MIDDLE

System.out.println("Adding the value in middle of list: ");

/*

will add elements in linked list in middle in reverse order

for(int m=11;m<22;m++){

obj.toAddMid(m,count1);

}

obj.print();*/

int j=0;

for(int m=11;m<22;m++){

obj.toAddMid(m,count1+j);

j+=2;

//here value of count1 will be fixed

//like in this case it is count1=9;

//here we increase by factor 1 then 

//in toaddMid function count1/2 will ve same for two values

//hence we will get different order of function as 

//for 10/2 it will be 5 and 11/2 it will be 5 also

//but it we increase by 2 then order will be preserved

//9/2 will be 4 and 11/2 will be 5 as difference will be of 2

//between values of count1.

//if count1 is even then also eerything will be same 

//now it will be like 10/2 ie 5 and 12/2 ie 6

}

obj.print();

System.out.println("-------------------------------------------------------------------");

/*int j=0;

for(int m=11;m<22;m++){

obj.toAddMid(m,count1+j);

j+=2;

}

obj.print();

output:

0 1 2 3 4 11 13 15 17 19 21 20 18 16 14 12 5 6 7 10 

(if 10 is the updated value of last element done above)

*/

System.out.print("Total Nodes in the network: ");

int count2=obj.countTotal2();

System.out.println(count2);

System.out.println("-------------------------------------------------------------------");

//TIME COMPLEXITY O(N) IF MULTIPLE VALUES INSERTED IN MIDDLE NEEDS TO BE UPDATED UPDATION MIDDLE

System.out.println("Now Updation of the values inserted now :");

int k1=0;

for(int i=30;i<41;i++){

obj.toUpdMid(count2+k1,i);

k1++;

}

obj.print();

System.out.println("-------------------------------------------------------------------");

//TIME COMPLEXITY O(N) HALF LIST TRAVERSAL DELETION MIDDLE

System.out.println("Deletion of the nodes from middle: ");

//All nodes inserted now ie to the right of central node are deleted

//it depends on the value of k 

//if you increase by 1 then right nodes will be deleted

//if you increase by 2 it means size will decrease and elements

//on the left from the central element will be deleted also.

int k=0;

for(int i=0;i<10;i++){

obj.toDelMid(count2-k);

k++;

}

obj.print();

System.out.println("-------------------------------------------------------------------");

//TIME COMPLEXITY O(1) CHANGE IN HEAD NODE INSERTION START

System.out.println("Now for insertion in the start: ");

for(int i=100;i<110;i++){

obj.toInsertStart(i);

}

obj.print();

System.out.println("-------------------------------------------------------------------");

//TIME COMPLEXITY O(1) IF FIRST NODE DATA NEEDS TO BE CHANGED INSERTION START

System.out.println("Updation in the start: ");

System.out.println("Enter the node data you want to update :");

int oldat=sc.nextInt();

System.out.println("Enter new value of data: ");

int newval=sc.nextInt();

obj.toUpdStart(oldat,newval);

obj.print();

//TIME COMPLEXITY O(1) FIRST NODE DELETE DELETION START

System.out.println("Deletion from start: ");

System.out.println("Enter the node data you want to delete :");

int oldat1=sc.nextInt();

obj.toDelStart(oldat1);

obj.print();

System.out.println("-------------------------------------------------------------------");

}

}