ImmutableLinkedList 1.1.0

dotnet add package ImmutableLinkedList --version 1.1.0
NuGet\Install-Package ImmutableLinkedList -Version 1.1.0
This command is intended to be used within the Package Manager Console in Visual Studio, as it uses the NuGet module's version of Install-Package.
<PackageReference Include="ImmutableLinkedList" Version="1.1.0" />
For projects that support PackageReference, copy this XML node into the project file to reference the package.
paket add ImmutableLinkedList --version 1.1.0
#r "nuget: ImmutableLinkedList, 1.1.0"
#r directive can be used in F# Interactive and Polyglot Notebooks. Copy this into the interactive tool or source code of the script to reference the package.
// Install ImmutableLinkedList as a Cake Addin
#addin nuget:?package=ImmutableLinkedList&version=1.1.0

// Install ImmutableLinkedList as a Cake Tool
#tool nuget:?package=ImmutableLinkedList&version=1.1.0

ImmutableLinkedList

ImmutableLinkedList is a compact .NET implementation of the immutable singly-linked list datastructure which is frequently used in functional-style programming.

ImmutableLinkedList is available for download as a NuGet package. NuGet Status

Release notes

Features

The package exposes two public types: ImmutableLinkedList<T> and the non-generic static helper type ImmutableLinkedList.

Creating a list

Lists can be created by starting from the empty list or by using various factory methods on ImmutableLinkedList:

// With C# >= 12
ImmutableLinkedList<string> emptyList = [];
ImmutableLinkedList<string> nonEmptyList = ["a", "b", "c"];
ImmutableLinkedList<string> listFromEnumerable = [..someEnumerable, "d"];

// Older (and current) versions
var emptyList = ImmutableLinkedList<string>.Empty;
var singletonList = ImmutableLinkedList.Create("a");
var listFromEnumerable1 = ImmutableLinkedList.CreateRange(new[] { "a", "b", "c" });
var listFromEnumerable2 = new[] { "a", "b", "c" }.ToImmutableLinkedList();

A list instance can be further built upon using the Prepend(Range) and Append(Range) methods. Because the list is immutable, these methods return new lists rather than modifying the existing ones. Also because of this, prepending is much faster than appending because it does not require copying the list structure.

Accessing list elements

Lists are IEnumerable, so they can be iterated over. However, the most common access pattern for this datastructure is to consider the Head (first item) and the Tail (List composed of all items but the first). There are a few APIs for this:

var list = ImmutableLinkedList.CreateRange(new[] { "a", "b", "c" });

// C# 7 tuple destructuring
var (head, tail) = list;

// individual properties
var head = list.Head;
var tail = list.Tail;

// the above methods throw when the list is empty. You can check for this first using
// list.Count or use the following
if (list.TryDeconstruct(out var head, out var tail))
{
    // do something with head and tail
}

Implementation Notes

ImmutableLinkedList<T> is a light-weight value type which wraps an underlying list of nodes. This structure has several benefits:

  • The wrapping value type holds the list count, allowing list.Count to run in constant time but avoiding the memory overhead of storing count with every list node
  • Clean representation of the empty list

ImmutableLinkedList<T> implements the IReadOnlyCollection<T> interface as well as the read-only parts of the ICollection<T> interface.

As mentioned previously, because the datastructure is immutable many operations require copying the underlying list nodes in order to build a new list. For all list operations, the implementation is aggressive in avoiding such copies where they are not necessary, thus preserving maximal shared structure between the original list and the new list being constructed. As an example Sort will return the original list unchanged if it is already sorted.

Related to this, ImmutableLinkedList<T> has reference equality semantics (via the IEquatable<T> interface).

Comparison to other implementations

The .NET core libraries offer two types that implement this datastructure:

