Push adds a value to the front of a linked list and returns the resulting list. In an immutable structure, it leaves the original list unchanged. section 1.2 section 2.2
For an immutable list or stack, push has three useful consequences:
- The new value becomes the first item, while the previous list becomes its tail. section 1.2
- Each push returns a separate list value, so earlier versions remain available. section 2.2 section 1.2.2
- Multiple lists can share the same tail, avoiding needless copying. section 2.2
Building and reversing a list
Starting with an empty list, repeated pushes such as Push(10), Push(20), and Push(30) produce 30, 20, 10. Reversing traverses that list and pushes each item onto a new empty list, yielding 10, 20, 30 while preserving the original. section 1.2.2 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;
}
}
Inspect the compact C# implementation: Push constructs a new node whose tail is the current list, while Empty provides a valid starting object. section 1.2
