This part of the assignment is an exercise in implementing the list ADT using a doubly-linked list. You will need to write a template structure to represent a list node, and a template class to represent the list. The setup is essentially similar to Assignment 7 all of the code will be placed in a single header file (List.h), the overloaded stream insertion operator will need to be forward declared, etc. A driver program is available to test your implementation: /home/turing/t90kjm1/CS241/Code/Spring2018/Honors10/assign10.cpp

The driver program contains code to test all three parts of the assignment. During your development process, simply comment out any code that references classes or methods you have not written yet.

Program struct Node Data members This template structure should have three data members: a member of the template parameter type to store a data item to be inserted into the list, a pointer to the previous Node in the list, and a pointer to the next Node in the list.

Methods Constructor The structure should have a constructor that can be used to initialize the data members of the list node.

class List Data members This class should have three data members. The first should be a pointer to a Node which will point to the front node in the list. The second should be a pointer to a Node which will point to the back node in the list. The third should be a size_t or unsigned integer that will be used to store the list size, the number of items currently stored in the list.

Methods and associated functions The List class should implement the following methods and functions. (Most of these are very similar to methods from the Queue class on Assignment 7.) template List::List() The class should have a default constructor that sets both pointer data members of the list to nullptr and the list size to 0

. template List::~List() The class should have a destructor. The destructor can simply call the clear() method.

template List::List(const List& other) The class should have a proper copy constructor. If you choose to make a copy of the linked list by using the push_back() method, make sure you set both the list front and list back pointers for the new list to nullptr and the list size to 0 before you attempt to insert any nodes into it.

template List& List::operator=(const List& other) The assignment operator should be properly overloaded.

template void List::clear() This method should properly set the list back to the empty state, deleting all of the nodes in the list.

template size_t List::size() const Returns the list size.

template bool List::empty() const Returns true if the list size is 0; otherwise, returns false.

template const T& List::front() const This method should return the data of the front node in the list. You may assume that it will not be called if the list is empty. template T& List::front() This method should return the data of the front node in the list. You may assume that it will not be called if the list is empty.

template const T& List::back() const This method should return the data of the back node in the list. You may assume that it will not be called if the list is empty.

template T& List::back() This method should return the data of the back node in the list. You may assume that it will not be called if the list is empty.

template void List::push_front(const T& val) This method should insert an item at the front of the list. See the Implementation Hints below for help on writing this method.

template void List::push_back(const T& val) This method should insert an item at the back of the list. See the Implementation Hints below for help on writing this method.

template void List::pop_front() This method should remove the item at the front of the list. You may assume it will not be called if the list is empty. See the Implementation Hints below for help on writing this method.

template void List::pop_back() This method should remove the item at the back of the list. You may assume it will not be called if the list is empty. See the Implementation Hints below for help on writing this method.

template bool List::operator==(const List& rhs) const The equality operator should be overloaded to allow the comparison of two List objects. This method returns true if 1) the two lists contain the same number of nodes, and 2) if each data element of the left list is equal to the corresponding element of the right list. Otherwise the method returns false. (This is similar in principal to the overloaded equality operator you wrote for Assignment 5.)

template bool List::operator<(const List& rhs) const The less than operator should be overloaded to allow the comparison of two List objects. This method will perform a lexicographical comparison of the two lists. Lexicographical comparison means dictionary (element-by-element) ordering. That is, list1 is less than list2 if the first data element of list1 is less than the first data element of list2, and greater if the first data element of list1 is greater than the first data element of list2. If the two first data elements are equivalent then the method compares the two second data elements, and so on. The first list is also considered to be less than the second if every data element in the first list is equal to the corresponding data element in the second but the second list contains more data elements.

template std::ostream& operator<<(std::ostream& lhs, const List& rhs) The output operator should be overloaded so that an entire List object can be sent to the standard output. As usual, this function will need to be a friend rather than a method.

Implementation Hints For some hints on implementing push_back(), push_front(), pop_back(), and pop_front(), see the Notes on Doubly-Linked List Insertion and Deletion on the course web site.

Other Notes In the interest of saving time, you do not need to write any documentation for any of the parts of this assignment (unless you want to). A makefile is required as usual. You do not need to submit the three parts of the assignment separately, just your finished version.