You want to store a collection of elements together in your C# program and be able to add one to this collection very quickly without ever requiring a copy of all the elements. The LinkedList collection provides a way to insert or remove elements in a list without impacting all the elements at once.
Key point: LinkedList has very fast insertion and removal of elements.
This program demonstrates the usage of the LinkedList type. The program first invokes the LinkedList constructor with a string type parameter. Then, it uses the AddLast and AddFirst instance methods to append or prepend elements to the linked list's internal data structure.
It next uses the enumerator by calling it implicitly in a foreach-loop, writing the contents of the LinkedList object data to the console.
Program that uses LinkedList [C#]
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
Overview. The LinkedList type is a class, which means 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, but no initialization logic is executed in the public parameterless constructor.
Using LinkedList. The program also shows how you can add elements to the beginning and to the end of the LinkedList data structure. The AddLast method on the LinkedList is equivalent to the Add method on the List type, but the internal implementation is different and no internal array buffer is used or needed. The easiest way to loop through and examine all the contents of a LinkedList is with the foreach-loop.
Foreach Loop ExamplesThis example first calls the Find instance method. After calling Find, we use the LinkedListNode reference variable to perform a relative position insertion into the LinkedList. The LinkedList just adjusts the reference pointers in its data structure, without copying the entire structure repeatedly to insert an element.
Program that finds nodes in LinkedList [C#]
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
Explanation. The Find method on the LinkedList type is an instance method that 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. The Find method returns a reference to an instance of the LinkedListNode class, which internally contains pointers to the other elements in the linked list.
Using AddAfter and AddBefore methods. The AddAfter and AddBefore methods 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. Because of the data structure inside the LinkedList class, no extra copying of the entire data set is required.
You can call the Remove method to remove an element with the specified element value. There is also a Remove method 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, which are parameterless. The Remove method contains an early-exit condition when it finds the first node that matches, so it does not remove duplicate nodes.
In terms of memory usage, the LinkedList is often much less efficient than a properly-sized array or List of the elements. This is because of the memory allocation in the .NET Framework and that 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. In other words, a LinkedList of 1000 elements will require more memory than a List of 1000 elements, assuming the List is sized correctly.
Memory Usage Array Examples List Examples
Pointers and indirection. For runtime performance, reducing levels of abstraction is important as it reduces the CPU and memory accesses in the program. Each time a reference in a LinkedList is encountered, another level of indirection occurs and performance decreases. For this reason, accessing elements that are tightly packed in an array or List is much faster than in a LinkedList, because the pointers can be accessed faster.
Insertion performance. 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. Note that you will have to make a separate heap allocation to insert an element onto the LinkedList, but this can be done quickly.
We saw the LinkedList generic collection in the C# language. The LinkedList class is a less-commonly used collection in the namespace, and it is harder to use on many operations and also would have worse performance for some uses. It provides good performance on insertion or deletion.
Collections