When should I use a List vs a LinkedList

Question

When is it better to use a List vs a LinkedList?

Solution 1

Edit

Please read the comments to this answer. People claim I did not do proper tests. I agree this should not be an accepted answer. As I was learning I did some tests and felt like sharing them.

Original answer...

I found interesting results:

// Temporary class to show the example
class Temp
{
    public decimal A, B, C, D;

    public Temp(decimal a, decimal b, decimal c, decimal d)
    {
        A = a;            B = b;            C = c;            D = d;
    }
}

Linked list (3.9 seconds)

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.AddLast(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

List (2.4 seconds)

        List<Temp> list = new List<Temp>(); // 2.4 seconds

        for (var i = 0; i < 12345678; i++)
        {
            var a = new Temp(i, i, i, i);
            list.Add(a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Even if you only access data essentially it is much slower!! I say never use a linkedList.

---

---

---

Here is another comparison performing a lot of inserts (we plan on inserting an item at the middle of the list)

Linked List (51 seconds)

        LinkedList<Temp> list = new LinkedList<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            var curNode = list.First;

            for (var k = 0; k < i/2; k++) // In order to insert a node at the middle of the list we need to find it
                curNode = curNode.Next;

            list.AddAfter(curNode, a); // Insert it after
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

List (7.26 seconds)

        List<Temp> list = new List<Temp>();

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.Insert(i / 2, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

Linked List having reference of location where to insert (.04 seconds)

        list.AddLast(new Temp(1,1,1,1));
        var referenceNode = list.First;

        for (var i = 0; i < 123456; i++)
        {
            var a = new Temp(i, i, i, i);

            list.AddLast(a);
            list.AddBefore(referenceNode, a);
        }

        decimal sum = 0;
        foreach (var item in list)
            sum += item.A;

So only if you plan on inserting several items and you also somewhere have the reference of where you plan to insert the item then use a linked list. Just because you have to insert a lot of items it does not make it faster because searching the location where you will like to insert it takes time.

Solution 2

In most cases, List<T> is more useful. LinkedList<T> will have less cost when adding/removing items in the middle of the list, whereas List<T> can only cheaply add/remove at the end of the list.

LinkedList<T> is only at it's most efficient if you are accessing sequential data (either forwards or backwards) - random access is relatively expensive since it must walk the chain each time (hence why it doesn't have an indexer). However, because a List<T> is essentially just an array (with a wrapper) random access is fine.

List<T> also offers a lot of support methods - Find, ToArray, etc; however, these are also available for LinkedList<T> with .NET 3.5/C# 3.0 via extension methods - so that is less of a factor.

Solution 3

Thinking of a linked list as a list can be a bit misleading. It's more like a chain. In fact, in .NET, LinkedList<T> does not even implement IList<T>. There is no real concept of index in a linked list, even though it may seem there is. Certainly none of the methods provided on the class accept indexes.

Linked lists may be singly linked, or doubly linked. This refers to whether each element in the chain has a link only to the next one (singly linked) or to both the prior/next elements (doubly linked). LinkedList<T> is doubly linked.

Internally, List<T> is backed by an array. This provides a very compact representation in memory. Conversely, LinkedList<T> involves additional memory to store the bidirectional links between successive elements. So the memory footprint of a LinkedList<T> will generally be larger than for List<T> (with the caveat that List<T> can have unused internal array elements to improve performance during append operations.)

They have different performance characteristics too:

Append

• LinkedList<T>.AddLast(item) constant time
• List<T>.Add(item) amortized constant time, linear worst case

Prepend

• LinkedList<T>.AddFirst(item) constant time
• List<T>.Insert(0, item) linear time

Insertion

• LinkedList<T>.AddBefore(node, item) constant time
• LinkedList<T>.AddAfter(node, item) constant time
• List<T>.Insert(index, item) linear time

Removal

• LinkedList<T>.Remove(item) linear time
• LinkedList<T>.Remove(node) constant time
• List<T>.Remove(item) linear time
• List<T>.RemoveAt(index) linear time

Count

• LinkedList<T>.Count constant time
• List<T>.Count constant time

Contains

• LinkedList<T>.Contains(item) linear time
• List<T>.Contains(item) linear time

Clear

• LinkedList<T>.Clear() linear time
• List<T>.Clear() linear time

As you can see, they're mostly equivalent. In practice, the API of LinkedList<T> is more cumbersome to use, and details of its internal needs spill out into your code.

However, if you need to do many insertions/removals from within a list, it offers constant time. List<T> offers linear time, as extra items in the list must be shuffled around after the insertion/removal.

Solution 4

Linked lists provide very fast insertion or deletion of a list member. Each member in a linked list contains a pointer to the next member in the list so to insert a member at position i:

• update the pointer in member i-1 to point to the new member
• set the pointer in the new member to point to member i

The disadvantage to a linked list is that random access is not possible. Accessing a member requires traversing the list until the desired member is found.

Solution 5

My previous answer was not enough accurate. As truly it was horrible :D But now I can post much more useful and correct answer.

---

I did some additional tests. You can find it's source by the following link and reCheck it on your environment by your own: https://github.com/ukushu/DataStructuresTestsAndOther.git

Short results:

• Array need to use:

  • So often as possible. It's fast and takes smallest RAM range for same amount information.
  • If you know exact count of cells needed
  • If data saved in array < 85000 b (85000/32 = 2656 elements for integer data)
  • If needed high Random Access speed

• List need to use:

  • If needed to add cells to the end of list (often)
  • If needed to add cells in the beginning/middle of the list (NOT OFTEN)
  • If data saved in array < 85000 b (85000/32 = 2656 elements for integer data)
  • If needed high Random Access speed

• LinkedList need to use:

  • If needed to add cells in the beginning/middle/end of the list (often)
  • If needed only sequential access (forward/backward)
  • If you need to save LARGE items, but items count is low.
  • Better do not use for large amount of items, as it's use additional memory for links.

More details:

Interesting to know:

1. LinkedList<T> internally is not a List in .NET. It's even does not implement IList<T>. And that's why there are absent indexes and methods related to indexes.

2. LinkedList<T> is node-pointer based collection. In .NET it's in doubly linked implementation. This means that prior/next elements have link to current element. And data is fragmented -- different list objects can be located in different places of RAM. Also there will be more memory used for LinkedList<T> than for List<T> or Array.

3. List<T> in .Net is Java's alternative of ArrayList<T>. This means that this is array wrapper. So it's allocated in memory as one contiguous block of data. If allocated data size exceeds 85000 bytes, it will be moved to Large Object Heap. Depending on the size, this can lead to heap fragmentation(a mild form of memory leak). But in the same time if size < 85000 bytes -- this provides a very compact and fast-access representation in memory.

4. Single contiguous block is preferred for random access performance and memory consumption but for collections that need to change size regularly a structure such as an Array generally need to be copied to a new location whereas a linked list only needs to manage the memory for the newly inserted/deleted nodes.

View more solutions

Comments

[Marc Gravell]

List<T> is array (T[]) based, not ArrayList based. Re insert: the array resize isn't the issue (the doubling algorithm means that most of the time it doesn't have to do this): the issue is that it must block-copy all the existing data first, which takes a little time.

[Marc Gravell]

My point was that that it isn't the resize that causes the pain - it is the blit. So worst case, if we are adding the first (zeroth) element each time, then the blit has to move everything each time.

[Sean Dixon]

I would add that linked lists have an overhead per item stored implied above via LinkedListNode which references the previous and next node. The payoff of that is a contiguous block of memory isn't required to store the list, unlike an array based list.

[Jonathan Allen]

Isn't a contiguous block of memory usually perferred?

[jpierson]

Yes, a contiguous block is preferred for random access performance and memory consumption but for collections that need to change size regularly a structure such as an Array generally need to be copied to a new location whereas a linked list only needs to manage the memory for the newly inserted/deleted nodes.

[Andrew]

If you have ever had to work with very large arrays or lists (a list just wraps an array) you will start to run into memory issues even though there appears to be plenty of memory available on your machine. The list uses a doubling strategy when it allocates new space in it's underlying array. So a 1000000 elemnt array that is full will be copied into a new array with 2000000 elements. This new array needs to be created in a contiguous memory space that is large enough to hold it.

[Raven]

I had a specific case where all i did was adding and removing, and looping one by one... here the linked list was far superior to the normal list..

[Iain Ballard]

Is count linkedlist constant? I thought that would be linear?

[Drew Noakes]

@Iain, the count is cached in both list classes.

[aStranger]

You wrote that "List<T>.Add(item) logarithmic time", however it is in fact "Constant" if the list capacity can store the new item, and "Linear" if the list doesn't have enough space and new to be reallocated.

[Drew Noakes]

@aStranger, of course you're right. Not sure what I was thinking in the above -- perhaps that the amortized normal case time is logarithmic, which it isn't. In fact the amortized time is constant. I didn't get into best/worst case of the operations, aiming for a simple comparison. I think the add operation is significant enough to provide this detail however. Will edit the answer. Thanks.

[JerKimball]

There is one benefit to LinkedList over List (this is .net specific): since the List is backed by an internal array, it is allocated in one contiguous block. If that allocated block exceeds 85000 bytes in size, it will be allocated on the Large Object Heap, a non-compactable generation. Depending on the size, this can lead to heap fragmentation, a mild form of memory leak.

[cHao]

Note that if you're prepending a lot (as you're essentially doing in the last example) or deleting the first entry, a linked list will nearly always be significantly faster, as there is no searching or moving/copying to do. A List would require moving everything up a spot to accommodate the new item, making prepending an O(N) operation.

[Earlz]

Note: This sounds completely typical of ANY linked list implementation, not just .Net's.

[Robert Jeppesen]

Good answer! You should mention that indexed access is constant time with List but linear with LinkedList.

[Drew Noakes]

@RobertJeppesen, actually LinkedList<T> doesn't have any member for index-based access. You can still do this using an extension method based on IEnumerable<T> which of course suggests linear time access.

[Robert Jeppesen]

@DrewNoakes That does make it obvious. :). Still, it is an advantage of List<T> that deservers mention.

