topbanner_forum
  *

avatar image

Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
  • Tuesday March 19, 2024, 3:47 am
  • Proudly celebrating 15+ years online.
  • Donate now to become a lifetime supporting member of the site and get a non-expiring license key for all of our programs.
  • donate

Author Topic: Linked Lists versus Lists in .NET  (Read 5530 times)

kyrathaba

  • N.A.N.Y. Organizer
  • Honorary Member
  • Joined in 2006
  • **
  • Posts: 3,200
    • View Profile
    • Donate to Member
Linked Lists versus Lists in .NET
« on: February 27, 2007, 11:49 AM »
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

  • Honorary Member
  • Joined in 2006
  • **
  • Posts: 332
  • Uhm yeah...
    • View Profile
    • RuffNekk's Crypto Pages
    • Donate to Member
Re: Linked Lists versus Lists in .NET
« Reply #1 on: February 27, 2007, 12:51 PM »
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.
Regards,
RuffNekk

Programming is an art form that fights back.

kyrathaba

  • N.A.N.Y. Organizer
  • Honorary Member
  • Joined in 2006
  • **
  • Posts: 3,200
    • View Profile
    • Donate to Member
Re: Linked Lists versus Lists in .NET
« Reply #2 on: February 27, 2007, 01:02 PM »
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.
« Last Edit: February 27, 2007, 01:05 PM by kyrathaba »

Ruffnekk

  • Honorary Member
  • Joined in 2006
  • **
  • Posts: 332
  • Uhm yeah...
    • View Profile
    • RuffNekk's Crypto Pages
    • Donate to Member
Re: Linked Lists versus Lists in .NET
« Reply #3 on: February 27, 2007, 01:16 PM »
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.
Regards,
RuffNekk

Programming is an art form that fights back.

f0dder

  • Charter Honorary Member
  • Joined in 2005
  • ***
  • Posts: 9,153
  • [Well, THAT escalated quickly!]
    • View Profile
    • f0dder's place
    • Read more about this member.
    • Donate to Member
Re: Linked Lists versus Lists in .NET
« Reply #4 on: February 27, 2007, 07:54 PM »
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 :)

- carpe noctem

kyrathaba

  • N.A.N.Y. Organizer
  • Honorary Member
  • Joined in 2006
  • **
  • Posts: 3,200
    • View Profile
    • Donate to Member
Re: Linked Lists versus Lists in .NET
« Reply #5 on: February 28, 2007, 06:49 AM »
In other words, for non-speed-critical tasks, lists are more often than not the simpler, and sometimes more efficient, alternative.

f0dder

  • Charter Honorary Member
  • Joined in 2005
  • ***
  • Posts: 9,153
  • [Well, THAT escalated quickly!]
    • View Profile
    • f0dder's place
    • Read more about this member.
    • Donate to Member
Re: Linked Lists versus Lists in .NET
« Reply #6 on: February 28, 2007, 08:17 AM »
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.
- carpe noctem

kyrathaba

  • N.A.N.Y. Organizer
  • Honorary Member
  • Joined in 2006
  • **
  • Posts: 3,200
    • View Profile
    • Donate to Member
Re: Linked Lists versus Lists in .NET
« Reply #7 on: February 28, 2007, 10:46 AM »
Speaking of C++, I wonder if I ought to make the move from C# to C++.NET

Eóin

  • Charter Member
  • Joined in 2006
  • ***
  • Posts: 1,401
    • View Profile
    • Donate to Member
Re: Linked Lists versus Lists in .NET
« Reply #8 on: February 28, 2007, 10:53 AM »
If you're doing .NET I say stick with C#, if you want to go native then switch to unmanaged C++.