Sorting using nodes

[nj1995]

Hi, I am struggling to figure out how to sort the values in a List class using nodes, any help is appreciated, thanks!

#include <iostream>
#include <iterator> 
#include <list>
#include <math.h>
#include <algorithm>
#include <cstdlib>	
using namespace std;

template <typename Object>
class List
{
	template <class	U>
	friend void displayList(List<U> &l1);
	template <class U>
	friend void displayListInReverse(List<U> &l1);
	template <class U>
	friend void insertSorted(List<U> &l1, U n);
private:
	struct Node
	{
		Object  data;
		Node   *prev;
		Node   *next;

		Node(const Object & d = Object(), Node *p = nullptr, Node *n = nullptr) : data(d), prev(p), next(n)
		{ }

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

public:
	class const_iterator
	{
		friend class List<Object>;

	public:
		const_iterator() : current(nullptr)
		{ }

		const Object& operator*() const
		{
			return retrieve();
		}

		const_iterator & operator++()
		{
			current = current->next;
			return *this;
		}

		const_iterator operator++(int)
		{
			const_iterator old = *this;
			++(*this);
			return old;
		}

		const_iterator & operator--()
		{
			current = current->prev;
			return *this;
		}

		const_iterator operator--(int)
		{
			const_iterator old = *this;
			--(*this);
			return old;
		}

		bool operator==(const const_iterator & rhs) const
		{
			return current == rhs.current;
		}

		bool operator!=(const const_iterator & rhs) const
		{
			return !(*this == rhs);
		}

	protected:
		Node *current;

		Object & retrieve() const
		{
			return current->data;
		}

		const_iterator(Node *p) : current(p)
		{ }

	};

	class iterator : public const_iterator
	{
		friend class List<Object>;

	public:

		iterator()
		{ }

		Object & operator*()
		{
			return const_iterator::retrieve();
		}

		const Object & operator*() const
		{
			return const_iterator::operator*();
		}

		iterator & operator++()
		{
			this->current = this->current->next;
			return *this;
		}

		iterator operator++(int)
		{
			iterator old = *this;
			++(*this);
			return old;
		}

		iterator & operator--()
		{
			this->current = this->current->prev;
			return *this;
		}

		iterator operator--(int)
		{
			iterator old = *this;
			--(*this);
			return old;
		}

	protected:

		iterator(Node *p) : const_iterator(p)
		{ }
	};

public:
	List()
	{
		init();
	}

	~List()
	{
		clear();
		delete head;
		delete tail;
	}

	List(const List & rhs)
	{
		init();
		for (auto & x : rhs)
			push_back(x);
	}

	List & operator=(const List & rhs)
	{
		List copy = rhs;
		std::swap(*this, copy);
		return *this;
	}

	List(List && rhs)
		: theSize(rhs.theSize), head(rhs.head), tail(rhs.tail)
	{
		rhs.theSize = 0;
		rhs.head = nullptr;
		rhs.tail = nullptr;
	}

	List & operator=(List && rhs)
	{
		std::swap(theSize, rhs.theSize);
		std::swap(head, rhs.head);
		std::swap(tail, rhs.tail);

		return *this;
	}

	iterator begin()
	{
		return iterator(head->next);
	}

	const_iterator begin() const
	{
		return const_iterator(head->next);
	}

	iterator end()
	{
		return iterator(tail);
	}

	const_iterator end() const
	{
		return const_iterator(tail);
	}

	int size() const
	{
		return theSize;
	}

	bool empty() const
	{
		return size() == 0;
	}

	void clear()
	{
		while (!empty())
			pop_front();
	}

	Object& front()
	{
		return *begin();
	}

	const Object& front() const
	{
		return *begin();
	}

	Object& back()
	{
		return *--end();
	}

	const Object& back() const
	{
		return *--end();
	}

	void push_front(const Object& x)
	{
		insert(begin(), x);
	}

	void push_back(const Object& x)
	{
		insert(end(), x);
	}

	void push_front(Object&& x)
	{
		insert(begin(), move(x));
	}

	void push_back(Object&& x)
	{
		insert(end(), move(x));
	}

	void pop_front()
	{
		erase(begin());
	}

	void pop_back()
	{
		erase(--end());
	}

	// Insert x before itr.
	iterator insert(iterator itr, const Object & x)
	{
		Node *p = itr.current;
		++theSize;
		return iterator(p->prev = p->prev->next = new Node(x, p->prev, p));
	}

	iterator insert(iterator itr, Object && x)
	{
		Node *p = itr.current;
		++theSize;
		return iterator(p->prev = p->prev->next = new Node(move(x), p->prev, p));
	}

	iterator erase(iterator itr)
	{
		Node *p = itr.current;
		iterator retVal(p->next);
		p->prev->next = p->next;
		p->next->prev = p->prev;
		delete p;
		--theSize;

		return retVal;
	}

	iterator erase(iterator from, iterator to)
	{
		for (iterator itr = from; itr != to; )
			itr = erase(itr);

		return to;
	}

private:
	int   theSize;
	Node *head;
	Node *tail;

	void init()
	{
		theSize = 0;
		head = new Node;
		tail = new Node;
		head->next = tail;
		tail->prev = head;
	}
};

template <class T>
void displayList(List<T> &l1)
{
	for (List<T>::iterator it = l1.begin(); it != l1.end(); ++it)
	{
		cout << ' ' << *it;
	}
}

template <class T>
void displayListInReverse(List<T> &l1)
{
	for (List<T>::iterator it = l1.end(); it != l1.begin(); --it)
	{
		cout << ' ' << *it;
	}
}

template <class T>
void insertSorted(List<T> &l1, T n)
{

}

int main()
{
	List<int> l1;
	for (int i = 0; i < 10; i++)
	{
		l1.push_back((rand() % 50) + 1);
	}

	cout << endl << "From first to last, sorted list l1 contains:" << endl;
	displayList(l1);

	cout << endl;

	cout << endl << "We now insert 55 by calling 'insertSorted' function." << endl;


	cout << endl << "After inserting 55, list l1 remains sorted and it contains: " << endl;
	displayList(l1);
	cout << endl;

	cout << endl << "Display list l1 in reverse: " << endl;
	displayListInReverse(l1);

	system("PAUSE");
	return 0;
}