[Drew Noakes]

@RobertJeppesen, I completely agree that it's a key distinction. In fact I think the name 'list' is misleading, although of course it's baked into the collective computer science consciousness now. Would you expand on the opening paragraph where I cover what we're talking about?

[Drew Noakes]

I don't see why point 2 makes sense. Linked lists are great when you're doing many insertions/deletions throughout the entire list.

[Antony Thomas]

Because of the fact that LinkedLists are not Index based, you really have to scan the entire list for insertion or deletion that incurs a O(n) penalty. List<> on the other hand suffers from Array resizing, but still,IMO, is a better option when compared to LinkedLists.

[Drew Noakes]

You don't have to scan the list for insertions/deletions if you keep track of the LinkedListNode<T> objects in your code. If you can do that, then it's much better than using List<T>, especially for very long lists where inserts/removals are frequent.

[Antony Thomas]

You mean thru a hashtable? If that is the case, that would be the typical space\time tradeoff that every computer programmer should make a choice based on the problem domain :) But yes, that would make it faster.

[alcedo]

This is strange. For the first results, it goes against what @marc gravell and other posters mentioned. eg: insertion and forward traversal time should be same for both LinkedList and List. any ideas?

[Miles Rout]

I don't think the name List is misleading at all in the case of a linked list. It's misleading in the case of an array!

