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.

 

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

Thanks David,

Is something like this that i'm looking for.

But is not working, how should i declare this variable 'i'?

Answer 5

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.

Answer 6

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

Answer 7

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

Answer 8

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?

Answer 9

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

Answer 10

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

Answer 11

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.

Answer 12

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.

Answer 13

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?

Answer 14

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?

Answer 15

Yes, absolutely. The type is inferred from the type parameter of the list.

Answer 16

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



 

Answer 17

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?