A Brisk Introduction to Linked Lists and Binary Search Trees

by: Ethan McCue

Linked Lists

A linked list is either

In Java we can represent this situation using a "sealed interface."

// A linked list is either empty or not empty.
sealed interface LinkedList<T> 
    permits Empty, NotEmpty {}

record Empty<T>() implements LinkedList<T> {}
record NotEmpty<T>(T first, LinkedList<T> rest) {}

To define operations on a linked list we need to define their operation on the "empty" and "not empty" cases.

The size of an empty list is 0.

int size(LinkedList<?> ll) {
    return switch (ll) {
        case Empty() -> 0;
        ...
    };
}

And the size of a not empty list is 1 + the size of the rest of the list.

int size(LinkedList<?> ll) {
    return switch (ll) {
        case Empty() -> 0;
        case NotEmpty(_, var rest) -> 1 + size(rest);
    };
}

To "map" a function on each element in the list works very similarly.

<T, R> LinkedList<R> map(
        LinkedList<T> ll, 
        Function<? super T, ? extends R> f
) {
    return switch (ll) {
        case Empty() -> new Empty();
        case NotEmpty(var first, var rest) -> new NotEmpty(
                f.apply(first), 
                map(rest, f)
        );
    };
}

As does every operation you might want to define. The recursive structure of the list itself is your guide for implementing operations on it.

Binary Search Trees

A tree is either

In Java we can represent this situation using a "sealed interface."

// A tree is either a leaf or a branch.
sealed interface BST<T> 
    permits Leaf, Branch {}

record Leaf<T>() implements BST<T> {}
record Branch<T>(BST<T> left, T value, BST<T> right) {}

To insert a value into a BST we need to be careful to always properly order elements. If a branch has 5 and we try to insert 2 in the tree, the 2 should go to the "left" because it is less than 5.

<T> BST<T> insert(
        BST<T> bst,
        T value,
        Comparator<? super T> comparator
) {
    return switch (bst) {
        case Leaf() -> new Branch(
                new Leaf(),
                value,
                new Leaf()
        );
        case Branch(var left, var v, var right) -> {
            int comparison = comparator.compare(value, v);
            if (comparison == 0) {
                yield bst;
            }
            else if (comparison > 0) {
                yield new Branch(
                        left,
                        v,
                        insert(right, value, comparator)
                );
            }
            else {
                yield new Branch(
                        insert(left, value, comparator),
                        v,
                        right
                );
            }
        }
    };
}

This is the invariant that allows us to quickly search for values in such a structure. At every branch we can ignore at most half of the tree.

<T> boolean contains(
        BST<T> bst,
        T value,
        Comparator<? super T> comparator
) {
    return switch (bst) {
        case Leaf() -> false;
        case Branch(var left, var v, var right) -> {
            int comparison = comparator.compare(value, v);
            if (comparison == 0) {
                yield true;
            }
            else if (comparison > 0) {
                yield contains(
                        left,
                        value,
                        comparator
                );
            }
            else {
                yield contains(
                        right,
                        value,
                        comparator
                );
            }
        }
    };
}

Now compare this explanation and whatever one you - the reader - were given in school. What are your thoughts?

<- Index