[ALZ]

if combine Double Linked List with Dictionary - you can get O(1) speed at insertion/deletion and accessing too.

[Christophe De Troyer]

I think it's notable that a List is implemented using an array. Which means that this array needs to be expanded once the list exceeds it's initial size. Which is again an O(n) operation. In contrast to a linkedlist, there is no storagemove needed so we never have that costly operation O(n). Alinked list is mostly handy when appending a lot of data in the beginning of the list. Correct me if I'm wrong.

[ruffin]

Why the in-loop list.AddLast(a); in the last two LinkedList examples? I get doing it once before the loop, as with list.AddLast(new Temp(1,1,1,1)); in the next to last LinkedList, but it looks (to me) like you're adding twice as many Temp objects in the loops themselves. (And when I double-check myself with a test app, sure enough, twice as many in the LinkedList.)

[Quonux]

@JerKimball heap fragmentation has nothing in common with memory leaks

[JerKimball]

@Quonux Strictly speaking, true - but a fragmented LOH will present itself almost identically to a memory leak; the allocated memory will continue to grow unabated.

[bytefire]

@Tono Nam, if you want to add an element at the beginning of the collection then LinkedList (O(1)) will be faster than List (O(n)), because List will have to shift n elements to right. It's a shame though that you can't chain or merge a linked list.

