A linked list is either empty or a value followed by another linked list, its tail. In an immutable version, Push places a new value in front of an existing list rather than changing it. Each new head can retain the old list as its tail. section 1.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;
}
}
The C# record keeps a value and tail together and gives callers Push and IsEmpty. Its empty list uses null for both fields—a compact choice, but one that still permits invalid combinations of value and tail. section 1.2
The small implementation has several performance surprises:
- Push takes O(1) time and extra memory; building n items takes O(n) of each. section 1.2.1
- Record-generated value equality recursively compares lists. Comparing long lists can overflow the call stack; even IsEmpty does more work than a direct tail check. section 1.2.1
- Repeated string concatenation makes the sample ToString O(n²) in time and extra memory. A StringBuilder would make it O(n). section 1.2.1
public LinkedList<T> Reverse()
{
var result = Empty;
for (var list = this; !list.IsEmpty; list = list.Tail!)
result = result.Push(list.Value!);
return result;
}
Reverse walks the original list and Pushes each value onto an initially empty result. The original is unchanged, and reversal takes O(n) time and extra memory. section 1.2.2
Reversal without mutation
Push 10, 20, 30, 40, and 50 in that order. The resulting list prints as 50 40 30 20 10; its reversal prints as 10 20 30 40 50, while the first list remains available. section 1.2.2
A linked list can also implement an immutable stack. Start with the required operations—Push, Peek, Pop, and IsEmpty—and their behavior on an empty stack, then choose the representation. A dedicated empty object avoids the first list’s ambiguous null-based state; new stack heads can share an unchanged tail. section 2.2
Listing 2.2 Implementing the immutable stack
class ImStack<T> : IImStack<T>
{
private class EmptyStack : IImStack<T> #1
{
public EmptyStack() { }
public IImStack<T> Push(T item) => new ImStack<T>(item, this); #2
public T Peek() => throw new InvalidOperationException();
public IImStack<T> Pop() => throw new InvalidOperationException();
public bool IsEmpty => true;
public IEnumerator<T> GetEnumerator()
{
yield break;
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); #3
}
public static IImStack<T> Empty { get; } = new EmptyStack(); #4
private readonly T item;
private readonly IImStack<T> tail;
private ImStack(T item, IImStack<T> tail) #5
{
this.item = item;
this.tail = tail;
}
public IImStack<T> Push(T item) => new ImStack<T>(item, this);
public T Peek() => item;
public IImStack<T> Pop() => tail;
public bool IsEmpty => false;
public IEnumerator<T> GetEnumerator()
{
for (IImStack<T> s = this; !s.IsEmpty; s = s.Pop())
yield return s.Peek();
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
The stack implementation separates the empty case from a nonempty node. Its empty object permits Push but rejects Peek and Pop; each nonempty node stores an item and a readonly tail. section 2.2
