Why no LinkedList?

[cody]

Why isn't there a LinkedList in .NET?
Was the reason that the mark&sweep GC algorithm has problems with heavily
linked data?

A LinkedList is very important is you have huge lists and append a new
element you just create this objekt and set a reference in contrast to an
arraylist where you have to copy the whole array and create a new one with
the double size.

Additionally removing elements in an ArrayList is a very expensive
operation: all elements behind the removed element has to be copied to fill
the hole. With LinkedList you just have to relink to element to remove
everything between them.

I was hoping that Whidbey would provide a LinkedList but I looked in the
beta and there was nothing.

So what are the reasons behind this decision?

--
cody

[Freeware, Games and Humor]
www.deutronium.de.vu || www.deutronium.tk

[William Ryan eMVP]

Re: Why no LinkedList?

Cody:

Behind the scenes they are used all over the place in .NET and you can
easily code one yourself. Back in the old days of C++ I had to write my own
so I did the same in C# just for fun. If you search google for Linked LIst
C# there are hundreds of examples...

http://csharpcomputing.com/Tutorials/Lesson9.htm

Maybe I"m missing your point with ArrayLists though...they don't necessitate
the use of an Array at all, so I'm probably misunderstandin g your point.
Can you explain that part a little more b/c I don't think I follow you.
"cody" <please_dont.sp am.deutronium@g mx.de> wrote in message
news:#cYg0qCGEH A.3724@TK2MSFTN GP11.phx.gbl...[color=blue]
> Why isn't there a LinkedList in .NET?
> Was the reason that the mark&sweep GC algorithm has problems with heavily
> linked data?
>
> A LinkedList is very important is you have huge lists and append a new
> element you just create this objekt and set a reference in contrast to an
> arraylist where you have to copy the whole array and create a new one with
> the double size.
>
> Additionally removing elements in an ArrayList is a very expensive
> operation: all elements behind the removed element has to be copied to[/color]
fill[color=blue]
> the hole. With LinkedList you just have to relink to element to remove
> everything between them.
>
> I was hoping that Whidbey would provide a LinkedList but I looked in the
> beta and there was nothing.
>
> So what are the reasons behind this decision?
>
> --
> cody
>
> [Freeware, Games and Humor]
> www.deutronium.de.vu || www.deutronium.tk
>
>[/color]

[cody]

Re: Why no LinkedList?

> Behind the scenes they are used all over the place in .NET and you can[color=blue]
> easily code one yourself. Back in the old days of C++ I had to write my[/color]
own[color=blue]
> so I did the same in C# just for fun. If you search google for Linked LIst
> C# there are hundreds of examples...[/color]

I know how to program a LinkedList. The Question was why isn't there a
LinkedList in the .NET framework?
[color=blue]
> Maybe I"m missing your point with ArrayLists though...they don't[/color]
necessitate[color=blue]
> the use of an Array at all, so I'm probably misunderstandin g your point.
> Can you explain that part a little more b/c I don't think I follow you.[/color]

So why it is called *Array*List then? It is called this way because it uses
an Array as internal data structure.

--
cody

[Freeware, Games and Humor]
www.deutronium.de.vu || www.deutronium.tk

[Willy Denoyette [MVP]]

Re: Why no LinkedList?

The beta of Whidbey, isn't released yet, so you must have been looking
somewhere else.
Anyway, a parameterized LinkedList is included in the VS2005 Technology
Preview.

Willy.

"cody" <please_dont.sp am.deutronium@g mx.de> wrote in message
news:%23cYg0qCG EHA.3724@TK2MSF TNGP11.phx.gbl. ..[color=blue]
> Why isn't there a LinkedList in .NET?
> Was the reason that the mark&sweep GC algorithm has problems with heavily
> linked data?
>
> A LinkedList is very important is you have huge lists and append a new
> element you just create this objekt and set a reference in contrast to an
> arraylist where you have to copy the whole array and create a new one with
> the double size.
>
> Additionally removing elements in an ArrayList is a very expensive
> operation: all elements behind the removed element has to be copied to
> fill
> the hole. With LinkedList you just have to relink to element to remove
> everything between them.
>
> I was hoping that Whidbey would provide a LinkedList but I looked in the
> beta and there was nothing.
>
> So what are the reasons behind this decision?
>
> --
> cody
>
> [Freeware, Games and Humor]
> www.deutronium.de.vu || www.deutronium.tk
>
>[/color]

