Previous Section
 < Free Open Study > 
Next Section


6.3 Linked Lists with Headers and Trailers

In writing the insertion and deletion algorithms for all implementations of linked lists, we see that special cases arise when we are dealing with the first node or the last node. One way to simplify these algorithms is to ensure that we never insert or delete items at the ends of the list.

How can this goal be accomplished? Recall that the elements in a sorted linked list are arranged according to the value in some key-for example, numerically by identification number or alphabetically by name. If we can determine the range of possible values for the key, it is often a simple matter to set up dummy nodes with values outside of this range. We can place a header node, containing a value smaller than any possible list element key, at the beginning of the list. We can place a trailer node, containing a value larger than any legitimate element key, at the end of the list.

Header node A placeholder node at the beginning of a list; used to simplify list processing

Trailer node A placeholder node at the end of a list; used to simplify list processing

The header and the trailer are regular nodes of the same type as the real data nodes in the list. They have a different purpose, however; instead of storing list data, they act as placeholders.

If a list of students is sorted by last name, for example, we might assume that there are no students named "AAAAAAAAAA" or "ZZZZZZZZZZ." We could therefore initialize our linked list to contain header and trailer nodes with these values as the keys. See Figure 6.11. How can we write a general list algorithm if we must know the minimum and maximum key values? We can use a parameterized class constructor and let the user pass as parameters elements containing the dummy keys. Alternatively, we can just leave the keys undefined and start the search with the second node in the list.

Click To expand
Figure 6.11: An "empty" list with a header and a trailer


Previous Section
 < Free Open Study > 
Next Section
Converted from CHM to HTML with chm2web Pro 2.85 (unicode)