[Damian]

It might also be a good idea to test insert at the start of the list, the LinkedList should be much faster than List at this task.

[nawfal]

This is by far the best answer here. Also you could add Clear. Both are O(n). The memory overhead for LinkedList is worth noting. Already upvoted.

[Drew Noakes]

@nawfal, I've added a section for Clear. The third paragraph already discusses memory usage. Would you add to it?

[nawfal]

@DrewNoakes Yes indeed you have discussed memory usage, I was just saying. Slight correction, Clear is linear time, not constant time for both methods. It's documented in msdn.

[paul23]

Isn't in normal application it quite common that you only need to "find it once"?? On top of that; the performance is quite skewed, your adding 2 elements in the linked list, so the size is 2 times as large as the list.

[nawfal]

I downvoted this answer. 1) your general advice I say never use a linkedList. is flawed as your later post reveals. You might want to edit it. 2) What are you timing? Instantiation, addition, and enumeration altogether in one step? Mostly, instantiation and enumeration are not what ppl are worried about, those are one time steps. Specifically timing the inserts and additions would give a better idea. 3) Most importantly, you're adding more than required to a linkedlist. This is a wrong comparison. Spreads wrong idea about linkedlist.

[Servy]

You can simply use RemoveAll to remove the items from a List without moving a lot of items around, or use Where from LINQ to create a second list. Using a LinkedList here however ends up consuming dramatically more memory than other types of collections and the loss of memory locality means that it will be noticeably slower to iterate, making it quite a bit worse than a List.

[mafu]

Sorry, but This answer is really bad. Please do NOT listen to this answer. Reason in a nutshell: It is completely flawed to think that array-backed list implementations are stupid enough to resize the array on each insertion. Linked lists are naturally slower than array-backed lists when traversing as well as when inserting at either end, because only they need to create new objects, while array-backed lists use a buffer (in both directions, obviously). The (poorly done) benchmarks indicate precisely that. The answer completely fails to check the cases in which linked lists are preferable!

[Arturo Torres Sánchez]

@Servy, note that @Tom's answer use Java. I'm not sure if there's a RemoveAll equivalent in Java.

[Servy]

@ArturoTorresSánchez Well the question specifically states that it's about .NET, so that just makes the answer that much less appropriate.

[Arturo Torres Sánchez]

@Servy, then you should have mentioned that from the beginning.

[RenniePet]

One advantage of List<> vs. LinkedList<> that I'd never thought of concerns how microprocessors implement caching of memory. Although I don't understand it completely, the writer of this blog article talks a lot about "locality of reference", which makes traversing an array much faster than traversing a linked list, at least if the linked list has become somewhat fragmented in memory. kjellkod.wordpress.com/2012/02/25/…

