Assignment Task
This first exercise is worth 10 points out of the 20 total points for programming assignment 1. In this exercise you will implement a toy version of a std::list, which is a doubly linked list. Just like in the standard library, the type of element in the list can be passed as a template parameter and we will test your solution instantiating the template type with int, std::string, and MyInteger the class we made in tutorial. You are not allowed to use any of the standard library sequence containers std::list, std::forward_list, std::vector, std::deque in this exercise.
Our toy version of std::list will be called MyList. As in the ForwardList Challenge from the Week 4 tutorial, MyList contains a Node class, which now has both next and prev pointers to implement a doubly linked list.
There are many ways to design a doubly linked list. We give you full freedom to make these architectural decisions, and you are free (and indeed will need) to add member variables and member functions to the MyList scaffold in the construction of your solution. In part 2 of this programming assignment you will add iterator functionality to your linked list. You may wish to read the project description of part 2 before you get started as this might affect the architectural decisions you make.
You can also look at the Week 4 tutorial that featured a singly linked list to see how to traverse a linked list and print out the values at the nodes, which may be helpful in your debugging.
We now go through the member functions you have to implement.
Basic Constructors:
// Default Constructor
// Do some setup of your list architecture?
MyList();
// Construct a list from an initializer list
// This lets us create a list with the ints 1,2,3,4 by saying
// MyList li {1,2,3,4};
MyList(std::initializer_list vals);
The Big Three
// Copy Constructor
MyList(const MyList&);
// Operator=
MyList& operator=(MyList);
// Destructor
// free all memory allocated with new
~MyList();
Front and Back
Member functions to get the first and last element of the list. These functions should work in constant time.
// return the last element by reference
T& back();
// return the last element by const reference
// this one can be used on a const MyDeque
const T& back() const;
// return the first element by reference
T& front();
// return the first element by const reference
// this one can be used on a const MyDeque
const T& front() const;
Add/Remove elements to the front/back
Member functions to add or remove elements from the front or back of the list. These functions should work in constant time.
// add an element to the front of the list
void push_front(T);
// remove the first element
void pop_front();
// add an element to the back of the list
void push_back(T);
// remove the last element
void pop_back();
Functions Related to the Number of Elements
Two functions related to the number of elements in the MyList. These should work in constant time.
// does the list have any elements?
bool empty() const;
// return the number of elements in the list
int size() const;
The Code
There are 4 files on the scaffold, myInteger.hpp, main.cpp, myList.hpp, and myList.cpp. The file myInteger.hpp is included so that we can populate the list with myInteger s. The file main.cpp has some tests to get you started and you are free to modify it as you wish for your own testing.
Your implementation should go in the file myList.cpp. You are free to add additional member variables and functions as needed, and can modify myList.hpp to declare these.
