When should I use a List vs a LinkedList

Question

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

Transonic

Java q, shouldnt be very different. – Starflower

@jonathan-allen, Please consider changing the accepted answer. The current one is inaccurate and extremely misleading. – Pesce

As Xpleria said, pls consider changing the current accepted answer. The current is misleading. – Shillyshally

Answer 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.

Squiggle

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. – Cloris

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. – Ingenerate

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

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? – Sonar

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. – Picador

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.) – Skipper

@Cloris heap fragmentation has nothing in common with memory leaks – Clump

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

@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. – Astrogate

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. – Accredit

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. – Pix

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. – Starflower

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! – Judicial

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. – Accrescent

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

I have added an answer correcting OP's measurements. – Starflower

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! – Villalobos

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

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. – Ratter

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. – Uprear

Answer 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.

Americanist

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/… – Pronounce

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

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. – Villalobos

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 ? – Swearword

@Swearword 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). – Americanist

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

@Swearword - 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. – Bemoan

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. – Kiki

Answer 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.

Collum

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

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

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. – Townshend

@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. – Collum

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

@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. – Collum

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

@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? – Collum

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! – Cromer

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. – Starflower

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

@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. – Starflower

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

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? – Gnash

@Gnash 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. – Registration

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. – Collum

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> ?? – Swearword

@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. – Collum

@Swearword - 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. – Bemoan

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. – Swearword

Answer 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.

Thordia

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. – Bonnee

Isn't a contiguous block of memory usually perferred? – Transonic

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. – Facile

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. – Breathing

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.. – Silicle

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

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.) – Bemoan

@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. – Bemoan

Answer 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.

Ephemerid

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.. – Swearword

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

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? – Spiritual

"If data saved in array < 85000 b (85000/32 = 2656 elements for integer data)" Did you mean 85000 bits or bytes? I assume Integer takes 4 bytes, not 32 – Mettlesome

Answer 6

The difference between List and LinkedList lies in their underlying implementation. List is array based collection (ArrayList). LinkedList is node-pointer based collection (LinkedListNode). On the API level usage, both of them are pretty much the same since both implement same set of interfaces such as ICollection, IEnumerable, etc.

The key difference comes when performance matter. For example, if you are implementing the list that has heavy "INSERT" operation, LinkedList outperforms List. Since LinkedList can do it in O(1) time, but List may need to expand the size of underlying array. For more information/detail you might want to read up on the algorithmic difference between LinkedList and array data structures. http://en.wikipedia.org/wiki/Linked_list and Array

Hope this help,

Lipocaic

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. – Americanist

@Marc, the 'doubling algorithm" only makes it O(logN), but it is still worse than O(1) – Lituus

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. – Americanist

@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. – Bemoan

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. – Bullough

Answer 7

The primary advantage of linked lists over arrays is that the links provide us with the capability to rearrange the items efficiently. Sedgewick, p. 91

Spice

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

@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. – Swearword

@Swearword - 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). – Bemoan

@Earthman No it should not be the answer, it just copy-pasted a reference without example or a bit of their own input. The best this would be is a comment not even an answer – Cognizant

Answer 8

A common circumstance to use LinkedList is like this:

Suppose you want to remove many certain strings from a list of strings with a large size, say 100,000. The strings to remove can be looked up in HashSet dic, and the list of strings is believed to contain between 30,000 to 60,000 such strings to remove.

Then what's the best type of List for storing the 100,000 Strings? The answer is LinkedList. If the they are stored in an ArrayList, then iterating over it and removing matched Strings whould take up to billions of operations, while it takes just around 100,000 operations by using an iterator and the remove() method.

LinkedList<String> strings = readStrings();
HashSet<String> dic = readDic();
Iterator<String> iterator = strings.iterator();
while (iterator.hasNext()){
    String string = iterator.next();
    if (dic.contains(string))
    iterator.remove();
}

Cleavers

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. – Clementineclementis

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

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

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

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. – Bemoan

Answer 9

When you need built-in indexed access, sorting (and after this binary searching), and "ToArray()" method, you should use List.

Vickeyvicki

Answer 10

