C# LinkedList Programs

LinkedList allows fast inserts and removes.

It implements a linked list. Each object is separately allocated. Certain operations do not require the whole collection to be copied. In many common cases LinkedList hinders performance.

Add. This program uses the LinkedList type. It first invokes the LinkedList constructor with a string parameter. 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.WriteLine

Based on:

.NET 4.5

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

The LinkedList type is a class. It is allocated on the managed heap when you invoke the new operator and then call the LinkedList instance constructor. The LinkedList contains several internal fields which will require some memory.

Note: No initialization logic is executed in the public parameterless constructor.

Also, we add elements to the beginning and to the end of the LinkedList. The AddLast method on the LinkedList is equivalent to the Add method on the List type, but the implementation is different. No internal array is used or needed.

Tip: The easiest way to loop through and examine all the contents of a LinkedList is with the foreach-loop.

Foreach

Find, insert. This example first calls the Find instance method. 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.

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

The Find method on the LinkedList type receives one parameter. For a LinkedList with the string type parameter, this method receives a string parameter. For a LinkedList with other types, an instance of those types is required.

Also: The Find method returns a reference to an instance of the LinkedListNode class, which contains pointers to the other elements.

AddAfter and AddBefore on the LinkedList class provide a way to insert a node into the linked list in a relative way. To use these methods, you must first locate with the Find method another node in the list.

Then: You provide that node as the first parameter, and the new value to insert in the relative position as the second parameter.

Note: Because of the data structure inside the LinkedList class, no extra copying of the entire data set is required.

Remove. You can call Remove to remove an element with the specified element value. There is also an overload that accepts a reference parameter of type LinkedListNode. You can first call Find to locate the node, and then remove it with Remove.

Also, you can remove the first or last nodes on the LinkedList with the RemoveFirst and RemoveLast methods. Remove contains an early-exit condition when it finds the first node that matches, so it does not remove duplicate nodes.

Performance. In terms of memory usage, the LinkedList is often less efficient than a properly-sized array or List of the elements. This is because of the memory allocation in the .NET Framework, and how objects are allocated.

Each node in the LinkedList will require a separate root in the garbage collector. In an array or List, many references are stored in a single block on the managed heap together, reducing the work required for a garbage collection.

Note: A LinkedList of 1000 elements will require more memory than a List of 1000 elements, assuming the List is correctly sized.

MemoryArraysList

For runtime performance, reducing levels of abstraction is important—it reduces the CPU and memory accesses. 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.

The key performance gain with the LinkedList type is the time required for inserting or removing elements in the collection. In a List or array, to insert an element, you must copy the entire element array each time.

In a LinkedList, you can insert or remove an element anywhere in the collection extremely quickly. If your program must guarantee insertion or removal performance, LinkedList may be useful.

But: You will have to make a separate heap allocation to insert an element onto the LinkedList—this can be done quickly.

Loop performance. With collections such as List or LinkedList, 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?

To investigate, I created a program that adds 1000 elements to both a List and a LinkedList, and then loops over those elements. The LinkedList was somewhat slower, but the performance difference was small.

Tip: It is probably safe to use LinkedList in loops, even in performance sensitive contexts.

Problem that loops over LinkedList: C#

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();
	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();
	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)

Research. In my algorithms textbook, I learned about the 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 (LinkedList) this is not needed.

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++

Summary. The LinkedList class is a less-commonly used collection 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.

Note: LinkedList provides good performance on insertion or deletion. In some program contexts it improves performance.

Related Links