Introducing self containing objects (Node)

Question

In some programming languages, many data structures use Node<T> (The examples in the question are in Java, but I suppose they are similar in other languages):

public class Node<T> {
    T info;
    Node<T> next;
    ...

I have seen students stare at the board\screen, perplexed, whenever this is introduced. They are confused by this implementation, because it is "Defining something with itself" (like saying "white is the color of things that are white-hot").

They have difficulty understanding how a class can have a property of itself. How could I explain to them why this is valid in programming?

This issue makes it hard for them to understand data structures like List,Queue etc.

Context: they are high-school students learning java, and are familiar with primitive types and a bit of OOP.

Answer 1

A visual demonstration might help. Let's say for the purpose of this in-class demo that the generic T is an object of class Student and you are demonstrating a (singly or doubly) linked list.

• Have students from a line in front of the class, so they are next to each other and facing the rest of the class.
• Explain how each object here is clearly an instance of the Student class. (This should be relatively obvious.)
• Now ask the class to brainstorm how this order could be preserved in memory, i.e. how each student could know what other student is to his/her right and left (if there is such a student).
• Hopefully students will recognize that they will want to know the name of that student (i.e. that Student object) and thus should store the (one or two) adjacent students' names as Node<T> next (and possibly Node<T> prev if doubly linked).
• Model this behavior by having students point to the student on their left with their right arm and the student on their right with their left arm, forming a chain of linked students.
• Emphasize at this point that the order is preserved because each object contains within it as a property the name of its neighboring object(s).

To extend this example in the context of linked lists, you can insert and remove nodes and see if students can figure out how to preserve order without orphaning part of the list.

Answer 2

The sample is not "defining something with itself." Rather it is defining two different kinds of things.

The first line: public class Node<T> { is beginning the definition of a template for things to be made later. That definition will be handled at compile time. The third line: Node<T> next; sets up an object that will be instantiated using some template. Later in the compile process, when the object is created, Java will look in the table for the template called "Node" that can handle some type. Since, by then, the complete template will exist, there's no problem. The key point here is that next is not a template, it is object that will use the Node<T> template when it is created.

If you also define public class Node2<T> extends Node<T>, then at run time, next could refer to the template Node<T>, or the template Node2<T>. Exactly which it is will be determined when the next object is instantiated.

If it hasn't already been covered, that would be an opportune time to cover early and late binding.

Answer 3

Reference

The existing answers seem to be missing the word "reference".

The problem would be real if that Node<T> attribute were (like in a C++ struct) really a "physical" node, right in there. But it is not - it is just a reference pointing to an actual object somewhere else on the heap. Nothing special about that, the fact that it happens to be the same type as defined currently does not hurt at all since all references are just the same if you look at them closely (i.e., a placeholder).

Trees

It may help to introduce the abstract tree data structure, without referencing (sic) any particular programming language.

Real world

Also, real world examples are plentiful. Books regularly contain references to other books. Papers contain references to other papers. People know other people (have a "reference" in their brain) without having little people sitting inside their skull. And so on.