Linked Lists

I have heard about Linked List forever and a day now and still don't know rightly what they are or how they are effiecent....

Would someone clue me in....

Look here, I explain the idea of linked lists a bit down the discussion.

Linked lists offer fast linear traversal, constant-time insertion and deletion at any known point in the sequence, but a lack of random access. Also, you have to decide whether you want splicing or the length query in constant time, the other one will be linear time. Sorting is O(n²) because of the lack of random access, and binary search is not possible, so that searching will always be linear.

Ok, my c/c++ isn't anywhere at the working level of writing a memory pool, but I think I understand the bascic linked list concept a little better now.

How would you implement a linked list in C#?

Keep in mind that I started programming in vb3 and my perceptions are warpped.... the last time I was considering writing a fast key/value or indexed strong typed collection in C# I looked at basing it on the System.Collections.Stack; didn't feel learning how to write push/pop code was worth the time so I used ArrayList by default...

A short answer will do for my second question. Can you think of any situation where I would actual want to break off into unmaged code and manage my own memory/memory pool in C# where I wouldn't be better off making a C++ Managed assembly/namespace.



Are you a student or a teacher at your university and what univirsty? I ask because I have I low opinion of the level of education of collage the educated programmers(at least in my area/experiance) and it sounds like you univirsty is providing the needed classes if the student cares to take them. That statement can be interpreted as meaning a very large percentage of the collage educated programmers I have worked with I have problem with thinking outside the box or this is what they taught me in school and this is what I do.....

One more since I am bombarding you... Is that you I see on the daily ***..?

*** the forum changed my post lol....

not to spam my thread but *** == w t f

dang ol short hand not the @#$% allowed

:)

I'm a student. I do my thinking outside the box - outside the university. Indeed, one of my younger professors complained about the lack of independent thinking in the students, but that's a problem of the system, not of the individual courses.

The situations in managed code when you'd want to use your own memory management are the same as in unmanaged code: when profiling reveals that you're spending too much time allocating objects. However, I believe that the allocator of .Net, having more information at runtime than just the number of requested bytes, is somewhat more efficient than most C++ allocators.
I can't think of any situation where you'd use unmanaged code to do this management, though. You'd just request a large block of memory in managed code and deal it out bit by bit.

I once wrote a C# LinkedList class. I'll upload it. I have no idea of the actual quality of the code though. It's been a while.

OK, here's the file. I realized that this class is quite incomplete. For example, it doesn't let you insert elements at arbitrary positions. Well, left as an exercise to the reader :)

Thanks for the sample; I'll check it out.

I actually thought you would say teacher/professor. I mean you seem to know something about almost everything. Are you going for Computer Engeniring or something else?

My particular study target is called "Software & Information Engineering", but most of my knowledge comes from private curiosity.