Page 121 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES
P. 121
Fundamentals of Data Structures
Notes Deleting the Last Node in Singly Linked List
In this case, last node is removed from the list. This operation is a bit trickier than removing the
first node, because algorithm should find a node, which is previous to the tail first. It can be done
in three steps.
The example given below shows the steps for deleting the last node in Singly Linked List:
1. Traverse the list and while traversing maintain the previous node address also.
Did u know? By the time we reach the end of list, we will have two pointers one pointing
to the tail node and other pointing to the node before tail node.
Figure 8.8: Traverse the List
2. Update previous nodes with NULL.
Figure 8.9: Update Previous Nodes
Source: http://www.csie.ntu.edu.tw/~hsinmu/courses/lib/exe/fetch.php?media=dsa_12spring:
dsame_chap3.pdf
3. Dispose the tail node.
Figure 8.10: Disposing the Tail Node
Source: http://www.csie.ntu.edu.tw/~hsinmu/courses/lib/exe/fetch.php?media=dsa_12spring:
dsame_chap3.pdf
Deleting an Intermediate Node in Singly Linked List
In this case, node to be removed is always located between two nodes. Head and tail links are
not updated in this case. Such a removal can be done in two steps.
114 LOVELY PROFESSIONAL UNIVERSITY
