0

In old times we all were dealing with Arrays, then link lists came boasting the following:

  1. it can grow and shrink at runtime by allocating and deallocating memory.
  2. Insertion and Deletion. Insertion and deletion of nodes are really easier.
  3. No Memory Wastage.
  4. Traversal.
  5. Reverse Traversing

While all above is true versus Arrays, I cannot find any benefit of a LinkedList over Generic List<T> ,as List<T> has all of the above properties.

Also, I have never seen LinkedList be used in any NET program.

I'm just looking to see if there is a situation which LinkedList<T> has an advantage over List<T>

===============================================

Thank you all for your feedbacks! The link above proved to be very helpful.

Based on the above link and comments, at least in .NET world, LinkedList seems to be much inferior to LIST.

BTFman
  • 220
  • 1
  • 8
  • This is nothing .NET specific. Yes, there are algorithms where linked lists work better than dynamically grown arrays. [Wikipedia has an overview](https://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays). – Jeroen Mostert Nov 06 '18 at 14:04
  • List is backed by an array, so searching should be faster, but inserting/slicing is usually slower. – Broom Nov 06 '18 at 14:05
  • 1
    But almost every comment on duplicate question shows List is much faster. – BTFman Nov 06 '18 at 14:07
  • Except for mid list inserting – Broom Nov 06 '18 at 14:08
  • Speed aside, linked lists are a more natural fit for algorithms that deal with next/previous kind of logic, as opposed to keeping track of array indices and handling underflow/overflow. It is true that on typical modern hardware, where locality of memory reference is king, there are very few circumstances where a linked list will give better performance. It's more or less grandfathered in as a classic collection type. – Jeroen Mostert Nov 06 '18 at 14:11
  • 1
    You are right , I have been dealing with .NET for 25 years, using linked list in .NET word is a joke.. No distant clue why. it is even there(Even old ArrayList does the job of Linked List). Could be possibility for backward compatibility with COM. – S Nash Nov 06 '18 at 14:18
  • 2
    @Broom And that's only true if you already have a reference to the location to insert. If you don't, it's way worse. – Servy Nov 06 '18 at 14:20
  • Ok, I'll concede that point, but how about memory management? Don't you need a new copy of the array when you modify it, effectively temporarily doubling the memory required for it? – Broom Nov 06 '18 at 14:35
  • 1
    @Broom: the keyword being "temporarily". On modern machines, memory is plentiful (or, at least, assumed to be, certainly with a garbage collected platform like .NET). A temporary increase is easily offset by the increase in speed of accessing the new array. It's true that if you're very tight on memory, proactively doubling array sizes can be a problem. – Jeroen Mostert Nov 06 '18 at 14:45
  • 1
    @Broom - vs the permanent 3xReference per node costs in the linked list, you'd need to be working with large structs for it to be worse. – Damien_The_Unbeliever Nov 06 '18 at 14:46
  • 1
    @Broom, Also don't Mix List with Arrays. They only implement common interface but are very different. – S Nash Nov 06 '18 at 14:49
  • @Broom A linked list requires twice as much memory per item as an array backed list (for a reference type or a type of similar size). One reference for the payload, one reference for the reference to the next item. The array backed solution only has that extra overhead for a short period of time when resizing (plus however much extra space is allocated when resizing). So while the array solution might peak a little higher for short periods of time, a linked list will consume more space on average, making it *worse* in a tight-memory situation. – Servy Nov 06 '18 at 15:02
  • @SNash A list is just a wrapper around an array with some added methods for convenience. For the purposes of discussing memory and performance of operations, they're identical. Obviously when it comes to actually implementing a solution, you should almost always use a `List` over an actual array. – Servy Nov 06 '18 at 15:04
  • @Servy/Damien_The_Unbeliever: I deal with lists of image data constantly. The reference overhead is nothing compared to a duplicated image data. – Broom Nov 06 '18 at 15:05
  • 2
    @Broom A list of images is not going to duplicate any images. There may be short periods of time where a *reference* to an image is duplicated, before the smaller buffer can be garbage collected. That's radically different. That is, unless you're storing image data in a value type, and if you are, then **stop doing that**. – Servy Nov 06 '18 at 15:07
  • they're stored as byte arrays. I always thought that modifying arrays required duplicating values even if they're reference types, since the array memory block is contiguous. – Broom Nov 06 '18 at 15:11
  • although now that I think about it, it makes way more sense for only the references to be held contiguously... – Broom Nov 06 '18 at 15:15
  • 1
    @Servy, LIST naturally uses Array class for easier implementation. other than that these 2 have some common interfaces, but this does not make them same at all. An Array uses interfaces that are not in LIST and vice vesa. So list is not a Wrapper for Array in sense of extending it .. – S Nash Nov 06 '18 at 15:25
  • @Broom: a multidimensional array (`a[x,y]`) stores the memory contiguously. A jagged array (`a[x][y]`) is an array of (references to) arrays. The latter tends to be more common than the former. – Jeroen Mostert Nov 06 '18 at 15:28
  • @SNash Wrapping something and extending it are two radically different things. Wrapping something is *never* extending it, and extending something is never wrapping it. A list is a wrapper around an array that provides convenient operations, and hiding some implementation details (which are specifically being discussed here). However, the underlying memory and performance characteristics of the operations being discussed here will be identical whether you use an array and manually perform the operations, or use a list and let it handle them for you. So the difference aren't relevant to here. – Servy Nov 06 '18 at 15:30

0 Answers0