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

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