a)
Deletion – deletion means removing element from the list.
There are three cases of deletion –
I.
Delete a node from beginning
II.
Delete a
node from middle
III.
Delete a node from end
I.
Delete a node from beginning – delete a node from beginning mean removing a node
from beginning of the list.
Algorithm of delete a node from beginning – We can use the following steps to delete a node from beginning of
the single linked list...
·Step 1: Check whether list is Empty (head== NULL)
·Step 2: If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
·Step 3: If it is Not Empty then, define a Node pointer 'ptr' and initialize
with head.
·Step 4: Check whether list is having only one node (ptr → next == NULL)
·Step5: if
it is TRUE then set head = NULL and delete temp (setting EMPTY list condition).
·Step 6: If it is FALSE then set head = ptr → next, and delete ptr.
II.
Delete a node
from middle of list (given node) - We can use the following steps to delete a specific node
from the single linked list...
·Step 1: Check whether list is Empty (head== NULL)
·Step 2: If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
·Step 3: If it is Not Empty then, define two Node pointers 'ptr' and 'preptr' and initialize 'ptr' with head.
·Step 4: Keep moving the ptr until it reaches to the exact node to be
deleted or to the last node. And every time set 'preptr = ptr' before moving
the 'ptr' to
its next node.
·Step 5: If it is reached to the last node then display 'Given node not found in the list! Deletion
not possible!!!'. And terminate the function.
·Step 6: If it is reached to the exact node which we want to delete,
then check whether list is having only one node or not
·Step 7: If list has only one node and that is the node to be
deleted, then set head = NULL and delete ptr (free (ptr)).
·Step 8: If list contains multiple nodes, then check whether ptr is the first node
in the list (ptr== head).
·Step 9: If ptr is
the first node then move the head to the next node (head = head → next) and delete ptr.
·Step 10: If ptr is
not first node then check whether it is last node in the list (ptr → next == NULL).
·Step 11: If ptr is
last node then set preptr → next = NULL and
delete ptr (free(ptr)).
·Step 12: If ptr is
not first node and not last node then set preptr → next = ptr
→ next and delete ptr (free (ptr)).
III.
Delete a node from middle (after) - We can use the following steps to delete
a specific node from the single linked list...
·Step 1: Check whether list is Empty (head== NULL)
·Step 2: If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
·Step 3: If it is Not Empty then, define two Node pointers 'preptr' and 'ptr' and initialize 'preptr' with head.
·Step 4: Keep moving the preptr until it
reaches to the exact node to be deleted or to the last node. And every time set
'preptr = ptr'
before moving the 'preptr' to its next node.
·Step 5: then set preptr
→ next = ptr
→ next and delete ptr (free (ptr)).
IV.
Delete a node
from end of list - We
can use the following steps to delete a node from end of the single linked
list...
·
Step 1: Check whether list is Empty (head== NULL)
·
Step 2: If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
·
Step 3: If it is Not Empty then, define two Node pointers 'ptr' and 'preptr' and initialize
'ptr'
with head.
·
Step 4: Check whether list has only one Node (ptr → next == NULL)
·
Step 5: If it is TRUE. Then, set head = NULL and delete ptr. And terminate the function. (Setting Empty list condition)
·
Step 6: If it is FALSE. Then, set 'preptr = ptr' and move ptr to its next node.
Repeat the same until it reaches to the last node in the list. (until ptr→ next == NULL)
·
Step 7: Finally, Set preptr → next = NULL and
delete ptr.