Помогите отсортировать узлы внутри списка

Question

Сейчас я работаю с общим связанным списком в C #, и мне нужно отсортировать узлы внутри списка.

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;
    }
}
}

Есть идеи?

Answer 1

Я бы немного изменил список следующим образом:

// 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

}

Реализуя IEnumerable<T>, вы можете использовать методы LINQ OrderBy() и OrderByDescending() в списке (а также повторять его, используя foreach), а новый конструктор позволяет вам легче создавать новый связанный список:

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

Answer 2

Я чувствую, что вы пытаетесь спросить:

«Я ничего не знаю о классе объектов, который содержит мой список! Как я могу отсортировать список объектов, о которых ничего не знаю?!»

Вот ответ на этот вопрос.

Ваш тип T должен реализовывать интерфейс . IComparable скорее всего тот, который вы хотите. Это даст вам возможность сравнивать переданный объект, требуя, чтобы у них был метод сравнения. Что-то вроде:

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

Это обеспечивает то, что для любого универсального класса, для которого вы создаете этот Список, у этого класса будет метод CompareTo, позволяющий сравнивать объекты этого класса с другими объектами этого класса. Сравнение является фундаментальной необходимостью сортировки.

Как только вы это подключите, вы можете отсортировать список, используя ваш любимый алгоритм сортировки и метод CompareTo (T item). Простые алгоритмы будут включать сортировку вставок и сортировку выбора . Амбициозный мог бы попробовать сортировать слиянием .

Если это не то, что вы хотели спросить, пожалуйста, дайте мне знать, и мы сможем разобраться в том, с чем у вас возникли проблемы.