Sams Teach Yourself C++ in 21 Days

In this appendix, you examine a linked list in detail as a case study of how you create

complex structures and, more importantly, how you use them.

The Component Parts of Your Linked List

The linked lists you create will consist of nodes. The node class itself will be abstract;

you’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 inter-

nal 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 holdsthe data.

The driver program doesn’t know about the nodes; it works with the list. The list, how-

ever, does little work; it simply delegates to the nodes.

Listing E.1 shows the code; you’ll examine it in excruciating detail in the rest of this

appendix.

876 Appendix E

FIGUREE.1

Linked lists.

Data

Singly

linked

Doubly

linked

Trees

Data

Data Data Data Data

Data Data Data

fl

fl

fl fl fl fl fl fl fl

fl

Data

Data Data

fl fl

Data Data

Data

Data

33 0672327112_app_e.qxd 11/19/04 12:30 PM Page 876