[Edward Ned Harvey]

Downvoted this "answer" because first of all, the blatant inaccuracy of "number of seconds." Maybe a type-o for nanoseconds, but blatant and repeated, so bad. Also, the API for List and LinkedList are different from each other - which means sometimes one is correct and the other is inappropriate. So this "answer" which states "never use LinkedList" based solely on performance for a particular task is inaccurate. I'm not even going to look for more flaws (which I'm sure exist) in this answer. Use a different answer.

[Casey]

@RenniePet List is implemented with a dynamic array and arrays are contiguous blocks of memory.

[nawfal]

@mafu where does the answer allude List<T> resizes array on each insertion?

[nawfal]

I have added an answer correcting OP's measurements.

[Cardin]

I'm appalled to find the selected answer being one that completely overlooks the implementation of a List/Array vs LinkedList from a computer science perspective. It's the traversal of a Linked List that slows things down!

[Cardin]

Since List is a dynamic array, that's why sometimes it's good to specify the capacity of a List in the constructor if you know it beforehand.

[nexus]

This is a completely uninformed answer. It should not be the chosen answer or the top result!

[Lorenzo Santoro]

The memory footprint after the Clear is considerably different, as the List<T> keeps its size, while the LinkedList does not.

[RBaarda]

IMO this should be the answer. LinkedList are used when a guaranteed order is important.

[tomalone]

Couple of thoughts on appending and prepending: 1. List<T>.AddItem(item) - should it be O(1), since List shoudn't do much calculation as to how to reach the last element, right? 2.. Is List<T>.Insert(0, item) not done in a constant time? whereas Insert in general would be O(n), specifically insert(0, item) would have O(1) because List doesn't need to sweat to much to calculate where it's 0 index is, does it?

[Francis Lord]

@tomalone If I'm understanding this correctly, Insert(0, item) is actually the worst case for insert since to insert at index 0, the list first has to move all the elements one square before inserting the new element. I believe it may even be worst if it needs to reallocate the array for lack of space.

[Drew Noakes]

That's right. List.Add is considered amortised constant time, because the cost of growing the array is spread out over each of its N elements, making it a constant factor. List.Insert is considered linear because you have to move elements to make space for the inserted item. Technically if you always insert at the end, it's constant time, but then you could just use Add anyway.

[Philm]

Question: With "data saved in array < or > 85.000 byte" you mean data per array/list ELEMENT do you? It could be understood that you mean the datasize of the whole array..

[Philm]

I see one contradiction in some conclusions: Given, that I only care about the speed of Append, what is best? I want to fill the container with some million text lines (or any other stream), but I don't care for RAM: I only need to care about the speed Append (.Add to the end of the list). This is the most important (canonical) case, inserts at the middle are something else: ----- Is it better to use a LinkedList<T> oder List<T> ??

[Drew Noakes]

@Philm, you should possibly start a new question, and you don't say how you're going to use this data structure once built, but if you're talking a million rows you might like some kind of hybrid (linked list of array chunks or similar) to reduce heap fragmentation, reduce memory overhead, and avoiding a single huge object on the LOH.

[Philm]

Is it possible that the C# implementation of all, array, List<T> and LinkedList<T> is somewhat suboptimal for one very important case: You need a very large list, append (AddLast) and sequential traversal (in one direction) are totally fine: I want no array resizing to get continuous blocks (is it guaranteed for each array, even 20 GB arrays?), and I don't know in advance the size, but I can guess in advance a block size, e.g. 100 MB to reserve each time in advance. This would be a good implementation. Or is array/List similar to that, and I missed a point ?

[Philm]

@RBaarda: I do not agree. It depends on the level we are talking of. The algorithmic level is different to the machine-implementation level. For speed consideration you need the latter too. As it is pointed out, arrays are implemented of being "one chunk" of memory what is a restriction, because this can lead to resizing and memory reorganisation, especially with very large arrays. After thinking a while, a special own data structure, a linked list of arrays would would be one idea to give better control over speed of linear filling and accessing very large data structures.

