Basic Structure

In this lab you will implement a linked list to practice using dynamic memory. However, you will only implement a small subset of the functions that a full linked list would have – enough to implement what is known as a queue. A queue only supports adding new items to the end of the list (the tail), and extracting items in order from the start of the list (the head).

For an introduction to linked lists, see Chapter 17 of the textbook or this tutorial from Carnegie Mellon University.

Your assignment is to finish implementing three of the member functions of the class List: AddToEnd(), RemoveFromStart(), and Size().

The List class implements a linked list of integers. It consists of an object of the class List, which has a pointer to the first Node. Each Node in turn has a pointer to the next Node in the list. There is a dummy Node, that is always present as the first item in the list, i.e., the List object's m_head points to a dummy Node. This node contains no real data (the m_data field is just set to 0), and is not considered to be an element of the list. It is there because it makes the implementation much easier: you can count on even an empty queue having at least one Node.