Benchmark Console Constructor foreach if List

`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.

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

Detail 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.

Detail The easiest way to loop through and examine all the contents of a 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`, 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?

Detail 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.

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.

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.

LinkedList