4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Maybe explain the benefit of writing a class once that is able to handle instances of different types of objects. Start with several types that implements a base object or interface. Write a list that needs to call the base properties or methods, e.g. validating before allowing it to be added, or otherwise throw an exception. Maybe the penny will drop. I'm assuming they have some grasp OOP principles. $\endgroup$ – JTC Jun 3 '17 at 16:56
  • $\begingroup$ @JTC The problem isn't with the generics of T, it's the Node field of the Node class which is difficult for the students. $\endgroup$ – ItamarG3 Jun 3 '17 at 17:00
  • 1
    $\begingroup$ I know, i admit I'm not directly answering your question :(. I was giving an example to build them up to understanding. $\endgroup$ – JTC Jun 3 '17 at 17:07
  • 1
    $\begingroup$ @JTC Oh. Well it's more than welcome $\endgroup$ – ItamarG3 Jun 3 '17 at 17:17
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ That will be a very enjoyable lesson for them ;P. Thanks! $\endgroup$ – ItamarG3 Jun 3 '17 at 18:00
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh. The template\object explanation is quite good. So I should add a section about what happens when (compile vs runtime) with this example (after the students understand it)? $\endgroup$ – ItamarG3 Jun 3 '17 at 9:30
  • $\begingroup$ @ItamarGreen Or, divert into that to help them grasp this. They will need that to grasp polymorphism. $\endgroup$ – Gypsy Spellweaver Jun 3 '17 at 9:32
  • $\begingroup$ I see what you mean. Thanks! $\endgroup$ – ItamarG3 Jun 3 '17 at 9:35
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Those real world examples are very handy. They also fit in well with the lesson plan. Thanks! $\endgroup$ – ItamarG3 Jun 14 '17 at 9:56

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.