Data Structures and Algorithms - Old Questions
8. Write an algorithm and C function to delete node in singly link list.
An algorithm to deleting the first node of the singly linked list:
let *head be the pointer to first node in the current list
1. Create a new node using malloc function
NewNode=(NodeType*)malloc(sizeof(NodeType));
2. Assign data to the info field of new node
NewNode->info=newItem;
3. Set next of new node to head
NewNode->next=head;
4. Set the head pointer to the new node
head=NewNode;
5. End
C function:
void deleteBeg()
{
NodeType *temp;
if(head==NULL)
{
printf(“Empty list”);
exit(1).
}
else
{
temp=head;
printf(“Deleted item is %d” , head->info);
head=head->next;
free(temp);
}
}
An algorithm to deleting the last node of the singly linked list:
let *head be the pointer to first node in the current list
1. If(head==NULL) then //if list is empty
print “Void deletion” and exit
2. else if(head->next==NULL) then //if list has only one node
Set temp=head;
print deleted item as,
printf(“%d” ,head->info);
head=NULL;
free(temp);
3. else
set temp=head;
while(temp->next->next!=NULL)
set temp=temp->next;
End of while
free(temp->next);
Set temp->next=NULL;
4. End
C Function:
void deleteEnd()
{
NodeType *temp;
if(head==NULL)
{
printf(“Empty list”);
return;
}
else if(head->next==NULL)
{
temp=head;
head=NULL;
printf(“Deleted item is %d”, temp->info);
free(temp);
}
else
{
temp=head;
while(temp->next->next!=NULL)
{
temp=temp->next;
}
printf(“deleted item is %d'” , temp->next->info):
free(temp->next);
temp->next=NULL;
}
}