Menu
When is it better to use a List vs a LinkedList?
935
Linked lists have most of their benefit when it comes to the insertion and deletion of nodes in the list. Unlike the dynamic array, insertion and deletion at any part of the list takes constant time. Linked lists hold two main pieces of information (the value and pointer) per node.
ArrayList provides constant time for search operation, so it is better to use ArrayList if searching is more frequent operation than add and remove operation. The LinkedList provides constant time for add and remove operations. So it is better to use LinkedList for manipulation.
In a Linked List, insertion and deletion operations are quite easy, as there is no need to shift every element after insertion or deletion. Only the address present in the pointers needs to be updated. While in an array, we have to shift elements.
It depends on what you're trying to accomplish. If you want to search or access a specific element, arrays are faster, but if you want to insert or delete an element, a linked list is faster.
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.
140
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:
LinkedList<T>.AddLast(item) constant time List<T>.Add(item) amortized constant time, linear worst case LinkedList<T>.AddFirst(item) constant time List<T>.Insert(0, item) linear time LinkedList<T>.AddBefore(node, item) constant time LinkedList<T>.AddAfter(node, item) constant time List<T>.Insert(index, item) linear time LinkedList<T>.Remove(item) linear time LinkedList<T>.Remove(node) constant time List<T>.Remove(item) linear time List<T>.RemoveAt(index) linear time LinkedList<T>.Count constant time List<T>.Count constant time LinkedList<T>.Contains(item) linear time List<T>.Contains(item) linear time 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.
45
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
