Collections - Java Software Solutions: Foundations of Program Design - page 626

count:4

list

front

rear

info info info info

next next next next

FIGURE 13.5 A list with front and rear references

Another implementation of a linked list could include a header node for the list
that has a reference to the front of the list and another reference to the rear of the
list. A rear reference makes it easier to add new nodes to the end of the list. The
header node could contain other information, such as a count of the number of
nodes currently in the list. The declaration of the header node would be similar
to the following:

class ListHeader
{
int count;
Node front, rear;
}

Note that the header node is not of the same class as the Node class to which it
refers. Figure 13.5 depicts a linked list that is implemented using a header node.
Still other linked list implementations can be created. For instance, the use of
a header can be combined with a doubly linked list, or the list can be maintained
in sorted order. The implementation should cater to the type of processing that
is required. Some extra effort to maintain a more complex data structure may be
worthwhile if it makes common operations on the structure more efficient.

SELF-REVIEW QUESTIONS (see answers in Appendix N)
SR 13.4 What is a dynamic data structure?
SR 13.5 Describe the steps depicted in Figure 13.2 to insert a node into a list.
What special cases exist?
SR 13.6 Describe the steps depicted in Figure 13.3 to delete a node from a list.
What special cases exist?