LinkedList in C# good case to use them

[LP]

Hi,

I was asked at the tech screening what the linked list was which I answered
with "academic" definition. Then a guy asked me how I would implement a
linked list in C# and what would be a good case for linked list.
I could not think of any .NET class that implement true linked list (I don't
think there is any). But, I guess one could implement their own linked list.
I couldn't think of a good case when it would be absolutely necessary
though. I mean System.Collections provides enough implementations to store
and access data any way you could imagine.
Is it fair to say that linked list is a thing of C days before framework
classes?

[Nicholas Paldino [.NET/C# MVP]]

LP,

No, I don't think this is the cast. Generally, for my purposes, linked
lists are good when the majority of operations you have to perform are
traversals through the list, as well as adding elements to the end or to the
beginning. However, they absolutely suck as the grow larger for things like
sorting, or searching for content.

It's all up to you, and the situation you are faced with.

Hope this helps.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

"LP" <[e-mail]> wrote in message
news:eW**************@TK2MSFTNGP15.phx.gbl...

Hi,

I was asked at the tech screening what the linked list was which I
answered
with "academic" definition. Then a guy asked me how I would implement a
linked list in C# and what would be a good case for linked list.
I could not think of any .NET class that implement true linked list (I
don't
think there is any). But, I guess one could implement their own linked
list.
I couldn't think of a good case when it would be absolutely necessary
though. I mean System.Collections provides enough implementations to store
and access data any way you could imagine.
Is it fair to say that linked list is a thing of C days before framework
classes?

[LP]

that could be easily done with an ArrayList.

"Nicholas Paldino [.NET/C# MVP]" <mv*@spam.guard.caspershouse.com> wrote in
message news:u6**************@tk2msftngp13.phx.gbl...

LP,

No, I don't think this is the cast. Generally, for my purposes, linked lists are good when the majority of operations you have to perform are
traversals through the list, as well as adding elements to the end or to the beginning. However, they absolutely suck as the grow larger for things like sorting, or searching for content.

It's all up to you, and the situation you are faced with.

Hope this helps.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

"LP" <[e-mail]> wrote in message
news:eW**************@TK2MSFTNGP15.phx.gbl...

Hi,

I was asked at the tech screening what the linked list was which I
answered
with "academic" definition. Then a guy asked me how I would implement a
linked list in C# and what would be a good case for linked list.
I could not think of any .NET class that implement true linked list (I
don't
think there is any). But, I guess one could implement their own linked
list.
I couldn't think of a good case when it would be absolutely necessary
though. I mean System.Collections provides enough implementations to store and access data any way you could imagine.
Is it fair to say that linked list is a thing of C days before framework
classes?

[Samuel R. Neff]

Linked Lists are good when the number of items in the list are small
and thus looping through the entire list is faster than looking up a
single item through another method (i.e., binary search on sorted list
or generation of hashcode for hashtable).

System.Collections.Specialized.ListDictionary implements a Linked List
for such occasions.

System.Collections.Specialized.HybridDictionary is a wrapper class
that uses a LinkedList for small lists and a Hashtable when the list
gets larger than 8 items. However, it has some overhead in the
wrapper so if you know ahead of time what size your list will be, it's
better to just use the appropriate list (the hybrid is good for cases
where most of the time the list will be very small but there is a
chance the list could grow bigger).

Also some classes use linked lists internally such as
MulticastDelegate and Exception.
Not sure what the interviewer would want to hear but when I've asked
similar questions of interviewees (which is only when they bring up
data structures) I usually want to hear that they would never write
one themselves. However, each interviewer could be looking for a
totally different answer, so it's not really a good question (my
opinion of course).

Best regards,

Sam
On Mon, 21 Mar 2005 11:05:46 -0500, "LP" <[e-mail]> wrote:

Hi,

I was asked at the tech screening what the linked list was which I answered
with "academic" definition. Then a guy asked me how I would implement a
linked list in C# and what would be a good case for linked list.
I could not think of any .NET class that implement true linked list (I don't
think there is any). But, I guess one could implement their own linked list.
I couldn't think of a good case when it would be absolutely necessary
though. I mean System.Collections provides enough implementations to store
and access data any way you could imagine.
Is it fair to say that linked list is a thing of C days before framework
classes?

B-Line is now hiring one Washington D.C. area VB.NET
developer for WinForms + WebServices position.
Seaking mid to senior level developer. For
information or to apply e-mail resume to
sam_blinex_com.

[Ajay Kalra]

I have never had the need to use it ever since I started using
collection in STL/C++.

According to MSDN docs, ListDictionary class implements IDictionary
with a singly linked list. Since look ups will be expensive if the
collection is large, it points out to use it for 10 items or less.

In general, you can look at System.Collections.Specialized for various
collections.

-----
Ajay Kalra
aj*******@yahoo.com

[Nicholas Paldino [.NET/C# MVP]]

Yes, it could, but you have to look at the performance implications.
With an array list, adding an item to the end of the list is pretty much the
same as a linked list (with the exception of possibly allocating more memory
and copying the contents over). However, adding an item to the beginning of
the list, or anywhere but the end requires the contents of the array to be
copied completely past the point of insertion. With linked lists, this is a
constant operation.

So while yes, you can do it with an ArrayList, actually doing it with
that could have different performance results.

--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com
"LP" <[e-mail]> wrote in message
news:OR**************@TK2MSFTNGP10.phx.gbl...

that could be easily done with an ArrayList.

"Nicholas Paldino [.NET/C# MVP]" <mv*@spam.guard.caspershouse.com> wrote
in
message news:u6**************@tk2msftngp13.phx.gbl...

LP,

No, I don't think this is the cast. Generally, for my purposes,

linked

lists are good when the majority of operations you have to perform are
traversals through the list, as well as adding elements to the end or to

the

beginning. However, they absolutely suck as the grow larger for things

like

sorting, or searching for content.

It's all up to you, and the situation you are faced with.

Hope this helps.
--
- Nicholas Paldino [.NET/C# MVP]
- mv*@spam.guard.caspershouse.com

"LP" <[e-mail]> wrote in message
news:eW**************@TK2MSFTNGP15.phx.gbl...

> Hi,
>
> I was asked at the tech screening what the linked list was which I
> answered
> with "academic" definition. Then a guy asked me how I would implement a
> linked list in C# and what would be a good case for linked list.
> I could not think of any .NET class that implement true linked list (I
> don't
> think there is any). But, I guess one could implement their own linked
> list.
> I couldn't think of a good case when it would be absolutely necessary
> though. I mean System.Collections provides enough implementations to store > and access data any way you could imagine.
> Is it fair to say that linked list is a thing of C days before
> framework
> classes?
>
>

[LP]

Basiclly my response was that any functionality LinkedList you need could be
found under System.Collections (which includes Specialized). Not sure if it
was what he wanted to hear.
I wonder much how much performance you would gain with your own
implementation as oppesed to framework class. Would it be noticiable to the
user and would it justify the effort and time.

[Ajay Kalra]

> Basiclly my response was that any functionality LinkedList you need
could be

found under System.Collections

I think this is fine. As you mentioned, a lot of it is subjective. I
would prefer to go with what is provided in framework than implement on
my own, unless framework classes lacked something (performance etc).

------
Ajay Kalra
aj*******@yahoo.com

[Bruce Wood]

I would agree with your answer. To expand on what I would consider the
correct answer to the question, the data structure you use depends upon
three things:

1. How you need to get at the data. Do you need to quickly locate
particular items, or are you always iterating over the list?
2. The ratio of reads to writes. Are you frequently modifying the list?
How? Are inserts only at the end, or do you have frequent inserts /
deletes in the middle of the list?
3. Do you need to maintain order? If you are iterating over the list,
do you care about the order? Do you need to maintain the original
insertion order, or some other order?

Before .NET, my two favourite data structures were linked list and hash
table. Now, with .NET I use ArrayList and Hashtable. Of course, this is
because most of my data requirements fit into one of two categories: 1)
Collections with high insert / delete rates but for which order is
unimportant; 2) Collections that are read far, far more often than
they're written, where element order may or may not be important. Of
course, the corresponding structures are Hashtable and ArrayList,
respectively.

As far as "writing my own", any interviewee who said that they'd prefer
to write their own would, receive a big, black mark in my estimation.
Yes, there are some specialized situations in which writing your own
data structure can improve design and perhaps even performance, but
IMHO they are few and far between. The collection structures already
provided in the .NET Framework cover 95% of your collection needs. For
the most part, the "I'll write it myself" mindset comes from being
either young and inexperienced, or from an inflated sense of
self-importance. It's the "I'm facing a problem that no one else has
ever faced" or the "I'm smarter than the guys in Redmond who put these
classes together" (or the combination "The guys in Redmond could never
have anticipated the special needs of my app.") way of thinking.

By this I don't mean that it's never right to roll your own data
structure. Sometimes it really is the case that the guys in Redmond
didn't anticipate a particular need and you have to build your own.
However, 95% of the time it's not the case.

[Brian Gideon]

LP,

The Chain of Command pattern from the GOF is an excellent case where
linked lists are used frequently. Stacks and queues are often
implemented with linked lists, but in most cases standard arrays offer
better performance.

The data structures in System.Collections are usually sufficient. I've
found myself wanting a red black tree in the past. But, that's the
only critical omission in my opinion.

I really don't understand why this is such a popular interview
question. I mean, why ask about linked lists without following up with
other data structures? The linked list certainly isn't the magical
data structure that solves all problems.

Brian
LP wrote:

Hi,

I was asked at the tech screening what the linked list was which I
answered with "academic" definition. Then a guy asked me how I
would implement a linked list in C# and what would be a good case
for linked list. I could not think of any .NET class that
implement true linked list (I don't think there is any). But, I
guess one could implement their own linked list. I couldn't think
of a good case when it would be absolutely necessary though. I mean
System.Collections provides enough implementations to store and
access data any way you could imagine. Is it fair to say that
linked list is a thing of C days before framework classes?

[LP]

I agree with your assessment.
For the most part I have a philosophy to utilize framework classes as much
as possible. That's one of the biggest reasons why .NET framework has been
becoming so popular, because of the richness of the class libraries it
provides. If something is missing from framework then my all means write
your own or by 3rd party.
As far as performance....As far I know HashTable uses highly optimized
algorithm to store and retrieve items based on key. If I can write my own
even faster implementation I would be interviewing with Microsoft.
Also I am not sure what interviewer indented to get out of this question.
Was it my knowledge of what the LinkedList was or if I could implement one.
Either way I don't think it's relevant. Simply knowing what the LinkedList
and how to implement one doesn't make one a good programmer. Ability to
solve problems using ones knowledge that what makes a good programmer. The
more relevant question could be something like: "You need to store customers
information in sequential manner and you need to be able to add or remove
new customer from the list", how would you implement it? Either ArrayList or
writing my own LinkedList implementation would be acceptable answers.

"Bruce Wood" <br*******@canada.com> wrote in message
news:11*********************@z14g2000cwz.googlegro ups.com...

I would agree with your answer. To expand on what I would consider the
correct answer to the question, the data structure you use depends upon
three things:

1. How you need to get at the data. Do you need to quickly locate
particular items, or are you always iterating over the list?
2. The ratio of reads to writes. Are you frequently modifying the list?
How? Are inserts only at the end, or do you have frequent inserts /
deletes in the middle of the list?
3. Do you need to maintain order? If you are iterating over the list,
do you care about the order? Do you need to maintain the original
insertion order, or some other order?

Before .NET, my two favourite data structures were linked list and hash
table. Now, with .NET I use ArrayList and Hashtable. Of course, this is
because most of my data requirements fit into one of two categories: 1)
Collections with high insert / delete rates but for which order is
unimportant; 2) Collections that are read far, far more often than
they're written, where element order may or may not be important. Of
course, the corresponding structures are Hashtable and ArrayList,
respectively.

As far as "writing my own", any interviewee who said that they'd prefer
to write their own would, receive a big, black mark in my estimation.
Yes, there are some specialized situations in which writing your own
data structure can improve design and perhaps even performance, but
IMHO they are few and far between. The collection structures already
provided in the .NET Framework cover 95% of your collection needs. For
the most part, the "I'll write it myself" mindset comes from being
either young and inexperienced, or from an inflated sense of
self-importance. It's the "I'm facing a problem that no one else has
ever faced" or the "I'm smarter than the guys in Redmond who put these
classes together" (or the combination "The guys in Redmond could never
have anticipated the special needs of my app.") way of thinking.

By this I don't mean that it's never right to roll your own data
structure. Sometimes it really is the case that the guys in Redmond
didn't anticipate a particular need and you have to build your own.
However, 95% of the time it's not the case.