Implementation for all the members functions in the list.h file the code for the file is given at the end. Thank You

Objectives: Understanding generic programming and information hiding by developing generic containers. Getting familiar with the concept of class template and its usage. Use of nested (iterator) classes. Use of namespace. Operator overloading.Task: Implement a doubly-linked list class template List and its associated iterators.

Requirements:

1. A header file List.h is provided, which contains the interfaces of the doubly linked list class template List. In particular, it contains a nested Node structure, and two nested iterators class (iterator and const_iterator). You cannot change anything in the List.h file. The List.h file is attached to this assignment.

2. You need to implement the member functions of the doubly-linked list class template List in a file named List.hpp. Note that List.hpp has been #included in the header file List.h (towards the end of the file).

3. Analyze the worst-case run-time complexities of the member functions reverse() and remove_if(). Give the complexities in the form of Big-O. Your analysis can be informal; however, it must be clearly understandable by others. Name the file containing the complexity analysis as "analysis.txt".

List.h File

#ifndef DL_LIST_H #define DL_LIST_H #include #include

namespace cop4530 {

template class List { private: // nested Node class struct Node { T data; Node *prev; Node *next;

Node(const T & d = T{}, Node *p = nullptr, Node *n = nullptr) : data{d}, prev{p}, next{n} {} Node(T && d, Node *p = nullptr, Node *n = nullptr) : data{std::move(d)}, prev{p}, next{n} {} };

public: //nested const_iterator class class const_iterator { public: const_iterator(); // default zero parameter constructor const T & operator*() const; // operator*() to return element // increment/decrement operators const_iterator & operator++(); const_iterator operator++(int); const_iterator & operator--(); const_iterator operator--(int);

// comparison operators bool operator==(const const_iterator &rhs) const; bool operator!=(const const_iterator &rhs) const;

protected: Node *current; // pointer to node in List T & retrieve() const; // retrieve the element refers to const_iterator(Node *p); // protected constructor

friend class List; };

// nested iterator class class iterator : public const_iterator { public: iterator(); T & operator*(); const T & operator*() const;

// increment/decrement operators iterator & operator++(); iterator operator++(int); iterator & operator--(); iterator operator--(int);

protected: iterator(Node *p); friend class List; };

public: // constructor, desctructor, copy constructor List(); // default zero parameter constructor List(const List &rhs); // copy constructor List(List && rhs); // move constructor

// num elements with value of val explicit List(int num, const T& val = T{});

// constructs with elements [start, end) List(const_iterator start, const_iterator end);

// constructs with a copy of each of the elements in the initalizer_list List (std::initializer_list iList);

~List(); // destructor

// copy assignment operator const List& operator=(const List &rhs);

// move assignment operator List & operator=(List && rhs);

// sets list to the elements of the initializer_list List& operator= (std::initializer_list iList);

// member functions int size() const; // number of elements bool empty() const; // check if list is empty void clear(); // delete all elements void reverse(); // reverse the order of the elements

T& front(); // reference to the first element const T& front() const; T& back(); // reference to the last element const T& back() const;

void push_front(const T & val); // insert to the beginning void push_front(T && val); // move version of insert void push_back(const T & val); // insert to the end void push_back(T && val); // move version of insert void pop_front(); // delete first element void pop_back(); // delete last element

void remove(const T &val); // remove all elements with value = val

template void remove_if(PREDICATE pred); // remove all elements for which Predicate pred // returns true. pred can take in a function object

// print out all elements. ofc is deliminitor void print(std::ostream& os, char ofc = ' ') const;

iterator begin(); // iterator to first element const_iterator begin() const; iterator end(); // end marker iterator const_iterator end() const; iterator insert(iterator itr, const T& val); // insert val ahead of itr iterator insert(iterator itr, T && val); // move version of insert iterator erase(iterator itr); // erase one element iterator erase(iterator start, iterator end); // erase [start, end)

private: int theSize; // number of elements Node *head; // head node Node *tail; // tail node void init(); // initialization };

// overloading comparison operators template bool operator==(const List & lhs, const List &rhs);

template bool operator!=(const List & lhs, const List &rhs);

// overloading output operator template std::ostream & operator<<(std::ostream &os, const List &l);

// include the implementation file here

#include "List.hpp"

} // end of namespace 4530

#endif