When implementing a linked list or a doubly linked list, you considered several cases; adding to the empty list, adding or removing the first node, adding or removing the last node, adding or removing a middle node. a header node is a node that comes before all other nodes in the list. A trailer node is a node that comes after all of the nodes in the list. If a list has a header node and a trailer node, most of these cases are eliminated. We are left only with adding and deleting from the middle of the list. The header and trailer nodes are not included when printing the list contents or searching the list. They can be considered "dummy" nodes.

The constructor of a linked list implementation that has a header and trailer node would create a list similar to the one illustrated in Figure 29-6. For example, if the list is designed to hold values in increasing order, the value in the header node will be a value smaller that all values in the list and the value in the trailer node will be a value larger than all values in the list.

Figure 29-6

You may see these terms used on the AP Exam but, when implementing linked lists on the free-response questions on the AP Exam, do not use header and trailer nodes unless explicitly told to do so.