Microsoft.FSharp.Collections.FSharpList<T> implements the core functional list type for the F# language. This supports many similar operations as ImmutableLinkedList<T> and is the clear choice for F# projects due to it's language integration. However, this type is less compelling for C# projects as it is rather awkward to use from C# because the methods are exposed via the separate ListModule class rather than being implemented on FSharpList<T> itself. Furthermore, using this type from a C# project means taking a dependency on the entire FSharp core DLL, which may be undesirable for some. Finally, FSharpList<T> does not offer constant-time Count and therefore does not implement IReadOnlyCollection<T>.

System.Collections.Immutable.ImmutableStack<T> from the System.Collections.Immutable package offers another implementation of the same basic datastructure (note that System.Collections.Immutable.ImmutableList<T> is a very different datastructure based on a binary tree which has very different performance characteristics). ImmutableStack<T> is a good choice if you want to use this datastructure to represent a stack. However, it is clumsy to use it as a more general collection because it only implements operations which are directly relevant to stacks. Furthermore, ImmutableStack<T> does not offer constant-time Count and therefore does not implement IReadOnlyCollection<T>.

Other operations

In addition to the operations already mentioned, ImmutableLinkedList<T> offers the following: Contains, Remove(value), RemoveAt(index), RemoveAll(predicate), Skip(count), SkipWhile(predicate), SubList(startIndex, count), Reverse, and Sort.

Release notes

  • 1.1.0 Added support for C# 12 collection expressions
  • 1.0.1 Compiled as a readonly struct and with C# 8 nullable reference type annotations
  • 1.0.0 Initial release
Product Compatible and additional computed target framework versions.
.NET net5.0 was computed.  net5.0-windows was computed.  net6.0 was computed.  net6.0-android was computed.  net6.0-ios was computed.  net6.0-maccatalyst was computed.  net6.0-macos was computed.  net6.0-tvos was computed.  net6.0-windows was computed.  net7.0 was computed.  net7.0-android was computed.  net7.0-ios was computed.  net7.0-maccatalyst was computed.  net7.0-macos was computed.  net7.0-tvos was computed.  net7.0-windows was computed.  net8.0 is compatible.  net8.0-android was computed.  net8.0-browser was computed.  net8.0-ios was computed.  net8.0-maccatalyst was computed.  net8.0-macos was computed.  net8.0-tvos was computed.  net8.0-windows was computed. 
.NET Core netcoreapp1.0 was computed.  netcoreapp1.1 was computed.  netcoreapp2.0 was computed.  netcoreapp2.1 was computed.  netcoreapp2.2 was computed.  netcoreapp3.0 was computed.  netcoreapp3.1 was computed. 
.NET Standard netstandard1.1 is compatible.  netstandard1.2 was computed.  netstandard1.3 was computed.  netstandard1.4 was computed.  netstandard1.5 was computed.  netstandard1.6 was computed.  netstandard2.0 was computed.  netstandard2.1 is compatible. 
.NET Framework net45 is compatible.  net451 was computed.  net452 was computed.  net46 was computed.  net461 was computed.  net462 was computed.  net463 was computed.  net47 was computed.  net471 was computed.  net472 was computed.  net48 was computed.  net481 was computed. 
MonoAndroid monoandroid was computed. 
MonoMac monomac was computed. 
MonoTouch monotouch was computed. 
Tizen tizen30 was computed.  tizen40 was computed.  tizen60 was computed. 
Universal Windows Platform uap was computed.  uap10.0 was computed. 
Windows Phone wpa81 was computed. 
Windows Store netcore was computed.  netcore45 was computed.  netcore451 was computed. 
Xamarin.iOS xamarinios was computed. 
Xamarin.Mac xamarinmac was computed. 
Xamarin.TVOS xamarintvos was computed. 
Xamarin.WatchOS xamarinwatchos was computed. 
Compatible target framework(s)
Included target framework(s) (in package)
Learn more about Target Frameworks and .NET Standard.

NuGet packages

This package is not used by any NuGet packages.

GitHub repositories

This package is not used by any popular GitHub repositories.

Version Downloads Last updated
1.1.0 158 1/13/2024
1.0.1 13,788 11/16/2019
1.0.0 1,031 4/3/2018
1.0.0-alpha01 996 3/31/2018