List.h

#pragma once
#include <iterator>
#include <iostream>
#include <algorithm>

using namespace std;

template <class T>
class List {
  private:
    class ListNode {
      public:
        ListNode();

        ListNode(const T & ndata);

        ListNode* next;

        ListNode* prev;

        const T data;
    };

  public:
    List();

    List(const List<T>& other);

    List<T>& operator=(const List<T>& rhs);

    int size() const;

    void print(ostream& os) const;

    bool empty() const;

    ~List();

    void insertFront(const T& ndata);

    void insertBack(const T& ndata);

    void reverse();

    void reverseNth(int n);

    void waterfall();

    List<T> split(int splitPoint);

    void mergeWith(List<T>& otherList);

    void sort();

    // ListIterator is an inner-class of List, defined in a separate
    // file:
    #include "List-ListIterator.hpp"

    ListIterator begin() const;

    ListIterator end() const;

    // Iterator constructor
    template <class Iter>
    List(const Iter& start, const Iter& end);

  private:
    /*
     * Private member variables.
     *
     * You must use these as specified in the spec and may not rename them.
     * You may add more if you need them.
     */

    ListNode* head_;

    ListNode* tail_;

    int length_;

    /*
     * Private helper functions.
     *
     * You must use these as specified in the spec and may not rename them.
     * You may place more here as you need them.
     */

    void _copy(const List<T>& other); // implemented in List-given.hpp

    void _destroy();

    void reverse(ListNode*& startPoint, ListNode*& endPoint);

    ListNode* split(ListNode* start, int splitPoint);

    ListNode* merge(ListNode* first, ListNode* second);

    ListNode* mergesort(ListNode* start, int chainLength);
};

// needed for template instantiation
#include "List.hpp"

// this includes all of the functions that are given to you
// (i.e., the ones that you do not need to implement)
#include "List-given.hpp"