Encoding the IntList Class

Before we can implement the IntList class, we need to have a clear idea of how we're going to represent the list in memory and how, in general, that representation will behave. This specification is called the encoding of the data structure (also known as the representation).

A very concise description of the encoding is

A singly linked list to store the integer elements, with a list header that keeps track of the front and back of the list, as well as the size of the list.

The IntList Encoding in Depth

The key idea behind a linked list is chaining together a sequence of small objects, called nodes, where each node contains one element of the list and a pointer to the next node in the list. In our class, each node is defined as follows:

    struct Node {
        int value_  = 0;        // Value of the list element
        Node* next_ = nullptr;  // Next list node
    };

You can allocate a new node on the heap using

Node* new_node = new Node{value};

to make the last node in the list, or

Node* new_node = new Node{value, next_node};

to make a node that attaches to an existing node next_node.

Nodes by themselves don't know how to do anything (they don't have any member functions; they just hold data). Nodes are managed by an IntList object, which does all necessary bookkeeping and provides the operations that users of the class can call.

The IntList object will contain pointers to the first and last data element (if any), and a count of the object’s size. Tracking the last element adds a little bit of complexity, but it allows us to implement push_back in constant time because we always know exactly where the last element is.

More concretely, our IntList class has the following private data members:

    // Data members
    Node* front_ = nullptr;  // Current head of list
    Node* back_  = nullptr;  // Current tail of list
    size_t size_ = 0;        // Current size of list
                // ^-------- by specifying initializations here, we can avoid
                //           needing to specify a member-initialzation list.

The diagram below shows an empty IntList,

and this diagram shows an IntList with three elements (42, 24, and 36).

Your Task, Part 1

In intlist.hpp, at the bottom of the class definition, in the private: section, you'll find we've already put the Node struct definition, and the three data members front_, back_, and size_, so that part is already done.

Your Task, Part 2

First, read this help page:

• The Joy of Assertions

Then, in intlist.hpp, add a new private member-function declaration:

    void check_invariants() const;

Then, in intlist.cpp, add a new private member-function definition:

void IntList::check_invariants() const {
    if (size_ == 0) {
        assert(XXXSOMETHNGXXX); // fill this in
        // more asserts as needed
    } else if (size_ == 1) {
        assert(XXXSOMETHNGXXX); // fill this in
        // more asserts as needed
    } else { // size_ > 1
        assert(XXXSOMETHNGXXX); // fill this in
        // more asserts as needed
    }
}

Use the description of the invariants above to fill in the assert statements. Although you can use && in a single assert statement, it's often clearer to use multiple assert statements (if it fails, you'll know exactly which condition failed).

(When logged in, completion status appears here.)