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.
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.
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.
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?
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.
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)
Performance. LinkedList often uses more memory than an array or List. This is because of the memory allocation in .NET, and how objects are allocated.
Detail 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, and has worse performance for some uses. This makes it an uncommon requirement.
Dot Net Perls is a collection of tested code examples. Pages are continually updated to stay current, with code correctness a top priority.
Sam Allen is passionate about computer languages. In the past, his work has been recommended by Apple and Microsoft and he has studied computers at a selective university in the United States.
This page was last updated on Jan 25, 2022 (edit).
