An immutable linked list is a linked-list structure whose nodes and links cannot change after construction. It is defined recursively: a list is either empty or a value followed by a tail list. section 1.2
Representing the empty list as a valid object avoids null-based method calls. A C# record makes fields read-only by default, while Push constructs a new node that points to the existing list. section 1.2
The design exposes several useful consequences:
- The original list remains unchanged when new lists are constructed. section 1.2.2
- Empty is represented as a list object, although the simple representation can still permit invalid nonempty tails. section 1.2
- Push provides readable construction syntax and supports later immutable stack extensions. section 1.2 section 2.1.7
Reversing a list
Reverse starts with Empty, traverses the input one item at a time, and Pushes each value onto a new list. The input order 50, 40, 30, 20, 10 therefore produces 10, 20, 30, 40, 50. The operation takes O(n) time and O(n) extra memory. section 1.2.2
Listing 1.1 Example immutable linked list
sealed record LinkedList<T>(T? Value, LinkedList<T>? Tail)
{
public static LinkedList<T> Empty = new (default, null);#1
public LinkedList<T> Push(T value) => new (value, this);
public bool IsEmpty => this == Empty; #2
public override string ToString()
{
var s = "";
for (var list = this; !list.IsEmpty; list = list.Tail!)
s += list.Value + " "; #3
return s;
}
}
Inspect the compact C# record implementation, including Empty, Push, IsEmpty, and traversal-based string conversion. section 1.2
