locked
Help sorting a Linked List

    Question

  • Hi,

     

    I’m a beginner in C#. For my applications, I need to sort linked lists.

     

    I’ll show my question with a very simple code.

     

    Basically I create a linked list of integers, add 2 values and need to order this list.

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    
    namespace ConsoleApplication1
    {
        class Program1
        {
            static void ListaLigada()
            {
                
                LinkedList<int> lista1 = new LinkedList<int>(); //creates the list
                lista1.AddFirst(23); //add first value
                lista1.AddFirst(25); //add second value
                
                //now i want to sort
                lista1.OrderByDescending();  
                //or
                lista1.OrderBy();
    
            }
        }
    }

     

    The problem is: the functions orderbydescending and orderby request a method. I’ve tried everything and nothing worked.

     

    The error message is: "No overload for method 'Orderby' takes '0' arguments".

     

    May someone help me?

     

    Thanks.

     

    • Edited by GMainieri Sunday, July 05, 2009 3:49 AM
    Sunday, July 05, 2009 3:45 AM

Answers

  • Hi!

    OrderBy and OrderByDescending are extension methods, and they expect some method (usually passed as lambda) to do the sorting. Try This:

    lista1.OrderByDescending(i => i);
    //or
    lista1.OrderBy(i => i);

    Please note that these methods don't sot the original list; they return a new, sorted one!

    Hope I could help!

    David

    • Proposed as answer by David Fulop Sunday, July 05, 2009 7:14 AM
    • Marked as answer by Figo Fei Thursday, July 09, 2009 3:30 AM
    Sunday, July 05, 2009 7:03 AM

