Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

When should I use a List vs a LinkedList

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

like image 935
Jonathan Allen Avatar asked Oct 04 '08 08:10

Jonathan Allen


People also ask

Why use a LinkedList over a list?

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.

When would you use a LinkedList vs ArrayList?

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.

Why do we prefer LinkedList?

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.

Is a LinkedList faster than a list?

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.


2 Answers

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.

like image 140
Marc Gravell Avatar answered Oct 14 '22 22:10

Marc Gravell


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.

like image 45
Drew Noakes Avatar answered Oct 14 '22 21:10

Drew Noakes