How to sort a singly linked LinkedList?

[Accendo]

I have tried having a look around on the web at different forums and can't decipher how to do this.

This is my Link class:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LinkedListGen
{
class LinkGen<T>
{
private T data;
private LinkGen<T> next;

public LinkGen(T item)
{
data = item;
next = null;
}

public LinkGen(T item, LinkGen<T> list)
{
data = item;
next = list;
}

public T HeadList
{
set { this.data = value; }
get { return this.data; }
}

public LinkGen<T> TailList
{
set { this.next = value; }
get { return this.next; }
}


}
}

And this is my LinkedListGen class:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LinkedListGen
{
    class LinkListGen<T> where T:IComparable
    {
        private LinkGen<T> list; //default value – empty list
        int count = 0;
        bool flag = false


public void AppendItem(T item) // Add items to back of list
{
LinkGen<T> temp = list;

if (temp == null)
{
list = new LinkGen<T>(item);
}

else
{
while (temp.TailList != null)
{
temp = temp.TailList;
}

temp.TailList = new LinkGen<T>(item);
}

}



public void Sort()
{
//I need the sort method here ofc.
}



public void AddItem(T item) //add item to front of list
{
list = new LinkGen<T>(item, list);
}

In the above class I do have a few more methods; RemoveItem, Concatenate, DisplayItems, Copy(Directly copy 1 lists contents to another), NumberOfItems, IsItemPresent. I only thought I should put in the methods that I think would get used just to save a massive amount of space.

Please help lol

Regards!

[Momerath]

You'll need either addbefore (easiest) or addafter to sort.

Create a new empty list. 
Go through each item in your list
    Find first item in new list that is greater than current item.
    Add current item before this item
New list is now in sorted order.

This isn't the fastest sort around. You can sort even faster by:

Build array out of list.
Array.Sort(array)
Build list out of array appending each item to new list

[Accendo]

Haha, I am just in the middle of trying to to it with an ArrayList.

*Trundles back to workshop for 5 minutes*

[Accendo]

Hey again, I have gotten to this point and my brain has re-frozen over...

public void Sort()
        {
            LinkListGen<int> newList = new LinkListGen<int>();
            ArrayList z = new ArrayList();
            //int x = 0;
            LinkGen<T> temp = list;
            
            while (temp != null)
            {
                z.Add(temp.HeadList);
                temp = temp.TailList;
            }

            z.Sort();

                foreach (int i in z)
                    newList.AddItem(i);
            


        }

I just can't think how to return this as my LinkedList I entered. If I can just go through the input, it would be:

a.Sort() //This is what I would input in my main class but how do I get my sort to do that from newList :S

[Momerath]

Don't use ArrayList, it isn't strongly typed and will not help. Use List<T> and when you need the array, call List<T>.ToArray().

I also think you'll have problems because you treat the list and a node in the list in the same class. You should have two classes: LinkedList<INode<T>> and INode<T>.

LinkedList would have all the add, remove, etc. methods.

INode would be something like:

interface INode<T> {
    T Value {get; set;}
    INode<T> Next {get; set;}
}

[Accendo]

Oh alright, okay then with the ArrayList. Could I pick your brains about that List<T> class, sadly must go home now and have no internets there grrr... But if you could just point in me in the right direction with it - a website with an example or such.

Also the thing you call INode (I have seen this before sadly my tutors set us on the path of different naming conventions) I have called LinkGen, it's my highest up piece of code. LinkGen and LinkListGen are seperate classes (in my first post) and it is how you said, for the adding and such :) - least I on right lines there.

Regards,
Ryan

[Momerath]

You are sort of on the right lines, but your node class has the add/delete etc methods in it. Those should be part of the linked list class, not the node. Nodes should know as little as possible about being a linked list.

List<T>

[Accendo]

OMG YES FINALLY!!!!

I spent HOURS (about 2) trying all different ways to do this I come back today and complete this method within about 15 minutes - Momerath if I was a woman I would now bear your children CHEERS!!!

[Accendo]

Here is my final code for the sort method, I am guessing as a newbie there are MANY ways to get it down to a handful of lines but here it is in it's working glory...

public void Sort()
        {
            List<T> z = new List<T>();
            LinkGen<T> temp = list;
            list = null; //After the above line creates a temp of list this empties the current LinkList for throwing back

            while (temp != null) //This while loop adds all the current list's contents to a List<T>  
            {
                z.Add(temp.HeadList);
                temp = temp.TailList;
            }

            z.Sort(); //This uses List<T> inherent .Sort() method

                foreach (T i in z) //This is where I send every item from the List<T> straight back into the list that was input
                    AddItem(i);
        }

Look at that beautiful little List<T> class there lol :P

Thanks again!