Essentially, a List<> in .NET is a wrapper over an array. A LinkedList<> is a linked list. So the question comes down to, what is the difference between an array and a linked list, and when should an array be used instead of a linked list. Probably the two most important factors in your decision of which to use would come down to:

• Linked lists have much better insertion/removal performance, so long as the insertions/removals are not on the last element in the collection. This is because an array must shift all remaining elements that come after the insertion/removal point. If the insertion/removal is at the tail end of the list however, this shift is not needed (although the array may need to be resized, if its capacity is exceeded).
• Arrays have much better accessing capabilities. Arrays can be indexed into directly (in constant time). Linked lists must be traversed (linear time).

Atabrine

Answer 11

This is adapted from Tono Nam's accepted answer correcting a few wrong measurements in it.

The test:

static void Main()
{
    LinkedListPerformance.AddFirst_List(); // 12028 ms
    LinkedListPerformance.AddFirst_LinkedList(); // 33 ms

    LinkedListPerformance.AddLast_List(); // 33 ms
    LinkedListPerformance.AddLast_LinkedList(); // 32 ms

    LinkedListPerformance.Enumerate_List(); // 1.08 ms
    LinkedListPerformance.Enumerate_LinkedList(); // 3.4 ms

    //I tried below as fun exercise - not very meaningful, see code
    //sort of equivalent to insertion when having the reference to middle node

    LinkedListPerformance.AddMiddle_List(); // 5724 ms
    LinkedListPerformance.AddMiddle_LinkedList1(); // 36 ms
    LinkedListPerformance.AddMiddle_LinkedList2(); // 32 ms
    LinkedListPerformance.AddMiddle_LinkedList3(); // 454 ms

    Environment.Exit(-1);
}

And the code:

using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace stackoverflow
{
    static class LinkedListPerformance
    {
        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;
            }
        }



        static readonly int start = 0;
        static readonly int end = 123456;
        static readonly IEnumerable<Temp> query = Enumerable.Range(start, end - start).Select(temp);

        static Temp temp(int i)
        {
            return new Temp(i, i, i, i);
        }

        static void StopAndPrint(this Stopwatch watch)
        {
            watch.Stop();
            Console.WriteLine(watch.Elapsed.TotalMilliseconds);
        }

        public static void AddFirst_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(0, temp(i));

            watch.StopAndPrint();
        }

        public static void AddFirst_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddFirst(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Add(temp(i));

            watch.StopAndPrint();
        }

        public static void AddLast_LinkedList()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (int i = start; i < end; i++)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        public static void Enumerate_List()
        {
            var list = new List<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        public static void Enumerate_LinkedList()
        {
            var list = new LinkedList<Temp>(query);
            var watch = Stopwatch.StartNew();

            foreach (var item in list)
            {

            }

            watch.StopAndPrint();
        }

        //for the fun of it, I tried to time inserting to the middle of 
        //linked list - this is by no means a realistic scenario! or may be 
        //these make sense if you assume you have the reference to middle node

        //insertion to the middle of list
        public static void AddMiddle_List()
        {
            var list = new List<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
                list.Insert(list.Count / 2, temp(i));

            watch.StopAndPrint();
        }

        //insertion in linked list in such a fashion that 
        //it has the same effect as inserting into the middle of list
        public static void AddMiddle_LinkedList1()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            LinkedListNode<Temp> evenNode = null, oddNode = null;
            for (int i = start; i < end; i++)
            {
                if (list.Count == 0)
                    oddNode = evenNode = list.AddLast(temp(i));
                else
                    if (list.Count % 2 == 1)
                        oddNode = list.AddBefore(evenNode, temp(i));
                    else
                        evenNode = list.AddAfter(oddNode, temp(i));
            }

            watch.StopAndPrint();
        }

        //another hacky way
        public static void AddMiddle_LinkedList2()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start + 1; i < end; i += 2)
                list.AddLast(temp(i));
            for (int i = end - 2; i >= 0; i -= 2)
                list.AddLast(temp(i));

            watch.StopAndPrint();
        }

        //OP's original more sensible approach, but I tried to filter out
        //the intermediate iteration cost in finding the middle node.
        public static void AddMiddle_LinkedList3()
        {
            var list = new LinkedList<Temp>();
            var watch = Stopwatch.StartNew();

            for (var i = start; i < end; i++)
            {
                if (list.Count == 0)
                    list.AddLast(temp(i));
                else
                {
                    watch.Stop();
                    var curNode = list.First;
                    for (var j = 0; j < list.Count / 2; j++)
                        curNode = curNode.Next;
                    watch.Start();

                    list.AddBefore(curNode, temp(i));
                }
            }

            watch.StopAndPrint();
        }
    }
}

