When should I use a List vs a LinkedList
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.
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 timeList<T>.Add(item)
amortized constant time, linear worst case
Prepend
LinkedList<T>.AddFirst(item)
constant timeList<T>.Insert(0, item)
linear time
Insertion
LinkedList<T>.AddBefore(node, item)
constant timeLinkedList<T>.AddAfter(node, item)
constant timeList<T>.Insert(index, item)
linear time
Removal
LinkedList<T>.Remove(item)
linear timeLinkedList<T>.Remove(node)
constant timeList<T>.Remove(item)
linear timeList<T>.RemoveAt(index)
linear time
Count
LinkedList<T>.Count
constant timeList<T>.Count
constant time
Contains
LinkedList<T>.Contains(item)
linear timeList<T>.Contains(item)
linear time
Clear
LinkedList<T>.Clear()
linear timeList<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.