LinkedList in C# good case to use them

  • Thread starter Thread starter LP
  • Start date Start date
L

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?
 
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.
 
that could be easily done with an ArrayList.

Nicholas Paldino said:
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]
- (e-mail address removed)

LP said:
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?
Click to expand...
Click to expand...
 
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


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?
Click to expand...

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.
 
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.
 
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]
- (e-mail address removed)


LP said:
that could be easily done with an ArrayList.

in
message news:[email protected]...
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]
- (e-mail address removed)

LP said:
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?
Click to expand...
Click to expand...
Click to expand...
 
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.
 
Basiclly my response was that any functionality LinkedList you need
could be
found under System.Collections
Click to expand...

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).
 
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.
 
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
 
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.
 
Usually when asked a question about implementing something that is simply not
done (or needed) much any more I say, "I can't remember how to implement that,
but I have many good reference books on algorithms and understand where and when
such a thing should be done."

It sounds like you were interviewed by a C/C++ programmer who wanted to show you
how much he/she knew about programming, or by a person who didn't know much
about the .NET framework.
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.
Click to expand...

Otis Mukinfus
http://www.otismukinfus.com
 
Back
Top