IntList Specifications

This page describes the interface and encoding for the IntList class you will be developing in this assignment.

Your implementation must support all the elements of the interface, and each element must have the specified complexity.

You may not change the names of anything in the interface, nor may you change the encoding. However, you are free (and encouraged!) to add private helper functions to your class.

The provided code already contains declarations for the interface and encoding.

Interfaces

Interfaces specify the provided operations.

IntList Interface

Your linked-list class must be named IntList and must support the following operations (in the description below, assume list, list1 etc. are IntList objects and \( n, m\ldots \) are the size of the lists):

• A default constructor †
  • Creates an empty list.
  • Requires \( \Theta(1) \) time.
• list1 = list2, the assignment operator. †
  • It destroys the old value of list1 and replaces it with a duplicate of list2.
  • Requires \( \Theta(n+m) \) time.
• A copy constructor
  • Copies all the integer values from an existing list into a new list.
  • Requires \( \Theta(n) \) time.
• A destructor
  • Destroys all the list elements and deallocates their heap memory.
  • Requires \( \Theta(n) \) time.
• list1.swap(list2) †
  • Swaps list1 and list2
  • Requires \( \Theta(1) \) (regardless of the lengths of the lists).
• swap(list1,list2) †
  • Performs the same swap operation as the member function above, but is provided as a symmetric-looking global function rather than a member function.
• list.push_front(v)
  • Pushes v (an int) onto the front of the list.
  • Requires \( \Theta(1) \).
• list.pop_front()
  • Removes and returns a single int from the front of the list.
  • Requires \( \Theta(1) \).
  • It is against the rules for users to call pop_front on an empty list.
• list.push_back(v)
  • Pushes v (an int) onto the back of the list.
  • Requires \( \Theta(1) \) time.
• list.size() †
  • Returns number of elements in the list (as a size_t)
  • Requires \( \Theta(1) \) time.
• list.empty()
  • Returns true if the list is empty.
  • Requires \( \Theta(1) \) time.
• list1 == list2
  • Returns true if the contents of both lists are identical.
  • Requires \( \Theta(1) \) time if the lists are of different lengths.
  • Requires \( \mathrm{O}(n) \) time if the lists are the same length.
    • More specifically, it takes \( \Theta(l) \) time where \( l \) is the length of the prefix of nodes that are equal. (e.g., if lists have different first elements, the algorithm only takes \( \Theta(1) \) time and if the lists are equal, it reqires \( \Theta(n) \) time.)

• list1 != list2. †

  • This trivial function returns !(list1 == list2) using the above function.

• Two public types, iterator and const_iterator †

  • These types provide the standard operations of a “forward iterator” to allow users to access elements of the list in order.
  • They are accessed outside the class as IntList::iterator and IntList::const_iterator.
  • (See also the discussion of IntList::Iter below.)
• list.begin()
  • Returns an iterator set at the first element in list
    • When the list is empty, a past-the-end iterator is returned.
• Requires \( \Theta(1) \) time to create the iterator.
• list.begin() const
  • Exactly like the above function, but for read-only lists; it returns a const_iterator.
• list.end()
  • Returns a past-the-end iterator
    • It is completely legal to call end() on an empty list.
    • As also noted in the iterator section, it is against the rules for users to call * or ++ on a past-the-end iterator.
  • Requires \( \Theta(1) \) time to create the iterator.
• list.end() const
  • Exactly like the above function, but for read-only lists; it returns a const_iterator.
• list.insert_after(i,v)
  • Inserts v (an int) integer immediately after the position indicated by i (an iterator).
    • It is against the rules to call insert_after with past-the-end iterator. Thus people are not allowed to call insert_after on an empty list.
  • Requires \( \Theta(1) \) time.

† This code has been provided for you; you don’t need to modify it.

IntList's Iterator Interface

Our list provides two user-facing, types, IntList::iterator and IntList::const_iterator. The first of these is an alias for a private class IntList::Iter—in other words, they are two names for the same thing, users write code using IntList::iterator objects, with a lowercase i, and we implement the IntList::Iter class.

The second class, IntList::const_iterator is a type alias for const_adaptor<IntList::Iter>, which is wrapper around our IntList::Iter class, which causes it to behave exactly the same, except that * returns a const int& rather than an int&. You can ignore the details of how this second class is created, but it may be useful to know we have set things up so that an iterator converts to a const_iterator automatically.

Recall that an iterator is a custom class that behaves like a pointer to an int from the perspective of the operations it provides (*, ++, etc.) but is not actually a pointer to an int, it is our own custom class. It might be tempting to say that the iterator “points to” something, but that might be confusing, so we'll adopt the following terminology:

• Internally, the iterator is set at a particular list node, but users cannot access the entire list node, only the int stored in it, so…
• Externally, the user uses the iterator to access a particular int element of the list, and when they use *iter, it refers to that int inside the node.

Our IntList::Iter class provides the following operations, which all take \( \Theta(1) \) time:

• A default constructor. †
  • It is against the rules for users to try to apply *, ++ or == to a default-constructed iterator. They may, however, assign it a new value.
• A copy constructor. †
• An assignment operator. †
• A destructor. †
• iter1 == iter2 and iter1 != iter2, which test to see if two iterators are set to the exact same list element.
  • It is against the rules for users to compare iterators from different lists.
• ++iter advances the iterator to the next list element (or to the past-the-end value).
  • It is against the rules for users to increment a past-the-end iterator, so your code doesn't have to handle this.
• *iter returns an int& (so that the integer at the current position can be modified, if desired).
  • It is against the rules for users to use * on a past-the-end iterator.

When a node in the list is removed by pop_front (or by assignment), any iterators that are set to that node are no longer considered valid (because the list node has been destroyed and they are the iterator equivalent of a dangling pointer!). If an iterator isn't considered valid, it is against the rules to do anything with it other than assign a new (valid) value to it, or destroy it (e.g., by letting the variable go out of scope)—users may not apply * or ++ to it, or even compare it with another iterator. It is up to the user to make sure that they don't use an iterator that isn't valid any more—your implementation doesn't need to do anything special to prevent misuse. But, like code written by other users, your tests must take care to obey all the rules, including not trying to use an iterator that is no longer valid.

The iterator should also provide the necessary information to work with standard-library algorithms, which means the class must include appropriate informational type definitions (see the header file for details). †

† This code has been provided for you; you don’t need to modify it.

Encodings

Recall that an encoding specifies how data is represented.

IntList Encoding

The IntList data structure is a linked list.

The IntList object will be relatively small, and all the data will be in IntList::Node objects on the heap.

The IntList object will contain pointers to the first and last data element (if any), and a count of the object’s size. These extensions let the class provide efficient push_back and size operations.

The diagram below shows an empty IntList:

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

Notice that the list elements are stored in Nodes. A Node is “just data”, it merely aggregates the data together—it isn't a self-contained class with its own operations. No functions in the interface give users direct access to Nodes themselves.

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 initialization list.

We've provided a struct-based definition for the Node type. In accordance with C++ conventions, you may not add any member functions to this struct.

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

IntList::Iter Encoding

The list’s iterator provides a way to access the value stored in an element of a list, and it is encoded as a pointer to a Node.

The diagram below shows iterator that is set at the second node of our list, allowing access to both the value stored in that element, and the next node along in the list.

(When logged in, completion status appears here.)