Bubble sort a linklist template

I am trying to sort a linked list. I am having problems with const. It wont let me assign to a variable that is const which is what it suppose to do. However, I dont' know how to work around this? I would appreciate any help I could get.

This is all in one header file, the sort function is also, I will try to pull it out so it's easy to find:

void LinkedList<T>::BubleSort()
{

T temp;
ListElement<T>* cur = head;

    const ListElement<T>* forward = head->Next();


while(cur)
{
    while(forward)
    {

        if(cur->Datum() > forward->Datum())
        {

                  temp = cur->Datum();
                  cur->Datum() = forward->Datum();
                  forward->Datum() = temp;
        }
    }
}

}

The errors I get

error C3892: 'cur' : you cannot assign to a variable that is const while compiling class template member function 'void LinkedList::BubleSort(void)' see reference to class template instantiation 'LinkedList' being compiled

of course if its const I can't do this, I just don't know how to get around this.

Here is the header file where all the info is and the sort function:

#include  <typeinfo>

template <class T>
class LinkedList;

template <class T>
class ListElement
{
T datum;
ListElement* next;

ListElement (T const&, ListElement*);
public:
T const& Datum () const;
ListElement const* Next () const;

friend class    LinkedList<T>;  
};

template <class T>
class LinkedList
{
ListElement<T>* head;
ListElement<T>* tail;
public:
LinkedList ();
~LinkedList ();

LinkedList (LinkedList const&);
LinkedList& operator = (LinkedList const&);

ListElement<T> const* Head () const;
ListElement<T> const* Tail () const;
bool IsEmpty () const;
T const& First () const;
T const& Last () const;

void BubleSort();
void Prepend (T const&);
void Append (T const&);
void Extract (T const&);
void Purge ();
void InsertAfte开发者_开发百科r (ListElement<T> const*, T const&);
void InsertBefore (ListElement<T> const*, T const&);
};

template <class T>
ListElement<T>::ListElement (
T const& _datum, ListElement<T>* _next) :
datum (_datum), next (_next)
{}

template <class T>
T const& ListElement<T>::Datum () const
{ return datum; }

template <class T>
ListElement<T> const* ListElement<T>::Next () const
{ return next; }



template <class T>
LinkedList<T>::LinkedList () :
head (0),
tail (0)
{}


template <class T>
void LinkedList<T>::Purge ()
{
while (head != 0)
{
ListElement<T>* const tmp = head;
head = head->next;
delete tmp;
}
tail = 0;
}

template <class T>
LinkedList<T>::~LinkedList ()
{ Purge (); }



template <class T>
ListElement<T> const* LinkedList<T>::Head () const
{ return head; }

template <class T>
ListElement<T> const* LinkedList<T>::Tail () const
{ return tail; }

template <class T>
bool LinkedList<T>::IsEmpty () const
{ return head == 0; }



template <class T>
T const& LinkedList<T>::First () const
{
if (head == 0)
    throw std::domain_error ("list is empty");
return head->datum;
}

template <class T>
T const& LinkedList<T>::Last () const
{
if (tail == 0)
    throw std::domain_error ("list is empty");
return tail->datum;
}
/**********************************************/

template <class T>

void LinkedList<T>::BubleSort()
{

T temp;
ListElement<T>* cur = head;
;
const ListElement<T>* forward = head->Next();


while(cur)
{
    while(forward)
    {

        if(cur->Datum() > forward->Datum())
        {

          temp = cur->Datum();
          cur->Datum() = forward->Datum();
          forward->Datum() = temp;
        }
    }
}

}

template <class T>
void LinkedList<T>::Prepend (T const& item)
{
ListElement<T>* const tmp = new ListElement<T> (item, head);
if (head == 0)
tail = tmp;
head = tmp;
}



template <class T>
void LinkedList<T>::Append (T const& item)
{
ListElement<T>* const tmp = new ListElement<T> (item, 0);
if (head == 0)
head = tmp;
else
tail->next = tmp;
tail = tmp;
}



template <class T>
LinkedList<T>::LinkedList (LinkedList<T> const& linkedList) :
head (0),
tail (0)
{
ListElement<T> const* ptr;
for (ptr = linkedList.head; ptr != 0; ptr = ptr->next)
Append (ptr->datum);
}

template <class T>
LinkedList<T>& LinkedList<T>::operator = (
LinkedList<T> const& linkedList)
{
if (&linkedList != this)
{
Purge ();
ListElement<T> const* ptr;
for (ptr = linkedList.head; ptr != 0; ptr = ptr->next)
    Append (ptr->datum);
}
return *this;
}



template <class T>
void LinkedList<T>::Extract (T const& item)
{
ListElement<T>* ptr = head;
ListElement<T>* prevPtr = 0;
while (ptr != 0 && ptr->datum != item)
{
prevPtr = ptr;
ptr = ptr->next;
}
if (ptr == 0)

    throw std::invalid_argument ("item not found");

if (ptr == head)
head = ptr->next;
else
prevPtr->next = ptr->next;
if (ptr == tail)
tail = prevPtr;
delete ptr;
}




template <class T>
void LinkedList<T>::InsertAfter (
ListElement<T> const* arg, T const& item)
{
ListElement<T>* ptr = const_cast<ListElement<T>*> (arg);
if (ptr == 0)
{

}
throw std::invalid_argument ("invalid position");
ListElement<T>* tmp = new ListElement<T> (item, ptr->next);
ptr->next = tmp;
if (tail == ptr)
{

}
tail = tmp;
}

template <class T>
void LinkedList<T>::InsertBefore (
ListElement<T> const* arg, T const& item)
{
ListElement<T>* ptr = const_cast<ListElement<T>*> (arg);
if (ptr == 0)
{

}
throw std::invalid_argument ("invalid position");
ListElement<T>* const tmp = new ListElement<T> (item, ptr);
if (head == ptr)
{

}
head = tmp;
else
{
ListElement<T>* prevPtr = head;
while (prevPtr != 0 && prevPtr->next != ptr)
    prevPtr = prevPtr->next;
if (prevPtr == 0)
{

}
throw std::invalid_argument ("invalid position");
prevPtr->next = tmp;
}
}

Sorting the list is a non-const operation; you can't do it with const accessors only. The usual solution is to overload the accessors with a const and a non-const variant:

ListElement const* Next() const { return next; }
ListElement* Next() { return next; }

You'd do the same thing for the accessor functions in your LinkedList class (unless you want to make the list immutable, of course).

... additionally, you write that Datum() returns a const reference, but then you use a Datum() call as an l-value in "cur->Datum() = forward->Datum();". How is that assignment going to work when the thing on the left is immutable?

Also, you declare forward to be pointer to a constant ListElement and then use forward on the LHS of an assignment: "forward->Datum() = temp;". You probably actually always want forward == cur->Next() in the two while()s. (I.e. always updated to point at whatever's next.) So it can't be const.

You're really going to have to rethink your use of const given the amount of mutability you seem to want to use.