java - Generic types in an array for a tree with more than one child

Question

I am trying to implement a tree with more than one child and I need to store these children somehow. I decided I could use a LinkedList but I want to try and use an array first.

(Please I do not want to use any Imports.)

class Node<T extends Comparable<? super T>>
{
    Node<T> arrChildren[] = new Node<T>[size];
}

This does not work.

class Node<T extends Comparable<? super T>>
{
    Comparable<Node<T>> arrChildren[] = new Comparable[size];
    T element;
}

This works but I cannot compare the arrChildren[0] with a normal Node<T> and if I make all my Node<T>s Comparable Nodes I cannot reach the elements inside.

This is my first post on Stack overflow I hope too get a good response, I dont mind criticism.

Thanks.

Answer 1

Generics and arrays simply do not mix well in Java. It will be much easier to just use a List<T> implementation like you were considering:

List<Node<T>> arrChildren = new LinkedList<>();

Longer explanation:

Arrays:

• Keep track of their component type at runtime.
• Are covariant (an Integer[] is a Number[] is an Object[]).

Generic types:

• Have their type arguments erased by the compiler such that they aren't available at runtime. Calls to a Node<String> become calls to a Node with appropriate casts to String.
• Aren't covariant (a List<Integer> is not a List<Number>).

The reason new Node<T>[size] isn't allowed is because the array needs to know its component type at runtime, at which point there's no longer a concept of T. Only something like new Node<?>[size] is permissible.

Ignoring the restriction on creating an array of Node<T>, simply having a reference to one isn't safe because the following scenario is possible:

Node<Integer>[] intNodeArray = ...;
Object[] objArray = intNodeArray; //legal because arrays are covariant
objArray[0] = new Node<String>("asfd"); //should fail but doesn't

...

//sometime later
Node<Integer> intNode = intNodeArray[0]; //still doesn't fail because of erasure
Integer i = intNode.getValue(); //only now do we get a runtime exception

Adding a Node<String> to the array should throw a runtime exception, but it doesn't because the array only knows that its component type is Node, not Node<Integer>.

For more information, see Angelika Langer's Generics FAQ: Can I create an array whose component type is a concrete parameterized type?