Memory Based Linked List Assignment
For this assignment you will be writing the class shown below that implements a list ADT using a linked list. You need to implement all the memory handling functions. As usual, move operations will only be significant for performance.
template<typename T>
class LinkedList {
struct Node {
// TODO
};
// TODO - Your data
public:
typedef T value_type;
class iterator {
// TODO - Data
public:
// TODO - Constructors
T &operator*() { TODO }
bool operator==(const iterator &i) const { TODO }
bool operator!=(const iterator &i) const { TODO }
iterator &operator=(const iterator &i) { TODO }
iterator &operator++() { TODO }
iterator &operator--() { TODO }
iterator operator++(int) {
// TODO
}
iterator operator--(int) {
// TODO
}
friend class const_iterator;
friend class LinkedList;
};
class const_iterator {
// TODO - Data
public:
// TODO - Constructors
// TODO - Include a constructor that converts from a regular iterator.
const T &operator*() { TODO }
bool operator==(const const_iterator &i) const { TODO }
bool operator!=(const const_iterator &i) const { TODO }
const_iterator &operator=(const const_iterator &i) { TODO }
const_iterator &operator++() { TODO }
const_iterator &operator--() { TODO }
const_iterator operator++(int) {
// TODO
}
const_iterator operator--(int) {
// TODO
}
};
// General Methods
// TODO - Constructors
LinkedList &operator=(const LinkedList &al) {
// TODO
}
~LinkedList() {
// TODO
}
void push_back(const T &t); // add to the end.
void pop_back(); // remove last element.
int size() const;
void clear();
iterator insert(iterator position,const T &t); // insert this element before the given index.
const T &operator[](int index) const; // get the element at index.
T &operator[](int index); // get the element at index.
iterator erase(iterator position); // remove the item at the given index.
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
const_iterator cbegin() const;
const_iterator cend() const;
};
For the nested types, you can declare value_type with a typedef or a using statement. For the others I recommend a nested class with the proper name. If you do that, then the begin method has the following signature when you write it below the class declaration.
typename LinkedList<T>::iterator LinkedList<T>::begin()
Your iterators need to satisfy the requirements for a bi-directional iterator in C++ (http://www.cplusplus.com/reference/iterator/BidirectionalIterator/).
If you write the methods below the classes you will need to specify them with both scopes for the outer class and the nested class. Since these should all be rather short you can write them in the class declaration as inlining is probably appropriate. Note that the versions of ++ and -- that take an int argument are the postfix version. The ones with no argument are prefix.
Why should you put begin and end methods in your class and have iterators? Try using a ranged for loop with your class. I will in my testing.
For testing, you should put your code in a file called LinkedList.h.
Test Rubric:
Basic tests of all methods (10 points)
Large tests (1000+ items) (5 points)
Tests with multiple types, including non-primitives (5 points)