When should I use a List vs a LinkedList
When is it better to use a List vs a LinkedList?
Solution 1:
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 2:
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>.Countconstant time -
List<T>.Countconstant 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 3:
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.