Linked Lists versus Lists in .NET

[kyrathaba]

I've been reading about linked lists and lists in the .NET Framework.  From my reading, it seems that lists generally outperform or are more efficient that linked lists.  What are some simple scenarios in which the programmer would be better served using a linked list?

[Ruffnekk]

Any scenario where an object in your list needs to be aware of a neighbouring object, either singly linked or doubly linked, which is practically never I have searched for an answer to this question before, because I was also wondering about it and more than once I stumbled upon pages stating that a linked list is probably the most useless list of all.

[kyrathaba]

I'm speaking out of my ignorance here, but weren't linked lists all the rage in C?  If so, was that because array lists weren't in use?  My hobbyist interest in programming started well after the reign of C, so I'm not very knowledgeable about it.  There's an article on www.csharp-online.net that recommends linked lists as a good solution when you need a linked data structure that allows you to easily add and remove elements.  But it seems the List<T> class is generally preferable, to me.

[Ruffnekk]

Yes they were a rage in C for a while and there are of course advantages to using a linked list, like simulating a stack or queue, inserting and deleting items is faster. Also, it's easier to use a neighbouring object directly from another object in iterations. The downside is the overall performance and accessing items in the list. Arraylists are much faster in general and you can access the nth item quickly (myArray[n]). In a LinkedList you have iterate over all items to get to the nth one. And last but not least, sorting linked lists is difficult.

What I don't understand is that Microsoft decided to give us a LinkedList collection in the .NET Framework 2.0 (it's a doubly linked list, so each node points forward and backwards).

The only useful application for a linked list I can think of is something like a preview. For example, you are displaying information on the screen and the user can click buttons to go to the next or previous item. You could easily display information about the next and/or previous items using a linked list; this would be more cumbersome in a normal list I guess.

[f0dder]

If you need to splice lists into multiple lists, or need to insert a large number of items in the middle of a collection, a list will offer better performance than just about everything else. Random access is slow though, and even linear access is slower because of the memory dereferencing. Also, you can have less heap fragmentation with linked lists than with, say, a C++ std::vector.

Can't think of real-world examples where it's better atm., but if you can come up with something where you need splicing or fast large inserts, you've got you answer

[kyrathaba]

In other words, for non-speed-critical tasks, lists are more often than not the simpler, and sometimes more efficient, alternative.

[f0dder]

Well, a C++ std::vector is simpler than a std::list (since it has (fast) random access etc.), and if you need splicing and large inserts, std::list can be the solution for speed-critical tasks...

So my default, simple and efficient container would be a vector, unless I need another because of whatever characteristic.

[kyrathaba]

Speaking of C++, I wonder if I ought to make the move from C# to C++.NET

[Eóin]

If you're doing .NET I say stick with C#, if you want to go native then switch to unmanaged C++.