Consider a singly link list with a head pointer. i) Write an algorithm that rece
ID: 3832427 • Letter: C
Question
Consider a singly link list with a head pointer. i) Write an algorithm that receives an integer, n, as input, and deletes the n^th node of the link list. The signature of the function looks like the following: void delete Index (int n); ii) What's the run time of your algorithm in terms of asymptotic notations. Consider a singly link list with both the head and tail pointers. i) Write an algorithm that inserts a new node with a given value at the tail of the list. void insertTail(int value); ii) What's the run time of your algorithm in terms of asymptotic notations.Explanation / Answer
since the programming language is not defined so writing the code in java
and assuming the defination of the node class for the linked list as folow
class Node{
int data;
Node next;
Node(int d){
this.data = d;
next = null;
}
}
1) void deleteIndex(int n){
if(head == null)
return;
Node temp = head;
Node prev = null;
while(temp!=null && n>=0){
n--;
prev = temp;
temp = temp.next;
}
if(temp==null)
return;
prev = temp.next;
}
complexity of the code is o(n) where n is the user defined value or the index of the list to be deleted
2)void insertTail(int value){
if(head == null){
head = new Node(value);
return;
}
Node temp = head;
while(temp.next!=null)
{
temp = temp.next;
}
Node d = new Node(value);
temp.next = d;
}
complexity is o(n) where n is the size of the list