Custom Linked List Sort Method

[martianxx]

Hi I am making a custom linked list (for fun!) and want to implement a sort method that sorts the stored data using the stored types > and < operators (will require the type to have these operators overloaded)

What is the best way to do this? I guess the first thing one might jump to would be to compare the current node with the the node to its "right" see if one is greater than the other. Then keep iterating through the list until you don't swap any more nodes. However I am thinking there is probably a more efficient way to do this. Here is my code so far:

#ifndef LIST_HPP
#define LIST_HPP

#include <string>

template <typename T>
class Node;

template <typename T>
class List
{	
	public:
		List();
		~List();
		
		bool isEmpty() const;
		T& front();
		T& back();
		inline unsigned int size() const;
		void pushFront(const T& s);
		void removeElement(const T& s);
		void insert(const T& s);
		T popFront();
		const T* each();
		
	private:
		unsigned int size_;
		Node<T>* head_;
		Node<T>* current_;		
};

template <typename T> List<T>::List() : size_(0), head_(0), current_(0)
{
}

template <typename T> List<T>::~List()
{
	while (isEmpty())
	{
		popFront();
	}
	head_ = 0;
}

template <typename T> bool List<T>::isEmpty() const
{
	return (!size_ || !head_);
}


template <typename T> T& List<T>::front()
{
	if (isEmpty())
		throw std::string("List Empty");

	return head_->data();
}

template <typename T> T& List<T>::back()
{
	Node<T>* cur = head_;
	
	while (true)
	{
		if (cur->next() == 0)
			return cur->data();
			
		cur = cur->next();
	}
}

template <typename T> void List<T>::pushFront(const T& s)
{
	current_ = head_ = new Node<T>(s, head_);
		
	size_++;
}

template <typename T> T List<T>::popFront()
{
	if (isEmpty())
	{
		throw std::string("List Empty");
	}
	
	Node<T>* current_head = head_;
	current_ = head_ = head_->next();
	
	T temp = current_head->data();
	
	delete current_head;
	
	size_--;
	
	return temp;
}
template <typename T> const T* List<T>::each()
{
	if (isEmpty())
		return 0;
		
	if (current_ == 0)
	{
		current_ = head_;
		return 0;
	}
	
	const T* ret_str = &current_->data();
	
	current_ = current_->next();
	
	return ret_str;
}
template <typename T> void List<T>::removeElement(const T& s)
{
	if (isEmpty())
	{
		throw std::string("List Empty");
		return;
	}
	
	Node<T>* prev = 0, *rnode;
	
	rnode = head_;
	
	while (rnode != 0)
	{
		if (rnode->data() == s)
			break;
			
		prev = rnode;
		rnode = rnode->next();
	}
	
	if (prev == 0)
	{
		Node<T>* temp = head_;
		current_ =  head_ = head_->next();
		
		delete temp;		
	}
	else
	{
		prev->next(rnode->next());
		delete rnode;
	}
	
	size_--;
}
template <typename T> void List<T>::insert(const T& s)
{
	if (isEmpty())
	{
		pushFront(s);
	}
	else if (size_ == 1)
	{
		if (s <= head_->data())
			pushFront(s);
		else
			head_->next(new Node<T>(s, 0));
			
		size_++;
	}
	else
	{
		Node<T>* current, *prev = 0, *new_node = 0;
		
		while (current != 0)
		{
			if (s <= current->data())
				break;
				
			prev = current;
			current = current->next();
		}
		
		if (prev == 0)
			pushFront(s);
		else
			prev->next(new Node<T>(s, current));
			
		size_++;
		
	}
	
}

template <typename T> unsigned int List<T>::size() const {return size_;}

template <typename T>
class Node
{
	public:
		Node(const T& data, Node<T>* next = 0);
		T& data();
		Node* next();
		void next(Node<T>* n);
		
	private:
		T data_;
		Node* next_;
};

template <typename T> Node<T>::Node(const T& data, Node* next): data_(data), next_(next)
{
}

template <typename T> void Node<T>::next(Node<T>* n)
{
	next_ = n;
}
template <typename T> Node<T>* Node<T>::next()
{
	return next_;
}
template <typename T> T& Node<T>::data()
{
	return data_;
}
#endif //LIST_HPP 

Surely there is a way to sort with only one iteration through the list? Or maybe not.

Thanks for any help in advance!

[writetonsharma]

What you are asking for is O(n) time complexity. This is not even possible for data which is contiguous in memory. There are some algo's though which can give O(n) complexity but they are not practical for production environments.

Here you have a linked list which has nodes scattered in memory. generally the sort take O(n^2)time complexity for a linked list. This can be marginally improved (reducing the constant factor may be). What you can do is use a external data structure may be a tree or hash table and keep some metadata in that (sorted) which will map to the actual linkedlist.

[martianxx]

I wrote this code a few weeks ago. Looks like I am ahead of myself. The list seems to sort the data as I insert it.