Is that true there are no Linked lists in .NET?

[martin-g]

Hi.

I have realized some heavy algorithm which works on ArrayList of
strings. It works slow because of a lot of insertions and deletions at
arbitrary positions in the list. Now I really need an ADT based on
linked list data structure, but can't find any appropriate collection
in FCL. Does it mean I must realize such an ADT myself? And what about
sorting, I also need sorting in my list, so I must realize it too? It
didn't seem true, and I decided to ask about it here.

Thanks in advance

Martin

 

[Peter Duniho]

[...]
Now I really need an ADT based on
linked list data structure, but can't find any appropriate collection
in FCL. Does it mean I must realize such an ADT myself? And what about
sorting, I also need sorting in my list, so I must realize it too? It
didn't seem true, and I decided to ask about it here.

I don't know what an "ADT" or "FCL" is, but how about the LinkedList class?
If you want it sorted, how about the SortedList class?

Pete

 

[Jon Skeet [C# MVP]]

I have realized some heavy algorithm which works on ArrayList of
strings. It works slow because of a lot of insertions and deletions at
arbitrary positions in the list. Now I really need an ADT based on
linked list data structure, but can't find any appropriate collection
in FCL. Does it mean I must realize such an ADT myself? And what about
sorting, I also need sorting in my list, so I must realize it too? It
didn't seem true, and I decided to ask about it here.

..NET 2.0 has a generic LinkedList class. There was nothing similar in
the framework before 2.0 as far as I know. However, there are plenty of
3rd party collections libraries around if you're stuck on 1.1.

 

[martin-g]

I don't know what an "ADT" or "FCL" is, but how about the LinkedList class?
If you want it sorted, how about the SortedList class?

"SortedList" class doesn't match, 'cause it seems to be realized using
binary search tree. I don't need my collection to be sorted any time,
instead I need constant time insertions and removals at any position.
Insertion time in "SortedList" is logarithmic.
"LinkedList" is quite another matter. I haven't heard about it, there
is no "LinkedList" class in my version of .NET. What's your .NET's
version?
There is also "ListDictionary" class in "Specialized" subnamespace, but
it doesn't fit too, as it's a singly linked, and I need a doubly linked
list. Besides there is a recomendation to use it for collections with
10 elements or less, which is unacceptible in my case.

Thanks

 

[martin-g]

.NET 2.0 has a generic LinkedList class. There was nothing similar in
the framework before 2.0 as far as I know. However, there are plenty of
3rd party collections libraries around if you're stuck on 1.1.

Thanks, I've found some source. Unfortunately it doesn't support
sorting. Seems I'll have to realize it myself.

 

[Peter Duniho]

"SortedList" class doesn't match, 'cause it seems to be realized using
binary search tree. I don't need my collection to be sorted any time,
instead I need constant time insertions and removals at any position.
Insertion time in "SortedList" is logarithmic.

I'm not sure what it means to say "I also need sorting in my list" but to
not want the list to be sorted at any time. As long as the list need not
always be in a sorted state, it seems like you can just use the sorting
method of your preference at the appropriate time, with whatever basic data
structure you started with.

..NET does offer basic sort functionality that you can use for that. For
that matter, it would be trivial to implement a quicksort from scratch on
the LinkedList class.

"LinkedList" is quite another matter. I haven't heard about it, there
is no "LinkedList" class in my version of .NET. What's your .NET's
version?

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

Hope that helps.

Pete