[William Ryan eMVP]

Re: Why no LinkedList?

> I know how to program a LinkedList. The Question was why isn't there a[color=blue]
> LinkedList in the .NET framework?[/color]
There's a lot of stuff that isn't implemented in the Framework yet. Your
personal wish might be the linked list but many people have different ones.
MS didn't have time to get everything in and doesn't make any pretense that
the framework is complete. I can think of 25 API calls that I would like to
have implemented and could make a good argument that similar functionality
is already provided so why not these. The answer is the same, the framework
isn't complete and you you aren't prohibited from implementing it on your
own.

I guess you don't program on the Compact Framework b/c there's a whole lot
more there that isn't yet implemented.
[color=blue]
> So why it is called *Array*List then? It is called this way because it[/color]
uses[color=blue]
> an Array as internal data structure.[/color]

Guess you didn't have time to read the help file on it ;-). It's called an
ArrayList because it uses an Array and implements the IList interface.

Also, I just checked and a linked list is supposed to be implemented in the
next version. The beta isn't scheduled to be released for a few months so
it had to have been an Alpha build and those are changing quickly. My
first alpha I got about a month and a half ago is Wayyy different from the
alpha I got last week.

Cheers,

Bill
"cody" <please_dont.sp am.deutronium@g mx.de> wrote in message
news:u0iZ7MDGEH A.3880@TK2MSFTN GP10.phx.gbl...[color=blue][color=green]
> > Behind the scenes they are used all over the place in .NET and you can
> > easily code one yourself. Back in the old days of C++ I had to write my[/color]
> own[color=green]
> > so I did the same in C# just for fun. If you search google for Linked[/color][/color]
LIst[color=blue][color=green]
> > C# there are hundreds of examples...[/color]
>[/color]
[color=blue]
>[color=green]
> > Maybe I"m missing your point with ArrayLists though...they don't[/color]
> necessitate[color=green]
> > the use of an Array at all, so I'm probably misunderstandin g your point.
> > Can you explain that part a little more b/c I don't think I follow you.[/color]
>[/color]
[color=blue]
>
> --
> cody
>
> [Freeware, Games and Humor]
> www.deutronium.de.vu || www.deutronium.tk
>
>[/color]