---

You can see the results are in accordance with theoretical performance others have documented here. Quite clear - LinkedList<T> gains big time in case of insertions. I haven't tested for removal from the middle of list, but the result should be the same. Of course List<T> has other areas where it performs way better like O(1) random access.

Starflower

Answer 12

Use LinkedList<> when

1. You don't know how many objects are coming through the flood gate. For example, Token Stream.
2. When you ONLY wanted to delete\insert at the ends.

For everything else, it is better to use List<>.

Alver

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

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. – Alver

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. – Collum

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. – Alver

@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. – Bemoan

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.) – Bemoan

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. – Bemoan

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 – Uprear

Answer 13

I do agree with most of the point made above. And I also agree that List looks like a more obvious choice in most of the cases.

But, I just want to add that there are many instance where LinkedList are far better choice than List for better efficiency.

1. Suppose you are traversing through the elements and you want to perform lot of insertions/deletion; LinkedList does it in linear O(n) time, whereas List does it in quadratic O(n^2) time.
2. Suppose you want to access bigger objects again and again, LinkedList become very more useful.
3. Deque() and queue() are better implemented using LinkedList.
4. Increasing the size of LinkedList is much easier and better once you are dealing with many and bigger objects.

Hope someone would find these comments useful.

Tryout

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. – Transonic

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. – Bemoan

Answer 14

Additionally to other answers, I find LinkedList<T> is better when it comes to large data sets and memory allocation.

While List<T> needs contiguous space, LinkedList<T> does not. This is extremely helpful when you have Data in the size of GBs. Because the single Node entries can fit wherever there is enough space. With a regular List<T> or T[] you need GBs of contiguous space in this case.

Imagine you have 2,000,000 items in a List<T>: When you insert into it and it needs to reallocate (because Capacity is full), you need contiguous space for 4,000,000 items (2.0x grow factor assumed). Actually even more because the new array and old array need to exist at the same time for the reallocation.

With a LinkedList<T> the items are scattered around in memory wherever they fit, and adding an item is nothing more than allocating memory for a single T and the Node's data (+ whatever other things the Runtime needs)

Antemortem

You have to also take into account the intrinsic memory usage of the data structure. Let's take an example, assuming 64bit machine: A List<int> with 2^10 elements will consume 1M * sizeof(int) == 1M * 4 bytes -> a single 4 MB chunk of contiguous memory (the array) plus minimal overhead: 8 bytes for the reference to the array + 4 bytes for the internal count. A LinkedList<int> will allocate 1M LinkedListNode<int> objects! Each has 3 references (original list, prev node, next node) plus the int payload: 3*8 + 4 = 28 bytes per node. Total: 28 * 1M = 28 MB! (vs 4MB for List<>) – Can

Answer 15

In .NET, Lists are represented as Arrays. Therefore using a normal List would be quite faster in comparison to LinkedList.That is why people above see the results they see.

Why should you use the List? I would say it depends. List creates 4 elements if you don't have any specified. The moment you exceed this limit, it copies stuff to a new array, leaving the old one in the hands of the garbage collector. It then doubles the size. In this case, it creates a new array with 8 elements. Imagine having a list with 1 million elements, and you add 1 more. It will essentially create a whole new array with double the size you need. The new array would be with 2Mil capacity however, you only needed 1Mil and 1. Essentially leaving stuff behind in GEN2 for the garbage collector and so on. So it can actually end up being a huge bottleneck. You should be careful about that.

Ralline

Answer 16

I asked a similar question related to performance of the LinkedList collection, and discovered Steven Cleary's C# implement of Deque was a solution. Unlike the Queue collection, Deque allows moving items on/off front and back. It is similar to linked list, but with improved performance.

Nucleo

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.) – Bemoan