[Marc Gravell]

@Philm that's the kind of scenario where you write your own shim over your chosen block strategy; List<T> and T[] will fail for being too chunky (all one slab), LinkedList<T> will wail for being too granular (slab per element).

[Philm]

Yes. Meanwhile I am thinkig of implementing a shim of LinkedList<T> of arrays of 10MB or something. The implementation could be interesting..

[Jonathan Allen]

Note that this advice is for .NET, not Java. In Java's linked list implementation you don't have the concept of a "current node", so you have to traverse the list for each and every insert.

[motoDrizzt]

I mostly wonder why it has not been deleted, instead. Given that even ITS author claims the answer is wrong, it shouldn't have taken a mod too long to decide to delete it.

[ToolmakerSteve]

@Philm - If an Array succeeds in allocating, it will be fully sequential; the allocation done in Resize is new T[newSize]. array.cs. List internally an Array, so same is true for it. LinkedList is not what you want when you have a large number of elements: it allocates a LinkedListNode per element. Each LinkedListNode is a separate allocation: there is not an Array of anything. No continuity. A lot of memory used for previous/next pointers. google c# LinkedList source code.

[ToolmakerSteve]

@Philm - your comment here "all I care about is the speed Append" is at odds with your comment on Mark Gravell's answer that you need continuous blocks. Either you are thinking about two very different uses, or you are confused about what you need. When in doubt, use List, and write your algorithm as simply as you can, with no concern for performance. After your code works correctly in every test case you can think of, time it. If fast enough, move on to another task.

[ToolmakerSteve]

To add to @ALZ's point: "fast insertion" of LinkedList only helps when you have a reference to the element to insert before or after. if you have to search for the element, then the time will be dominated by that linear search. If each element is associated with a unique key, then a Dictionary mapping key to element will give you the element in O(1) time. (E.g. if each element has an int Id, and you are passing around those Ids rather than passing around references to elements, you'll want this Dictionary.)

[ToolmakerSteve]

@IlyaRyzhenkov - you are thinking about the case where Add is always at end of existing array. List is "good enough" at that, even if not O(1). The serious problem occurs if you need many Adds that are not at the end. Marc is pointing out that the need to move existing data every time you insert (not just when resize is needed) is a more substantial performance cost of List.

[ToolmakerSteve]

If RemoveAll is not available for List, you could do a "compaction" algorithm, which would look like Tom's loop, but with two indices and the need to move items to be kept one at a time down in the list's internal array. Efficiency is O(n), the same as Tom's algorithm for LinkedList. In both versions, the time to compute the HashSet key for the strings dominates. This is not a good example of when to use LinkedList.

[ToolmakerSteve]

Re your statement that Deque is "similar to linked list, but with improved performance". Please qualify that statement: Deque is better performance than LinkedList, for your specific code. Following your link, I see that two days later you learned from Ivan Stoev that this was not an inefficiency of LinkedList, but an inefficiency in your code. (And even if it had been an inefficiency of LinkedList, that would not justify a general statement that Deque is more efficient; only in specific cases.)

[ToolmakerSteve]

This answer is only partially correct: 2) if elements are large, then make the element type a Class not a Struct, so that List simply holds a reference. Then element size becomes irrelevant. 3) Deque and queue can be efficiently done in a List if you use List as a "circular buffer", instead of doing insert or remove at start. StephenCleary's Deque. 4) partially true: when many objects, pro of LL is don't need huge contiguous memory; downside is extra memory for node pointers.

[ToolmakerSteve]

