Sortable linked list of objects

For a school lab I have to make a linked list of messages and then sort those messages by priority, with "High" priority being pulled out first, then medium, then low. I've been trying to figure this out for days and I can't wrap my mind around the sorting. I've been trying to get it to sort without adding anything other than a head and a size field in my ListofMessages class but all I seem to do is add garbage code. I wanted to figure this out myself but right now I'm stumped.

Here's what I have so far. Hopefully you can make sense of it:

class ListOfMessages
{
    private int m_nSize;
    public Message m_cListStart;
    //public Message m_cNextItem;
    public Message m_cLastItem;

    public ListOfMessages()
    {
        m_nSize = 0;
        m_cListStart 开发者_C百科= null;
        //m_cNextItem = null;
    }

    public int Count
    {
        get { return m_nSize; }
    }       

    public string Display(Message cMessage)
    {
        return "Message: " + cMessage.m_strMessage + "\nPriority: " + cMessage.m_strPriority;
    }

    //list additions
    public int Add(Message newMessage)
    {
        Message nextMessage = new Message();
        //inserts objects at the end of the list
        if (m_nSize == 0)
        {
            m_cListStart = newMessage;
                //m_cLastItem = newMessage;
        }
        else
        {
            Message CurrentMessage = m_cListStart;

            if (newMessage.m_strPriority == "High")
            {

                    if (m_cListStart.m_strPriority != "High")
                    {
                        //Make the object at the start of the list point to itself
                        CurrentMessage.m_cNext = m_cListStart;
                        //Replace the object at the start of the list with the new message
                        m_cListStart = newMessage;

                    }
                else
                {
                    Message LastMessage = null;

                    for (int iii = 0; iii < m_nSize; iii++)//(newmessage.m_strpriority == iii.m_strpriority)
                    //&& (iii.m_cnext == null);)
                    {
                        if (m_cListStart.m_strPriority != "High")
                        {
                            nextMessage = newMessage;
                            nextMessage.m_cNext =
                            CurrentMessage = nextMessage;
                            //LastMessage.m_cNext = CurrentMessage;
                        }
                        LastMessage = CurrentMessage;

                        if (m_cListStart.m_cNext != null)
                            m_cListStart = m_cListStart.m_cNext;
                    }
                }
                //iii = iii.m_cnext;
            }
                    // for (int iii = m_cListStart; ; iii = iii.m_cNext)//(newMessage.m_strPriority == iii.m_strPriority)
                    //    //&& (iii.m_cNext == null);)
                    //{
                    //    //Message lastMessage = iii;
                    //    if (iii.m_strPriority != iii.m_strPriority)
                    //    {
                    //        //iii.m_cNext = newMessage;
                    //        newMessage.m_cNext = iii.m_cNext;
                    //        iii.m_cNext = newMessage;
                    //    }


                    //m_cLastItem.m_cNext = newMessage;
        }
            //m_cLastItem = newMessage;
            return m_nSize++;
    }

    public Message Pop()
    {
        //Message Current = m_cListStart;
        //if the object at the start of the list has another object after it, make that object the start of the list
        //and decrease the size by 1 after popping an object off if there is more than 1 object after the start of the list
        if (m_cListStart.m_cNext != null)
        {
            m_cListStart = m_cListStart.m_cNext;
        }
        if (m_nSize > 0)
            m_nSize--;
        else
            m_cListStart = null;
        return m_cListStart;
        //if (m_cListStart.m_cNext != null)
        //    m_cListStart = m_cListStart.m_cNext;
        //if (m_nSize > 1)
        //    m_nSize--;
        //return m_cListStart;
    }

My pop function to retrieve the messages might need some refining but most of the work right now lies in the Add function. I'm really just stumbling through the dark there.

Does anyone know of a simple way of doing what I'm asking?

---

Why dont you write a custom linked list as follows:

class Node<T> : IComparable<T>
{
   public int Priority {set;get;}
   public T Data {set;get;}
   public Node<T> Next {set;get;}
   public Node<T> Previous {set;get;}

   // you need to implement IComparable here for sorting.
}

This is your node definitions. Now We need to implement a LinkedList Class.

Your linked list class can be doubly linked list, since you dont have any specs on it. and it would be easier with doubly linked list.

Here is the definition:

class LinkedList<T> : IEnumerable<T> where T: IComparable
{
    public Node<T> Head {set;get;}
    public Node<T> Tail {set;get;}

    // set of constructors
    //.....

    public void Insert(Node<T> node)
    {
       // you can do recursive or iterative impl. very easy.
    }

    // other public methods such as remove, insertAfter, insert before, insert last etc.

    public void Sort()
    {
       // easiest solution is to use insertion sort based on priority.
    }

}

If you can get away by creating extra memory, ie: another linked list. insertion sort would be fine. For this purpose you need to implement insert after functionality as well.

I have a LinkedList implementation, you can check it out. You just need to implement sorting based on priority, you can use bubble sort, insertion sort, or merge sort.

Also, you might want to look at Heap which you can use to implement a priority Queue, it serves the purpose. I have a Heap Data Structure Implementation, you can check it out.

---

The easiest solution would be to have three singly-linked lists, one for each priority.

When you add, you add to the end of the correct list. When you remove, you first try to remove from the highest priority list. If that is empty, try the middle one. If even that is empty, use the lowest list.

If you have constant number of priorities, the time complexities are O(1) in both cases.