[Jon Skeet [C# MVP]]

Re: Why no LinkedList?

William Ryan eMVP <bill@NoSp4m.de vbuzz.com> wrote:[color=blue][color=green]
> > So why it is called *Array*List then? It is called this way because it
> > uses an Array as internal data structure.[/color]
>
> Guess you didn't have time to read the help file on it ;-). It's called an
> ArrayList because it uses an Array and implements the IList interface.[/color]

Um, that's basically just what Cody said. So using an ArrayList *does*
necessitate using an array (internally) contrary to your previous
assertion. I don't believe Cody was ever suggesting that the *user* of
an ArrayList needs to use an array (directly) themselves - only that
ArrayList *does* use an array, and therefore suffers when it needs to
be copied.

--
Jon Skeet - <skeet@pobox.co m>

http://www.pobox.com/~skeet

If replying to the group, please do not mail me too

[codymanix]

Re: Why no LinkedList?

> > > So why it is called *Array*List then? It is called this way because it[color=blue][color=green][color=darkred]
> > > uses an Array as internal data structure.[/color]
> >
> > Guess you didn't have time to read the help file on it ;-). It's called[/color][/color]
an[color=blue][color=green]
> > ArrayList because it uses an Array and implements the IList interface.[/color]
>
> Um, that's basically just what Cody said. So using an ArrayList *does*
> necessitate using an array (internally) contrary to your previous
> assertion. I don't believe Cody was ever suggesting that the *user* of
> an ArrayList needs to use an array (directly) themselves - only that
> ArrayList *does* use an array, and therefore suffers when it needs to
> be copied.[/color]


Thats exactly what I said :)

--
cody

Freeware Tools, Games and Humour
http://www.deutronium.de.vu || http://www.deutronium.tk

[codymanix]

Re: Why no LinkedList?

> The beta of Whidbey, isn't released yet, so you must have been looking[color=blue]
> somewhere else.
> Anyway, a parameterized LinkedList is included in the VS2005 Technology
> Preview.[/color]


That is good.

--
cody

Freeware Tools, Games and Humour
http://www.deutronium.de.vu || http://www.deutronium.tk

[codymanix]

Re: Why no LinkedList?

> > I know how to program a LinkedList. The Question was why isn't there a[color=blue][color=green]
> > LinkedList in the .NET framework?[/color]
>
> There's a lot of stuff that isn't implemented in the Framework yet. Your
> personal wish might be the linked list but many people have different[/color]
ones.

I never said that is it my Personal urgently wish to have a LinkedList. Sure
it would be useful but I say it again:
My question was only *Why isn't there a LinkedList*. I thought that there
could be a special reason. It could be that
the GC algorithm has problems with heavily linked data or something.

I was wondering because other frameworks mostly provides *only* a LinkedList
and _no_ ArrayList.
So I thought there had to be a special reason why .NET did it the other way
around.

--
cody

Freeware Tools, Games and Humour
http://www.deutronium.de.vu || http://www.deutronium.tk

[Ravichandran J.V.]

Re: Why no LinkedList?

"I was wondering because other frameworks mostly provides *only* a
LinkedList and _no_ ArrayList."

Which other framework(s) are you talking about ?


with regards,


J.V.Ravichandra n
- http://www.geocities.com/
jvravichandran
- http://www.411asp.net/func/search?
qry=Ravichandra n+J.V.&cob=aspn etpro
- http://www.southasianoutlook.com
- http://www.MSDNAA.Net
- http://www.csharphelp.com
- http://www.poetry.com/Publications/
display.asp?ID= P3966388&BN=999 &PN=2
- Or, just search on "J.V.Ravichandr an"
at http://www.Google.com

*** Sent via Developersdex http://www.developersdex.com ***
Don't just participate in USENET...get rewarded for it!

[William Ryan eMVP]

Re: Why no LinkedList?

<<you have to copy the whole array and create a new one with the double
size.>> this is the part that threw me and I said I may have misunderstood
the point. "you" as the programmer doesn't have to use an array to do
anything with the arraylist just as I don't have to implement a link list to
use a Datareader although it does behind the scenes. I see now that he
meant you in a different context, hence that's why the whole thing seemed
confusing.

I guess it was just a semantical thing..sorry for any confusion.

Cheers,

Bill
"Jon Skeet [C# MVP]" <skeet@pobox.co m> wrote in message
news:MPG.1ad721 41854f095b98a54 d@msnews.micros oft.com...[color=blue]
> William Ryan eMVP <bill@NoSp4m.de vbuzz.com> wrote:[color=green][color=darkred]
> > > So why it is called *Array*List then? It is called this way because it
> > > uses an Array as internal data structure.[/color]
> >
> > Guess you didn't have time to read the help file on it ;-). It's called[/color][/color]
an[color=blue][color=green]
> > ArrayList because it uses an Array and implements the IList interface.[/color]
>
> Um, that's basically just what Cody said. So using an ArrayList *does*
> necessitate using an array (internally) contrary to your previous
> assertion. I don't believe Cody was ever suggesting that the *user* of
> an ArrayList needs to use an array (directly) themselves - only that
> ArrayList *does* use an array, and therefore suffers when it needs to
> be copied.
>
> --
> Jon Skeet - <skeet@pobox.co m>
> http://www.pobox.com/~skeet
> If replying to the group, please do not mail me too[/color]