Help sorting nodes inside a list

Question

Im currently working with a generic linked list in C# and I need to sort the nodes inside the list.

namespace ConsoleApplication1
{

// T is the type of data stored in a particular instance of GenericList.
public class GenericList<T>
{
    private class Node
    {
        // Each node has a reference to the next node in the list.
        public Node Next;
        // Each node holds a value of type T.
        public T Data;
    }

    // The list is initially empty.
    private Node head = null;

    // Add a node at the beginning of the list with t as its data value.
    public void AddNode(T t)
    {
        Node newNode = new Node();
        newNode.Next = head;
        newNode.Data = t;
        head = newNode;
    }

    // The following method returns the data value stored in the last node in
    // the list. If the list is empty, the default value for type T is
    // returned.
    public T GetFirstAdded()
    {
        // The value of temp is returned as the value of the method. 
        // The following declaration initializes temp to the appropriate 
        // default value for type T. The default value is returned if the 
        // list is empty.
        T temp = default(T);

        Node current = head;
        while (current != null)
        {
            temp = current.Data;
            current = current.Next;
        }
        return temp;
    }
}
}

Any ideas?

Where are the methods to remove a node and compare data in a node? Those would be useful to have as well. — JB King, Mar 17 '11 at 20:56
Will this help you? http://stackoverflow.com/questions/768095/sorting-a-linked-list — WorldIsRound, Mar 17 '11 at 20:58

score 1 · Answer 1 · answered Mar 17 '11 at 21:28

I'd slightly change the list in this way:

// implement IEnumerable<T>
public class GenericList<T> : IEnumerable<T>
{
    #region Constructors

    public GenericList()
    {
    }

    public GenericList(IEnumerable<T> values)
        : this()
    {
        foreach (var val in values)
            this.AddNode(val);
    }

    #endregion

    #region IEnumerable Implementations

    public IEnumerator<T> GetEnumerator()
    {
        return new Enumerator(this);
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return new Enumerator(this);
    }

    #endregion

    #region Nested Enumerator

    class Enumerator : IEnumerator<T>
    {
        private GenericList<T> innerList;
        private Node current;
        private bool started;

        public Enumerator(GenericList<T> list)
        {
            this.innerList = list;
            this.current = null;
            started = false;
        }

        public T Current
        {
            get
            {
                if (!started)
                    throw new InvalidOperationException("You can't ask Current before calling MoveNext()");
                return current.Data;
            }
        }

        object System.Collections.IEnumerator.Current
        {
            get { return this.Current; }
        }

        public bool MoveNext()
        {
            if (!started)
            {
                current = innerList.head;
                started = true;
            }
            else
            {
                current = current.Next;
            }
            if (current != null)
                return true;
            return false;
        }

        public void Reset()
        {
            started = false;
            current = null;
        }

        public void Dispose()
        {
        }
    }

    #endregion

    #region Your methods i.e. AddNode() etc.

    //...

    #endregion

}

Implementing IEnumerable<T> you can use LINQ OrderBy() and OrderByDescending() methods on the list (as well as iterate it using foreach), and the new constructor allows you to create a new linked list easier:

var sortedList = new GenericList<int>(unsortedList.OrderBy(x => x));

score 0 · Answer 2 · answered Mar 17 '11 at 21:24

I feel like you're trying to ask:

"I don't know anything about the class of objects my list holds! How can I ever sort a list of objects I know nothing about?!"

Here's the answer to that question.

Your T type should implement an interface. IComparable is likely the one you want. This will give you a means of comparing the object that's passed in by requiring them to have a comparison method. Something like:

public class GenericList<T> where T : System.IComparable<T>

What this does is ensure that whatever generic class you make this List for, that class will have a CompareTo method, allowing objects of that class to be compared to other objects of that class. Comparison is a fundamental necessity of sorting.

Once you have that hooked up, you can sort your list using your favorite sorting algorithm, and using the CompareTo(T item) method. Simple algorithms would include insertion sort and selection sort. The ambitious might try out merge sort.

If this isn't what you meant to ask, please let me know, and we can get to the bottom of what you're having trouble with.

Help sorting nodes inside a list

2 Answers2