Sorting in LinkedList<>

[martin-g]

Hi.

Mostly I program in C++, and I'm not fluent in C# and .NET. In my last
project I began to use LinkedList<and suddenly noticed that can't
find a way to sort it. Does it mean I must implement sorting for
LinkedList<myse lf?

Thanks in advance

Martin

[pvdg42]

"martin-g" <ma******@mail. ruwrote in message
news:11******** **************@ f1g2000cwa.goog legroups.com...

Hi.

Mostly I program in C++, and I'm not fluent in C# and .NET. In my last
project I began to use LinkedList<and suddenly noticed that can't
find a way to sort it. Does it mean I must implement sorting for
LinkedList<myse lf?

Thanks in advance

Martin

So it would appear.
Perhaps this article would be helpful to you:

http://msdn2.microsoft.com/en-us/library/6tc79sx1.aspx

[martin-g]

pvdg42 wrote:

So it would appear.
Perhaps this article would be helpful to you:

http://msdn2.microsoft.com/en-us/library/6tc79sx1.aspx

Thank you for answer. That's really wild... Looking through the article
I couldn't eventually select the collection class of my need. On the
one hand I want an item to be added to the container at constant time
at any position, so must use LinkeList<>. On the other hand I want to
sort the container, so I must use List<>. FCL has really strange
container organization... Only now I understood: I love STL very much...

[Brian Gideon]

martin-g wrote:

pvdg42 wrote:

So it would appear.
Perhaps this article would be helpful to you:

http://msdn2.microsoft.com/en-us/library/6tc79sx1.aspx

Thank you for answer. That's really wild... Looking through the article
I couldn't eventually select the collection class of my need. On the
one hand I want an item to be added to the container at constant time
at any position, so must use LinkeList<>. On the other hand I want to
sort the container, so I must use List<>. FCL has really strange
container organization... Only now I understood: I love STL very much...

So you want constant time insertions and the ability to sort the
collection. The List<collection sounds like a good match.
Insertions are usually O(1) and you can call the Sort method to sort
the collection. Have you looked at SortedDictionar y yet? Insertions
are a bit slower, but the items are always stored in order so there's
no need to perform a separate sort operation.

Brian

[Jon Skeet [C# MVP]]

Brian Gideon <br*********@ya hoo.comwrote:

Thank you for answer. That's really wild... Looking through the article
I couldn't eventually select the collection class of my need. On the
one hand I want an item to be added to the container at constant time
at any position, so must use LinkeList<>. On the other hand I want to
sort the container, so I must use List<>. FCL has really strange
container organization... Only now I understood: I love STL very much...

So you want constant time insertions and the ability to sort the
collection. The List<collection sounds like a good match.
Insertions are usually O(1) and you can call the Sort method to sort
the collection. Have you looked at SortedDictionar y yet? Insertions
are a bit slower, but the items are always stored in order so there's
no need to perform a separate sort operation.

Insertions into a List<are certainly *not* O(1) in general. When
adding to the end of the list, the additions will be cheap if there's
enough room in the buffer. Otherwise, it requires a copy of all the
items after the new entry (or all the items if a new buffer is
required).

The MSDN docs say it's an O(n) operation too.

--
Jon Skeet - <sk***@pobox.co m>
http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too

[Brian Gideon]

Jon wrote:

Brian Gideon <br*********@ya hoo.comwrote:

Thank you for answer. That's really wild... Looking through the article
I couldn't eventually select the collection class of my need. On the
one hand I want an item to be added to the container at constant time
at any position, so must use LinkeList<>. On the other hand I want to
sort the container, so I must use List<>. FCL has really strange
container organization... Only now I understood: I love STL very much...

So you want constant time insertions and the ability to sort the
collection. The List<collection sounds like a good match.
Insertions are usually O(1) and you can call the Sort method to sort
the collection. Have you looked at SortedDictionar y yet? Insertions
are a bit slower, but the items are always stored in order so there's
no need to perform a separate sort operation.

Insertions into a List<are certainly *not* O(1) in general. When
adding to the end of the list, the additions will be cheap if there's
enough room in the buffer. Otherwise, it requires a copy of all the
items after the new entry (or all the items if a new buffer is
required).

The MSDN docs say it's an O(n) operation too.

Yeah, wow, I'm not sure what I was thinking when I wrote that. In
fact, my whole post doesn't make any since...beginni ng, middle, and
end. That's one of those you just wish you could take back. Ya think
I can talk Google into deleting that one :)

[Bruce Wood]

Jon wrote:

Insertions into a List<are certainly *not* O(1) in general. When
adding to the end of the list, the additions will be cheap if there's
enough room in the buffer. Otherwise, it requires a copy of all the
items after the new entry (or all the items if a new buffer is
required).

The MSDN docs say it's an O(n) operation too.

So, List<isn't a linked list, it's an array...? I suppose it would
have to be, if it's meant to be the "first choice" collection for
general use.

Does Framework 2.0 even provide a true link list? Dumb question, I
know, but we're still on 1.1.... :-)

[Lucian Wischik]

"Bruce Wood" <br*******@cana da.comwrote:

>Does Framework 2.0 even provide a true link list?

LinkedList<T>, which was already mentioned earlier in this thread...

[martin-g]

Bruce Wood wrote:

So, List<isn't a linked list, it's an array...? I suppose it would
have to be, if it's meant to be the "first choice" collection for
general use.

Yes, List<is based on array.

Does Framework 2.0 even provide a true link list? Dumb question, I
know, but we're still on 1.1.... :-)

I was on 1.1 too, and decided to turn to 2.0 only for its LinkedList<>
generic collection. And some time later realized it's not the linked
list of my dreams.

[Jon Skeet [C# MVP]]

Jon Skeet [C# MVP] wrote:

Well, System.Collecti ons.LinkedList still exists, and there's a generic
LinkedList as well.

I do apologise - of course there isn't a System.Collecti ons.LinkedList,
I don't know what I was thinking of...

Jon