Why can we add null elements to a java LinkedList?

Question

I'm using java.util implementation of a linked list. I was wondering why it allows us to add null elements, and we can even iterate through them?

Doesn't that defeat the point of a linked list, where we have an element that points to the next element, and the conventional implementation of a linked list would break if we added null elements and tried to iterate over it.

Answer 1

Looking at the Java 7 sources, LinkedList is implemented as a series of nodes.

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;
    }
}

Each node has a reference to the previous node and next node, as well as an item. When you insert a null value into the list, you're inserting a node with a null value for item, but the next and prev pointers are non-null.

Answer 2

Conceptually, the Java collections hold pointers to objects and not the objects themselves. When you see List<String> think List<Pointer-to-String>. You can store multiple copies of the same string-address in a collection. Multiple collections can share the same object pointers, and you can store the null pointer in a collection.

You are thinking of a "conventional" implementation that adds the pointers to the structures themselves. Java separates the details of the "links" from your code by introducing a "header" object that contains pointers to one another AND a pointer to the object you put in. This pointer to your object can be null. Internally, the LinkedList code uses a null pointer in the "header" object to designate the end of the list. This extra pointer is a tad slower since you have to chase it to get to the "payload". But it allows polymorphism (4 paragraphs down).

We usually don't think of the details of a List implementation at all. We code to the "List" interface. The List allows us to insert and remove pointers to objects and access these pointers to objects by index. The pointers can be null.

The LinkedList is quick with inserts/removes but slower with random access (it has to chase the "header" pointers). The ArrayList is quick with random access but slow with inserts/removes (it has to copy memory around). You write your code to the "List" interface and pick an implementation based on your use. And you can change implementation later without changing your code that uses the List interface.

Note in the C++ standard-template library a std::list<std::string> makes a collection of objects themselves (not pointers to objects), and you can't insert nulls. A Java-like collection would be a std::list<std::string *>, which is a collection of pointers that CAN be null.

Collecting "pointers" has the advantage of allowing polymorphism. If I collect objects and not pointers then I can't put a SuperString into a collection of Strings because the code actually copies the structure into its own memory. SuperString is too big for a String slot. But pointers are all the same size; I can put a pointer to a SuperString into a collection of String pointers just fine.