When is it better to use a List(Of T) vs a LinkedList(Of T)?
A:
When you need built-in indexed access, sorting (and after this binary searching), and "ToArray()" method, you should use List.
Michael Damatov
2008-10-04 08:27:29
+16
A:
In most cases, List<T> is more useful. LinkedList<T> will have less cost when adding/removing items in the middle of the list, whre-as 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.
Marc Gravell
2008-10-04 08:28:41
+23
A:
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.
b3
2008-10-04 08:34:23
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.
paulecoyote
2009-07-22 16:26:46
Isn't a contiguous block of memory usually perferred?
Jonathan Allen
2010-02-05 19:52:55
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.
jpierson
2010-03-17 13:37:22
+5
A:
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,
Teera
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
2008-10-04 08:38:58
@Marc, the 'doubling algorithm" only makes it O(logN), but it is still worse than O(1)
Ilya Ryzhenkov
2008-10-04 10:02:10
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.
Marc Gravell
2008-10-04 10:23:48