@AntonyThomas - No, he means by passing around references to nodes instead of passing around references to elements. If all you have is an element, then both List and LinkedList have bad performance, because you have to search. If you think "but with List I can just pass in an index": that is only valid when you never insert a new element into the middle of the List. LinkedList doesn't have this limitation, if you hold on to a node (and use node.Value whenever you want the original element). So you rewrite algorithm to work with nodes, not raw values.

[ToolmakerSteve]

Point 1) is sometimes true, sometimes not. The downside of LinkedList, when there might be many objects, and objects are small, is that each object requires an extra allocation - the LinkedListNode that is created when you Add it to the LinkedList. The upside is that you don't have to acquire a single contiguous chunk of memory, so you avoid a potential memory fragmentation issue. (I've never found the performance cost of List's internal Resize to be significant; its how memory is used that matters in practice.)

[ToolmakerSteve]

As Drew points out, Point 2) is questionable. The usual argument in favor of LinkedList is when you need to delete/insert anywhere except at the tail. List has to move existing data. LinkedList does not. Your argument in a comment that "you really have to scan the entire list" means that you are thinking about algorithms where indices don't change. Indeed, List is good in those cases - but as soon as you delete/insert in the middle of a list, existing indices are useless. So List is not good in those cases. You have it backwards; "middle of list" is when LinkedList wins over List.

[ToolmakerSteve]

@b3 re "random access is not possible": only partially true. If you write algorithms that pass around references to nodes, then LinkedList is superior to List in manipulating "random" elements, if inserts/deletes are done anywhere but at the end of the collection. As soon as you insert/delete in the middle, any existing List indices become invalid, and the advantage of List is lost. Whereas if your algorithm is holding a node, it can still examine elements before/after efficiently. For some algorithms, this gives superior performance.

[Philm]

My comments are more out of principal interest of details of the standard .NET implementations and possible ideas to improve sth. than one single use case. Of course I am aware that every performance statement "depends". So these two remarks on two answers do not affect the identical scenario. But generally it is of course desirable to get high speed on iterating (cache locality) as for arrays as well as for insert. Inserting on the end of a List (if the underlying array is still large enough) should be fast enough. Inserting at the beginning is of course something else.

[ToolmakerSteve]

@Philm - I upvoted your comment, but I would like to point out that you are describing a different requirement. What the answer is saying is that linked list has performance advantage for algorithms that involve a lot of rearranging of items. Given that, I interpret RBaarda's comment as referring to the need to add/delete items while continuously maintaining a given ordering (sort criteria). So not just "linear filling". Given this, List loses out, because indices are useless (change every time you add an element anywhere but at the tail end).

[Andrew___Pls_Support_UA]

Array elements located sequentially in memory. So per array. I know about mistake in table, later I will fix it :) ( I hope.... )

[MattE]

The problem is Theoretical Big O notations don't tell the entire story. In computer science that is all anyone ever cares about, but there is far more to be concerned with than this in the real world.

[Rob]

With lists being slow at inserts, if a list has a lot of turnaround (lots of inserts/deletes) is memory occupied by deleted space kept and if so, does that make "re"-inserts faster?

[user1496062]

What people forget is 1) While O(N) may result in a few orders less operations, the cache hit and allocation cost of having a wrapper node probably still mean performance is worse unless lists are very large. 2) There is a huge difference between List<int> vs List<MyObject> 3) Things like List<int> sometimes uses simd for reads . 4) With linq you see a lot of ToLists() if the underlying object is a linked list this is much more expensive

[user1496062]

Also note when talking about list<struct/primitive> vs list<object> this shows almost no improvement in linked lists often with boxing etc and a massive improvement for List.

[Holger]

There is no such thing as a "dynamic array", it's just a new array in a larger size and all the elements are moved. So if you increase a 1 GB array by 10 bytes, you allocate 1000000010 fresh new bytes, and move 1 Gig, so you have 2 GB allocated in the moment of increase. This you have to necessarily avoid, so linking chunks of 10 MB is a good compromise. But a jagged array is good enough for that. it does not need to be a linked list.