Custom Linked List Sort Method

Question

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!

Answer 1

Could use a Radix Sort and there is a very nice article on linked list sorting more efficient than performing a node to every other node comparison in O(n * n) time here.