One deletion operation consists in deleting a node at the beginning of the list and returning the value stored in it. This operation is implemented by a member function delete From Head() given below. In this operation, the information from the first node is temporarily stored in local variable and then head is reset so that what was the second node becomes the first node. In this way, the former first node can be deleted in constant O(1) time.
Deleting the first node, from a linked list pointed by ‘head’ can be done is O(i) time head = head →next
Deleting a note that follows a node with address P can also be done in O(i) time
But a node with address P cannot be deleted in O(i) time. It takes linear time.
//Delete the first node
delete From Head(struct node *q,int num)
{
struct node *temp;
temp=*q;
*q=templink;
free(temp);
}
We can use this algorithm to delete every node by calling it recursively. The best case is when the head node is to be deleted, which takes O(1) time to accomplish. The worst case is when the last node needs to be deleted because in that case it will take O(n) performance.
