C# LinkedListUse the LinkedList type in example programs. LinkedList inserts and removes elements fast.
LinkedList. This 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.
Add. 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.
Next It uses the enumerator by calling it implicitly in a foreach-loop, writing the contents of the LinkedList object data to the console.
Class LinkedList is a class. It is allocated on the managed heap when we invoke the new operator.
Note The LinkedList contains several internal fields which will require some memory.
Foreach The easiest way to loop through and examine all the contents of a LinkedList is with the foreach-loop.
C# program that uses LinkedList
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, insert. We pass an element value to Find. After calling Find, we use the LinkedListNode reference variable to perform a relative position insertion into the LinkedList.
Note LinkedList adjusts the reference pointers in its data structure, without copying the entire structure to insert an element.
Info Find() receives 1 parameter. It returns a reference to a LinkedListNode instance, which contains pointers to the other elements.
C# program that finds nodes in LinkedList
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
Benchmark, loop. 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?
Program To investigate, I created a program that adds 1000 elements to both a List and a LinkedList.
Version 1 This version of the code loops over the List of elements. It has an if-check that contains unreached code.
Version 2 Here we loop over the LinkedList. The code has the same logical steps that version 1 has.
Result The LinkedList is somewhat slower, but the performance difference was small.
C# program that loops over LinkedList
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")); Console.Read(); } }
6480.76 ns (List loop) 7954.76 ns (LinkedList loop)
Performance. LinkedList often uses more memory than an array or List. This is because of the memory allocation in the .NET Framework, and how objects are allocated.
Nodes Each node in the LinkedList will require a separate root in the garbage collector.
However In an array or List, many references are stored in a single block on the managed heap together.
Note A LinkedList of 1000 elements will require more memory than a List of 1000 elements, assuming the List is correctly sized.
Memory locality. Each time a reference in a LinkedList is encountered, another level of indirection occurs and performance decreases.
Thus Accessing elements tightly packed in an array or List is faster than in a LinkedList—the pointers can be accessed faster.
Performance gain. 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.
But You will have to make a separate heap allocation to insert an element onto the LinkedList—this can be done quickly.
Summary. LinkedList is found in the Generic namespace. It is harder to use on many operations. It has worse performance for some uses. This makes it an uncommon requirement.
© 2007-2021 sam allen. see site info on the changelog