All replies

  • Hi!

    OrderBy and OrderByDescending are extension methods, and they expect some method (usually passed as lambda) to do the sorting. Try This:

    lista1.OrderByDescending(i => i);
    //or
    lista1.OrderBy(i => i);

    Please note that these methods don't sot the original list; they return a new, sorted one!

    Hope I could help!

    David

    • Proposed as answer by David Fulop Sunday, July 05, 2009 7:14 AM
    • Marked as answer by Figo Fei Thursday, July 09, 2009 3:30 AM
    Sunday, July 05, 2009 7:03 AM
  • Just a few things to clarify.

    1. If you have a list of let's say a Peron class with Name, Age and Address properties, and you want a list that contains your Person objects, sorted by the Age property, you have to use the following lambda: 
    var sortedList = pList.OrderBy(p => p.Age);
    This instructs the method to do the sorting by the Age property. The "p" is just a range variable, you can name it anything. It refers to the "current" element in the sorting.

    2. Lambdas are anonymous methods (meaning in most of the cases when you are dealing with CLR objects, you can interchange them). If you like the anonymous method syntax more, you could write the following:
    var sortedList = pList.OrderBy(delegate(Person p) { return p.Age; });

    Hope this helps! :)

    David
    Sunday, July 05, 2009 7:14 AM
  • Hi,
    Welcome to C#. Hope you are doing well.

    One of the way to order in memory List is to use LINQ. For instance,

    LinkedList<int> lista1 = new LinkedList<int>(); //creates the list
    lista1.AddFirst(23); //add first value
    lista1.AddFirst(25); //add second value
    
    //now i want to sort
    IEnumerable<int> orderedResult = from item in lista1
                                     orderby item
                                     select item;
    
    foreach (var item in orderedResult)
    {
        Console.WriteLine(item.ToString());
    }
    Beside this, the OrderBy method is extension method with which you can use http://msdn.microsoft.com/en-us/library/bb383977.aspx

    Hope this will gives you a better picture. Please feel free to discuss further

    Adil Mughal - MCP http://adilamughal.blogspot.com
    Sunday, July 05, 2009 7:21 AM
  • Thanks David,

    Is something like this that i'm looking for.

    But is not working, how should i declare this variable 'i'?
    Sunday, July 05, 2009 11:05 AM
  • Thanks David,

    how should i declare this variable 'p'?

    var p; //?

    This simple example is just for learning purposes.
    I'm gonna need more than a Linked List of integers. I'm gonna need a Linked List of a class.
    But I only work with numbers.
    Maybe when I do something with a class, those things will make more sense.
    • Edited by GMainieri Sunday, July 05, 2009 11:16 AM
    Sunday, July 05, 2009 11:13 AM
  • i is a range variable, you don't have to declare it, it has no meaning outside the ordering method. Basically it's an element of the sequence you're trying to sort.
    The code above works here, so if it doesn't compile for you, please, paste here the error messages.

    David
    Sunday, July 05, 2009 11:15 AM
  • Hi!

    No, you don't have to declare it. If you look at the second example ("Lambdas are anonymous methods..."), you can see that "p" is a Person-type variable that is a parameter in the anon. method. The first example is absolutely the same. You don't have to declare it before the method, because in pList.OrderBy(p => p.Age) the "p" on the left side of the => operator is the declaration itself. The type is inferred by the compiler. If you use this method on a List<Person>, "p" will be a Person.
    Try the code, it should work. :)

    David
    • Edited by David Fulop Sunday, July 05, 2009 1:18 PM left side! :D
    Sunday, July 05, 2009 11:25 AM
  • Thanks Adil,

    I added the following to your code.

                LinkedList<int> lista2 = new LinkedList<int>();  
                foreach (var item in orderedResult)
                {
                    lista2.AddLast(item);
                    Console.WriteLine(item.ToString());
                }
    And now I have my sorted List.

    But I'm a PhD student, and performance is important for me, and this is a computational waste, because I've ordered item by item and then I've added item by item.

    I need to create the sorted List while I'm ordering, that is, I need to do so during the code.

    IEnumerable<int> orderedResult = from item in lista1
                                                 orderby item
                                                 select item;


    Another suggestion?
    Sunday, July 05, 2009 11:37 AM
  • Thanks Adil,

    I added the following to your code.

                LinkedList<int> lista2 = new LinkedList<int>();  
    
                foreach (var item in orderedResult)
    
                {
    
                    lista2.AddLast(item);
    
                    Console.WriteLine(item.ToString());
    
                }
    
    
    And now I have my sorted List.

    But I'm a PhD student, and performance is important for me, and this is a computational waste, because I've ordered item by item and then I've added item by item.

    I need to create the sorted List while I'm ordering, that is, I need to do so during the code.

    IEnumerable<int> orderedResult = from item in lista1
    
                                                 orderby item
    
                                                 select item;
    
    


    Another suggestion?

    Then I guess you can also use List<int> and then call the method Sort as shown below:

    List<int> list1 = new List<int>();
    list1.Add(23);
    list1.Add(17);
    list1.Sort();
    and this will sort your list :) and as far as I remember that uses quick sort algorithm behind the scene.
    Adil Mughal - MCP http://adilamughal.blogspot.com
    Sunday, July 05, 2009 11:46 AM
  • I don't think LinkedList<T> is the best choice here. Just use List<T>, and it has a Sort method. Much simpler. :p

    David
    • Proposed as answer by David Fulop Sunday, July 05, 2009 11:53 AM
    Sunday, July 05, 2009 11:53 AM
  • I don't think LinkedList<T> is the best choice here. Just use List<T>, and it has a Sort method. Much simpler. :p

    David

    For this example, 'List' is the smarter choice.

    But i'm going to need some functions of the 'LinkedList', like LinkedListNode, Find, AddLast, AddFirst, Min, Max, etc.
    Sunday, July 05, 2009 12:38 PM

  • Then I guess you can also use List<int> and then call the method Sort as shown below:

    List<int
    > list1 = new
     List<int
    >();
    list1.Add(23);
    list1.Add(17);
    list1.Sort();
    
    and this will sort your list :) and as far as I remember that uses quick sort algorithm behind the scene.
    Adil Mughal - MCP http://adilamughal.blogspot.com
    I knew about the sort function that List has. I think it's awesome and is that why i was trying to do the same with orderby.

    But i'm going to need some functions of the 'LinkedList', like LinkedListNode, Find, AddLast, AddFirst, Min, Max, etc.

    Sunday, July 05, 2009 12:43 PM
  • Hi!

    OrderBy and OrderByDescending are extension methods, and they expect some method (usually passed as lambda) to do the sorting. Try This:

    lista1.OrderByDescending(i => i);
    //or
    
    lista1.OrderBy(i => i);
    

    Please note that these methods don't sot the original list; they return a new, sorted one!

    Hope I could help!

    David


    I did this. Al least now is compiling. But still not sorting. It's sorting for you?
    Sunday, July 05, 2009 12:47 PM
  • Hi!

    No, you don't have to declare it. If you look at the second example ("Lambdas are anonymous methods..."), you can see that "p" is a Person-type variable that is a parameter in the anon. method. The first example is absolutely the same. You don't have to declare it before the method, because in pList.OrderBy(p => p.Age) the "p" on the right side of the => operator is the declaration itself. The type is inferred by the compiler. If you use this method on a List<Person>, "p" will be a Person.
    Try the code, it should work. :)

    David

    So, in my example, if I use

    lista1.orderby(p=>p);

    p will be a integer?
    Sunday, July 05, 2009 12:53 PM
  • Yes, absolutely. The type is inferred from the type parameter of the list.
    Sunday, July 05, 2009 1:19 PM
  • No, it's odd, but it doesn't work on LinkedList<>. :S (Previously I gave the list an ordered sequence, and it seemed fine, so I thought everything is OK...)
    However, there is a small trick we can use here. The logic is good, it works on Lists, so there must be a problem with the implementation of the LinkedList.
    This does the sorting:

    var orderedInts = lista1.ToList().OrderBy(i => i);

    The results type will be the same, so I think it'll serve your purpose.

    David



     

    Sunday, July 05, 2009 1:28 PM
  • No, it's odd, but it doesn't work on LinkedList<>. :S (Previously I gave the list an ordered sequence, and it seemed fine, so I thought everything is OK...)
    However, there is a small trick we can use here. The logic is good, it works on Lists, so there must be a problem with the implementation of the LinkedList.
    This does the sorting:

    var orderedInts = lista1.ToList().OrderBy(i => i);
    

    The results type will be the same, so I think it'll serve your purpose.

    David



    Ok. Now we are almost there.


    I did the following:

                var orderedints =lista1.ToList().OrderBy(p=>p);
                lista1.Clear();
                lista1 = new LinkedList<int>(orderedints);


    And worked. Now I have my lista1 sorted.

    but i still think we can do this in one step (therefore reducing CPU time).

    I tried something like this:

                lista1 = new LinkedList<int>(lista1.OrderBy(p => p));

    AND IT WORKED! We did it!

    Thanks David. You helped a lot. That is what i wanted.

    What do you think? This is the way to do using the minimum of CPU time? I think so, and you?
    Sunday, July 05, 2009 2:48 PM