Static methods for operations on inner class

Question

I'm working through Algorithms Fourth Edition (Sedgewick) and am confused by some of the linked-list exercises which seem to be asking to implement static methods for the non-static nodes. For example,

1.3.27 Write a method max() that takes a reference to the first node in a linked list as argument and returns the value of the maximum key in the list. Assume that all keys are positive integers, and return 0 if the list is empty.

or

1.3.31 Implement a nested class DoubleNode for building doubly-linked lists, where each node contains a reference to the item preceding it and the item following it in the list (null if there is no such item). Then implement static methods for the following tasks: insert at the beginning, insert at the end, remove from the beginning, remove from the end, insert before a given node, insert after a given node, and remove a given node.

As I understand (and confirmed by SO answers here and here) this isn't possible. As expected, Eclipse gives errors if I try to write a static method in the superclass:

public class DoublyLinkedList<Item> {

    public static void insertStart(DoubleNode first) {
        // implementation
    }

    private class DoubleNode {
        Item item;
        DoubleNode next;
        DoubleNode previous;

    }
}

(gives the error Cannot make a static reference to the non-static type DoubleNode); or in the inner class:

public class DoublyLinkedList<Item> {

    private class DoubleNode {
        Item item;
        DoubleNode next;
        DoubleNode previous;

        public static void insertStart(DoubleNode first) {
            // implementation
        }
    }
}

(gives the error The method insertStart cannot be declared static; static methods can only be declared in a static or top level type).

I could write the required methods as instance methods for the DoublyLinkedList class, and this would seem most natural to me.

However, I feel that I might be missing out on something important here. The author explicitly states that the methods should be static, and also suggests taking a reference to the first node as an argument (which would be unnecessary for an instance method as the class will have an instance variable for the first node). What am I missing?

Answer 1

You can make nested classes as static. You will lose the constraint of having an enclosing parent class instance, but it will allow you to operate on DoubleNodes from a static method :

// This will compile
public class DoublyLinkedList<Item> {

    public static <T> void insertStart(DoublyLinkedList<T> list, DoubleNode<T> first) {
        // implementation
    }

    private static class DoubleNode<E> {
        E item;
        DoubleNode<E> next;
        DoubleNode<E> previous;

    }
}

Two things to notice here : As you can see, when making the inner class static, you need to provide it its own type parameter (in this case, E). In your code you didn't need to do that, because any DoubleNode instance was guaranteed to have a containing DoublyLinkedList instance, which already determines what Item will be.

Secondly, you need to introduce a type parameter for your static method ("<T>"), so you can enforce the same generic type for both arguments. You could also have done this and get away with it :

public static void insertStart(DoublyLinkedList<?> list, DoubleNode<?> first) {
    ...
}

In case you're wondering, this is also how it is done in the JDK's LinkedList implementation :

// Source : Oracle JDK 1.7.0_67 lib - inside LinkedList class
private static class Node<E> {
     E item;
     Node<E> next;
     Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
       this.item = element;
       this.next = next;
       this.prev = prev;
    }
}

As a sidenote, I do agree that it is more natural to write those methods as instance members ; that's how it's generally done in OOP libraries. I don't have a copy of Sedgewick's book but it looks like he's trying to teach you both nested class manipulation and list implementations at the same time ;)