C# LinkedList

Use 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.Constructor

Next: It uses the enumerator by calling it implicitly in a foreach-loop, writing the contents of the LinkedList object data to the console.

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.

Foreach

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); } } } Output 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); } } } Output 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.

List If

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(); } } Output 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.

Research. There are advantages of linked lists over arrays. With an array, an insertion or removal is slow. We have to copy all following elements. With a linked list, this is not needed.

Quote: The primary advantage of linked lists over arrays is that the links provide us with the capability to rearrange the items efficiently (Algorithms in C++ Third Edition).

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.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# LinkedList

Related Links:

.Net

Java

Related Links