
264 Data Structures Using C
6.5 THE CONCEPT OF DUMMY NODES
The linked list and its variants, discussed above, have a major drawback. Every algorithm has to take care
of special cases. For instance, besides a normal operation, an algorithm has to make sure that it works for
the following exceptional or boundary cases:
(1) the empty list
(2) on the head element of the list
(3) on the last element of the list
The above situation occurs when a node in a linked list has no predecessor or a successor. For
example, the first node in a linked list has no predecessor and, therefore, insertion or deletion at the end
requires a special case. Similarly ...