The linked list will consist of nodes. The node class itself will be abstract; we'll use three subtypes to accomplish the work. There will be a head node whose job is to manage the head of the list, a tail node (guess what its job is!), and zero or more internal nodes. The internal nodes will keep track of the actual data to be held in the list.
Note that the data and the list are quite distinct. You can, in theory, save any type of data you like in a list. It isn't the data that is linked together; it is the node that holds the data that is linked.
The program doesn't actually know about the nodes; it only works with the list. The list, however, does little work; it simply delegates to the nodes.
Listing 19.1 shows the code; ...