.NET - Is there a singly-linked list in System.Collections.Immutable somewhere?

Question

In functional programming, singly linked lists are extremely popular, because it is easy to reuse sub-lists without allocating any memory or copying values. This means you can add or remove items from one end without any allocation. The F# list is like this.

From what I've read, it sounds like System.Collections.Immutable.ImmutableList<T> is like an immutable version of System.Collections.Generic.List<T>, which is an abstraction over arrays. This is more optimized for random access than a linked list, but requires copying the entire list when adding or removing items.

System.Collections.Generic.LinkedList<T> is a mutable doubly-linked list, which means that either mutation and/or copying is required to add or remove items.

There is no System.Collections.Immutable.ImmutableLinkedList<T> that I've been able to find.

Is there really no immutable singly-linked list in the System.Collections.Immutable package? Is using Microsoft.FSharp.Core.List<T> the best option here?

Answer 1

There is (as of this writing), no great answer to this in the .NET base class library.

The closest thing in System.Collections.Immutable is ImmutableStack<T>, which is implemented as a singly-linked list under the hood. However, the exposed functions are very limited so unless you actually want a stack this is probably a poor choice. You are correct that ImmutableList<T> is a different datastructure with different operations and performance characteristics.

There is FSharpList<T> in the F# standard library, but due to being an F# primitive this is awkward to use from C# (it's possible, it just won't result in clean, idiomatic code). Also requires taking the full F# standard lib as a dependency.

Having faced the same problem in one of my projects, I wrote a NuGet package "ImmutableLinkedList" (github here) for this, so that could be an option as well.