#ifndef LIST_H
#define LIST_H
/* List.h
*
* doubly-linked, double-ended list with Iterator interface
*/
#include <iostream>
#include <cassert> //assert
#include <cstddef> //NULL
using namespace std;
template <typename T>
class List {
//OVERVIEW: a doubly-linked, double-ended list with Iterator interface
public:
//EFFECTS: returns true if the list is empty
bool empty() const {
return !first;
}
//EFFECTS: returns the number of elements in this List
//HINT: Traversing a list is really slow. Instead, keep track of the size
// with a private member variable. That's how std::list does it.
int size() const {
return num;
}
//REQUIRES: list is not empty
//EFFECTS: Returns the first element in the list by reference
T & front() {
assert(!empty());
return first->datum;
}
//REQUIRES: list is not empty
//EFFECTS: Returns the last element in the list by reference
T & back() {
assert(!empty());
return last->datum;
}
//EFFECTS: inserts datum into the front of the list
void push_front(const T &datum) {
Node *temp = new Node{};
temp->datum = datum;
temp->next = first;
temp->prev = nullptr;
if (num == 0) {
last = temp;
first = temp;
}
else {
first->prev = temp;
first = temp;
}
if (num == 1) {
last->prev = temp;
}
num += 1;
}
//EFFECTS: inserts datum into the back of the list
void push_back(const T &datum) {
Node *temp = new Node{};
temp->datum = datum;
temp->prev = last;
temp->next = nullptr;
if (num == 0) {
first = temp;
last = temp;
}
else {
last->next = temp;
last = temp;
}
if (num == 1) {
first->next = temp;
}
num += 1;
}
//REQUIRES: list is not empty
//MODIFIES: may invalidate list iterators
//EFFECTS: removes the item at the front of the list
void pop_front() {
assert(!empty());
Node *temp = first;
first = first->next;
if (first) {
first->prev = nullptr;
} else {
last = nullptr;
}
delete temp;
num -= 1;
}
//REQUIRES: list is not empty
//MODIFIES: may invalidate list iterators
//EFFECTS: removes the item at the back of the list
void pop_back() {
assert(!empty());
Node *temp = last;
last = last->prev;
if (last) {
last->next = nullptr;
} else {
first = nullptr;
}
delete temp;
num -= 1;
}
//MODIFIES: may invalidate list iterators
//EFFECTS: removes all items from the list
void clear() {
while (!empty()) {
pop_back();
}
num = 0;
}
// You should add in a default constructor, destructor, copy constructor,
// and overloaded assignment operator, if appropriate. If these operations
// will work correctly without defining these, you can omit them. A user
// of the class must be able to create, copy, assign, and destroy Lists
List(): first(nullptr), last(nullptr), num(0) {}
List(const List &other): first(nullptr), last(nullptr), num(0) {
copy_all(other);
}
List & operator=(const List &rhs) {
if (this != &rhs) {
clear();
copy_all(rhs);
}
return *this;
}
~List() {
clear();
}
private:
//a private type
struct Node {
Node *next;
Node *prev;
T datum;
};
//REQUIRES: list is empty
//EFFECTS: copies all nodes from other to this
void copy_all(const List<T> &other) {
for (Node *ptr = other.first; ptr; ptr = ptr->next) {
push_back(ptr->datum);
}
}
Node *first; // points to first Node in list, or nullptr if list is empty
Node *last; // points to last Node in list, or nullptr if list is empty
int num;
public:
////////////////////////////////////////
class Iterator {
//OVERVIEW: Iterator interface to List
// You should add in a default constructor, destructor, copy constructor,
// and overloaded assignment operator, if appropriate. If these operations
// will work correctly without defining these, you can omit them. A user
// of the class must be able to create, copy, assign, and destroy Iterators.
// Your iterator should implement the following public operators: *,
// ++ (prefix), default constructor, == and !=.
public:
// This operator will be used to test your code. Do not modify it.
// Requires that the current element is dereferenceable.
Iterator(): node_ptr(nullptr) {}
Iterator(const Iterator &other): node_ptr(other.node_ptr) {}
Iterator& operator--() {
assert(node_ptr);
node_ptr = node_ptr->prev;
return *this;
}
T & operator*() const {
assert(node_ptr);
return node_ptr->datum;
}
Iterator &operator++() {
assert(node_ptr);
node_ptr = node_ptr->next;
return *this;
}
bool operator==(Iterator rhs) const {
return node_ptr == rhs.node_ptr;
}
bool operator!=(Iterator rhs) const {
return node_ptr != rhs.node_ptr;
}
private:
Node *node_ptr; //current Iterator position is a List node
// add any additional necessary member variables here
// add any friend declarations here
friend class List;
// construct an Iterator at a specific position
Iterator(Node *p) {
node_ptr = p;
}
};//List::Iterator
////////////////////////////////////////
// return an Iterator pointing to the first element
Iterator begin() const {
return Iterator(first);
}
// return an Iterator pointing to "past the end"
Iterator end() const {
return Iterator();
}
//REQUIRES: i is a valid, dereferenceable iterator associated with this list
//MODIFIES: may invalidate other list iterators
//EFFECTS: Removes a single element from the list container
void erase(Iterator i) {
if (i.node_ptr == first) {
pop_front();
} else if (i.node_ptr == last) {
pop_back();
} else {
Node *temp = i.node_ptr;
i.node_ptr->prev->next = i.node_ptr->next;
i.node_ptr->next->prev = i.node_ptr->prev;
delete temp;
}
num -= 1;
}
//REQUIRES: i is a valid iterator associated with this list
//EFFECTS: inserts datum before the element at the specified position.
void insert(Iterator i, const T &datum) {
if (i.node_ptr == first) {
push_front(datum);
} else if (i.node_ptr == nullptr) {
push_back(datum);
} else {
Node *temp = new Node{};
temp->datum = datum;
temp->next = i.node_ptr;
temp->prev = i.node_ptr->prev;
i.node_ptr->prev->next = temp;
i.node_ptr->prev = temp;
num += 1;
}
}
};//List
////////////////////////////////////////////////////////////////////////////////
// Add your member function implementations below or in the class above
// (your choice). Do not change the public interface of List, although you
// may add the Big Three if needed. Do add the public member functions for
// Iterator.
#endif // Do not remove this. Write all your code above this line.