|
Tell your lecturer from me that is an imbicile question. It is like saying which is fruitiest, apples or oranges. Both are useful, both have a specific job to do.
|
|
|
|
|
Plums.
There are just some times when you have to say plums.
|
|
|
|
|
Hey how many of you don't know about LinkedList<t>?[^]
It's been available since .NET 2!! And I missed it seems like it's not been discussed a lot. In fact many discussions omitted such important class.[^]
Any specific article which discuss and compare among various .NET collection classes now in terms of fetch-by-key/insert/remove/add/memory allocation/performance (polynomial time, linear time...etc) similar to cplusplus.com[^]
Gosh how the hell did I miss such important subject.
REF 1: MSDN Chapter 5 — Improving Managed Code Performance
- no reference of LinkedList but ListDictionary[^]
REF 2: That's more like it... read this comparison.[^] My question for this article is, "Insert" -- are they refering to "insert in middle of the list"? Of "Add" which adds to end of list? But, for example, for Dictionary<x,y> only supports "Add", there's no such thing as "Insert". "Insert" is supported by "IList<t>" however. Seems like article did not distinguish between add and insert.
REF 3: This seems to be the winner!![^]
Anything else?
Anyway, seems like 99% of applications we got by with Generic List/Dictionary (reasonable performance no op exceeds polynomial time) without LinkedList (all good except lookup). Does anybody has a good scenario as an example where they'd need LinkedList?
dev
modified on Wednesday, April 13, 2011 10:31 PM
|
|
|
|
|
It looks like you are the only person who hadn't noticed - why did it take you so long? 
Linked list are useful, yes. But there are other structures that are more useful, depending on your circumstances:
Queue[^]
Stack[^]
HashSet[^]
To name but three.
There is a list of all the generic collections under the System.Collections.Generic Namespace[^]
Real men don't use instructions. They are only the manufacturers opinion on how to put the thing together.
Manfred R. Bihy: "Looks as if OP is learning resistant."
|
|
|
|
|
"It looks like you are the only person who hadn't noticed - why did it take you so long?"
> because i first started with .NET 1 and didn't have more time at work than "Deliver"
dev
|
|
|
|
|
devvvy wrote: didn't have more time at work than "Deliver"
Get used to that!
Update your skills outside work - that way you may be able to get a better job: if you never upgrade your skills you pretty definitely won't!
Some employers are interested in keeping employees current because it helps the employee and the company. Others are just out to screw everything they can from you, and then discard the dried out husk "because you don't know the technology we are moving into". Get away from the later as fast as you can!
Real men don't use instructions. They are only the manufacturers opinion on how to put the thing together.
Manfred R. Bihy: "Looks as if OP is learning resistant."
|
|
|
|
|
err... mate, if you don't have an answer, try not to answer.
dev
|
|
|
|
|
Since you didn't post a question, I didn't answer it...
Real men don't use instructions. They are only the manufacturers opinion on how to put the thing together.
Manfred R. Bihy: "Looks as if OP is learning resistant."
|
|
|
|
|
|
The LinkedList that comes with .NET is rather annoying to work with IMO - when I 'need' (= want) a linked-list-like data structure I usually end up rolling my own.
Due to excessive space wastage and pointer chasing a linked list usually a poor choice anyway (Insert operations that are not at the beginning or end (that can both be rewritten to Add) are quite rare)
As an example, I've used a linked list (the "roll-my-own" version) to implement Lex-BFS, because it requires many insertions and deletion from "anywhere" in the list.
Then after some benchmarking, I found that a normal List was faster anyway - for the sizes of the instances I was working with (a couple of dozens of nodes).
I can't remember any examples of when I used a linked list and actually kept it.
|
|
|
|
|
Excessive waste of space? Disk? Or memory you mean?
dev
|
|
|
|
|
Anywhere you put them
That's usually RAM of course
|
|
|
|
|
And you used a memory profiler and found out that LinkedList consumes a lot more RAM than, say, a Dict?
dev
|
|
|
|
|
No, just add the bytes. I'm comparing to a normal List<T> btw.
On 32bit, every linked list node is 12 bytes overhead + 3*4 for next/prev/parent-list (for the .NET implementation - you could skip that parent list node) + sizeof(T) and then aligned to a multiple of 4. That's at least 28 bytes for every item in the list - no matter how long that list is.
For a List<T>, there is 12 bytes overhead + 4*4 for size/version/items/syncRoot + capacity * sizeof(T). The overheads are only incurred once and the capacity is at most twice the number of items, as the list grows to infinity the size per element approaches 2 * sizeof(T) which is 16 bytes per element for doubles and longs but usually 8 bytes or less.
|
|
|
|
|
ah I see your argument thanks
dev
|
|
|
|
|
Never had a need for it, other Collections are better suited to what I do. What I really like is HashSet which didn't show up until V3.5.
|
|
|
|
|
yes same here. Primarily because fetches are slower compared to Dict's
dev
|
|
|
|
|
Peter just commented - "Sparse Matrix", makes sense. I'm thinking back at what I've done last year or two trying to think of an example...
dev
|
|
|
|
|
"Does anybody has a good scenario as an example where they'd need LinkedList?"
It's useful when you don't know the size you'll need in advance, you're doing mostly sequential processing, and want fast performance. Insertions/deletions in the middle are fast. Its drawbacks are:
1. Memory overhead from pointers,
2. It's slow for randomly accessing elements in the middle, i.e. the nth element. Sorting is very slow.
3. No locality of reference, i.e. when you access element n, element n + 1 probably isn't in the cache, as it would be with an array or List.
You could use a List, which has fast indexed access (nth element) but there are some drawbacks:
1. When you exceed its initial allocation, it copies the WHOLE list to a new array. This is slow.
2. The new array is double the size of the previous one, so you may end up allocating twice the storage you need.
3. Insertions and deletions in the middle are slow, since many elements have to be moved.
You have to use the right tool for the job.
|
|
|
|
|
Yes I know if you don't know capacity ahead of time List would reallocate. What I am asking is, real life scenario.
I got by using Dictionary and List for the most part, some SortedDictionary - and all done within polynomial time.
Never had a business/tech scenario where I'd need link list with slow retrieval time.
For instance, trade tables, dictionary with tradeId as key be better.
Or execution queue - also been using dictionary with execId as key. Never a linkedList.
Any real/practical scenario?
dev
|
|
|
|
|
If you're wanting to hold a sparse matrix, a linked list is an ideal structure. I've used them before to hold massively dimensioned matrices (e.g. for chemical engineering based systems). That was in C++ though - I am less than whelmed by the .NET implementation.
|
|
|
|
|
hum... good point... which brings me to the thought that there's no such thing as sparse list.
thanks
dev
|
|
|
|
|
"Any real/practical scenario?"
In an upcoming project, I have a data stream coming in, and I "clump" elements for later processing. I don't know in advance how many clumps I'm going to have, and the later processing is only going to go through them sequentially.
I'm planning on using a linked list for this.
|
|
|
|
|
hum... sequential access - why not a SortedList<int, Stream>? with key "Int" (for example DataId)
dev
|
|
|
|
|
1. A SortedList maintains an array for the elements like the generic List, so has the same disadvantages: The WHOLE list must be recopied every time it exceeds its capacity, which is slow, and which may waste space.
2. In addition, the SortedList maintains another copy of the the elements' keys for indexing, which takes even more space.
3. In my case, I don't need sorting, so this would be overhead for me, both in the time to keep it sorted, and in the extra memory required for the indexing.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
