Nullable Generics - Implementing SequentialSearchST in C#

For learning purposes, I am implementing certain code from Sedgewick & Wayne's Algorithms, Fourth Edition.

Because of language features, a direct translation doesn't seem possible.

For example, I believe the get method in their implementation of SequentialSearchST can return null for both value and reference types because Java boxes/unboxes "value objects" (for lack of a better term) like Integer automatically.

C#, as far as I can tell, does not have an equivalent built in. It also does not appear to be possible to put an all-purpose nullable constraint on a generic type.

At least one other person has tried this, but their implementation does not allow you to store reference types for TValue which prevents you from implementing other Algorithms classes like SeparateChainingHashST.

So, I have decided to throw a runtime error in the static constructor below. Is that about as good as it gets? That is, is there no way to throw a compile time error?

public class SequentialSearchSt
{
    private Node first;

    static SequentialSearchSt()
    {
        if (!default(TValue).Equals(null)) throw new InvalidOperationException("TValue must be a nullable or reference type.");
    }

    private class Node
    {
        public TKey key;
        public TValue val;
        public Node next;

        public Node(TKey key, TValue val, Node next)
        {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }

    public TValue Get(TKey key)
    {
        for (Node x = first; x != null; x = x.next)
        {
            if (key.Equals(x.key))
            {
                return x.val;
            }
        }
        return default(TValue);
    }

    // more code...
}

Consider removing the requirement that default(TValue) is null, and instead of returning null, throw a KeyNotFoundException:


The exception that is thrown when the key specified for accessing an element in a collection does not match any key in the collection.

For convenience, you may also want to provide a bool TryGetValue(TKey key, out TValue value) method.

If possible, making SequentialSearchSt implement IDictionary will make using the class easier for any .NET developer.

StackExchange Code Review Q#77208, answer score: 3