LinkedList
This C# generic type allows fast inserts and removes. It implements a classic linked list. Each object is separately allocated.
In the LinkedList
, certain operations do not require the whole collection to be copied. But in many common cases LinkedList
hinders performance.
This program invokes the LinkedList
constructor. Then it uses the AddLast
and AddFirst
methods to append or prepend elements to the linked list's internal data structure.
foreach
-loop, writing the contents of the LinkedList
object data to the console.LinkedList
is a class
. It is allocated on the managed heap when we invoke the new operator.LinkedList
contains several internal fields which will require some memory.LinkedList
is with the foreach
-loop.using System; using System.Collections.Generic; class Program { static void Main() { // // Create a new linked list object instance. // LinkedList<string> linked = new LinkedList<string>(); // // Use AddLast method to add elements at the end. // Use AddFirst method to add element at the start. // linked.AddLast("cat"); linked.AddLast("dog"); linked.AddLast("man"); linked.AddFirst("first"); // // Loop through the linked list with the foreach-loop. // foreach (var item in linked) { Console.WriteLine(item); } } }first cat dog man
Find
, insertWe pass an element value to Find
. After calling Find
, we use the LinkedListNode
reference variable to perform a relative position insertion into the LinkedList
.
LinkedList
adjusts the reference pointers in its data structure, without copying the entire structure to insert an element.Find()
receives 1 parameter. It returns a reference to a LinkedListNode
instance, which contains pointers to the other elements.using System; using System.Collections.Generic; class Program { static void Main() { // // Create a new linked list. // LinkedList<string> linked = new LinkedList<string>(); // // First add three elements to the linked list. // linked.AddLast("one"); linked.AddLast("two"); linked.AddLast("three"); // // Insert a node before the second node (after the first node) // LinkedListNode<string> node = linked.Find("one"); linked.AddAfter(node, "inserted"); // // Loop through the linked list. // foreach (var value in linked) { Console.WriteLine(value); } } }one inserted two three
A common operation is looping. I was concerned about the performance of LinkedList
in tight loops. Does LinkedList
cause slowdowns in a loop when compared to List
?
List
and a LinkedList
.List
of elements. It has an if
-check that contains unreached code.LinkedList
. The code has the same logical steps that version 1 has.LinkedList
is somewhat slower, but the performance difference was small.using System; using System.Collections.Generic; using System.Diagnostics; class Program { const int _max = 100000; static void Main() { var list = new List<string>(); var link = new LinkedList<string>(); // Add elements. for (int i = 0; i < 1000; i++) { list.Add("OK"); link.AddLast("OK"); } var s1 = Stopwatch.StartNew(); // Version 1: use List. for (int i = 0; i < _max; i++) { foreach (string v in list) { if (v.Length != 2) { throw new Exception(); } } } s1.Stop(); var s2 = Stopwatch.StartNew(); // Version 2: use LinkedList. for (int i = 0; i < _max; i++) { foreach (string v in link) { if (v.Length != 2) { throw new Exception(); } } } s2.Stop(); Console.WriteLine(((double)(s1.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); Console.WriteLine(((double)(s2.Elapsed.TotalMilliseconds * 1000000) / _max).ToString("0.00 ns")); } }6480.76 ns (List loop) 7954.76 ns (LinkedList loop)
LinkedList
often uses more memory than an array or List
. This is because of the memory allocation in .NET, and how objects are allocated.
LinkedList
will require a separate root in the garbage collector.List
, many references are stored in a single block on the managed heap together.LinkedList
of 1000 elements will require more memory than a List
of 1000 elements, assuming the List
is correctly sized.Each time a reference in a LinkedList
is encountered, another level of indirection occurs and performance decreases.
List
is faster than in a LinkedList
—the pointers can be accessed faster.In a List
or array, to insert an element, you must copy the entire array. In a LinkedList
, you can insert or remove an element anywhere in the collection quickly.
LinkedList
—this can be done quickly.LinkedList
is found in the Generic namespace. It is harder to use on many operations, and has worse performance for some uses. This makes it an uncommon requirement.