48

In a recent project of mine, I defined a class with the following header:

public class Node extends ArrayList<Node> {
    ...
}

However, after discussing with my CS professor, he stated that the class would both be "horrible for memory" and "bad practice". I have not found the first to be particularly true, and the second to be subjective.

My reasoning for this usage is that I had an idea for an object which needed to be defined as something that could have arbitrary depth, where the behavior of an instance could be defined either by a custom implementation or by the behavior of several like objects interacting. This would allow for the abstraction of objects whose physical implementation would be made up of many sub-components interacting.¹

On the other hand, I see how this could be bad practice. The idea of defining something as a list of itself is not simple or physically implementable.

Is there any valid reason why I shouldn't use this in my code, considering my use for it?


¹ If I need to explain this further, I would be glad to; I am just attempting to keep this question concise.

  • 1
  • 1
    @gnat This has more to do with strictly defining a class as a list of itself, rather than containing lists which contain lists. I think it's a variant of a similar thing, but not entirely the same. That question refers to something along the lines of Robert Harvey's answer. – Addison Crump Nov 2 '16 at 21:03
  • 16
    Inherit from something that is parameterized by itself is not unusual, as shows the commonly used CRTP idiom in C++. In the case of the container, the key question is however to justify why you have to use inheritance instead of composition. – Christophe Nov 2 '16 at 21:17
  • 1
    I like the idea. After all, each node in a tree is a (sub) tree. Usually the tree-ness of a node is concealed from a type view (the classical node is not a tree but a single object) and instead expressed in the data view (the single node allows access to branches). Here it's the other way around; we won't see branch data, it's in the type. Ironically, the actual object layout in C++ would likely be very similar (inheritance is implemented very similarly to containing data), which makes me think we are dealing with two ways expressing the same thing. – Peter A. Schneider Nov 3 '16 at 13:17
  • 1
    Maybe I am missing a bit, but do you really need to extend ArrayList<Node>, compared to implement List<Node>? – Matthias Nov 4 '16 at 8:54
108

Frankly, I don't see the need for inheritance here. It doesn't make sense; Node is an ArrayList of Node?

If this is just a recursive data structure, you would simply write something like:

public class Node {
    public String item;
    public List<Node> children;
}

Which does make sense; node has a list of children or descendant nodes.

  • 34
    It's not the same thing. A list of a list of a list ad-infinitum is meaningless unless you are storing something besides a new list in the list. That's what Item is there for, and Item operates independently of the lists. – Robert Harvey Nov 2 '16 at 20:44
  • 6
    Oh, I see now. I had approached Node is an ArrayList of Node as Node contains 0 to many Node objects. Their function is the same, essentially, but instead of being a list of like objects, it has a list of like objects. The original design for the class written was the belief that any Node can be expressed as a set of subNodes, which both implementation do, but this one is certainly less confusing. +1 – Addison Crump Nov 2 '16 at 20:50
  • 11
    I would say that identity between a node and a list tends to arise "naturally" when you write singly-linked lists in C or Lisp or whatever: in certain designs the head node "is" the list, in the sense of being the only thing ever used to represent a list. So I can't completely dispel the feeling that in some contexts perhaps a node "is" (not just "has") a collection of nodes, even though I agree it feels EvilBadWrong in Java. – Steve Jessop Nov 2 '16 at 22:11
  • 12
    @nl-x That the one syntax is shorter doesn't mean it's better. Also, incidentally, it's pretty rare to access items in a tree like that. Usually the structure isn't known at compile time, so you tend to not be traversing such trees by constant values. The depth is also not fixed, so you can't even iterate over all values using that syntax. When you adapt the code to use a traditional tree traversal problem you end up writing Children just once or twice, and it's typically preferable to write it out in such cases for the sake of code clarity. – Servy Nov 3 '16 at 14:29
  • 8
57

The “horrible for memory” argument is entirely wrong, but it is an objectively “bad practice”. When you inherit from a class, you don't just inherit the fields and methods you are interested in. Instead, you inherit everything. Every method that it declares, even if it isn't useful for you. And most importantly, you also inherit all its contracts and guarantees that the class provides.

The acronym SOLID provides some heuristics for good object-oriented design. Here, the Interface Segregation Principle (ISP) and the Liskov Substitution Pricinple (LSP) have something to say.

The ISP tells us to keep our interfaces as small as possible. But by inheriting from ArrayList, you get many, many methods. Is it meaningful to get(), remove(), set() (replace), or add() (insert) a child node at a particular index? Is it sensible to ensureCapacity() of the underlying list? What does it mean to sort() a Node? Are users of your class really supposed to get a subList()? Since you cannot hide methods you don't want, the only solution is to have the ArrayList as a member variable, and forward all methods that you actually want:

private final ArrayList<Node> children = new ArrayList();
public void add(Node child) { children.add(child); }
public Iterator<Node> iterator() { return children.iterator(); }

If you really want all the methods you see in the documentation, we can move on to the LSP. The LSP tells us that we must be able to use the subclass wherever the parent class is expected. If a function takes an ArrayList as parameter and we pass our Node instead, nothing is supposed to change.

Compatibility of subclasses starts with simple things like type signatures. When you override a method, you can't make the parameter types more strict since that might exclude uses that were legal with the parent class. But that is something the compiler checks for us in Java.

But the LSP runs much deeper: We have to maintain compatibility with everything that is promised by the documentation of all parent classes and interfaces. In their answer, Lynn has found one such case where the List interface (which you have inherited via ArrayList) guarantees how the equals() and hashCode() methods are supposed to work. For hashCode() you are even given a particular algorithm that must be implemented exactly. Let's assume you have written this Node:

public class Node extends ArrayList<Node> {
  public final int value;

  public Node(int value, Node... children) {
    this.value = Value;
    for (Node child : children)
      add(child);
  }

  ...

}

This requires that the value cannot contribute to the hashCode() and cannot influence equals(). The List interface – which you promise to honour by inheriting from it – requires new Node(0).equals(new Node(123)) to be true.


Because inheriting from classes makes it too easy to accidentally break a promise that a parent class made, and because it usually exposes more methods than you intended, it is generally suggested that you prefer composition over inheritance. If you must inherit something, it is suggested to only inherit interfaces. If you want to reuse behaviour of a particular class, you can keep it as a separate object in an instance variable, that way all its promises and requirements aren't forced on you.

Sometimes, our natural language suggests an inheritance relationship: A car is a vehicle. A motorcycle is a vehicle. Should I define classes Car and Motorcycle that inherit from a Vehicle class? Object-oriented design is not about mirroring the real world exactly in our code. We cannot easily encode the rich taxonomies of the real world in our source code.

One such example is the employee-boss modelling problem. We have multiple Persons, each with a name and address. An Employee is a Person and has a Boss. A Boss is also a Person. So should I create a Person class that is inherited by Boss and Employee? Now I have a problem: the boss is also an employee and has another superior. So it seems like Boss should extend Employee. But the CompanyOwner is a Boss but isn't an Employee? Any kind of inheritance graph will somehow break down here.

OOP isn't about hierarchies, inheritance, and re-use of existing classes, it is about generalizing behaviour. OOP is about “I have a bunch of objects and want them to do a particular thing – and I don't care how.” That's what interfaces are for. If you implement the Iterable interface for your Node because you want to make it iterable, that's perfectly fine. If you implement the Collection interface because you want to add/remove child nodes etc., then that's fine. But inheriting from another class because it happens to give you all that is not, or at least not unless you have given it careful thought as outlined above.

  • 10
    I've printed your last 4 paragraphs, titled them as About OOP and Inheritance and pined them on the wall at work. Some of my colleagues need to see that as I know they would appreciate the way you put it :) Thank you. – YSC Nov 3 '16 at 16:46
17

Extending a container in as of itself is usually accepted to be bad practice. There's really very little reason to extend a container instead of just having one. Extending a container of yourself just makes it extra strange.

14

Adding to what has been said, there is a somewhat Java-specific reason to avoid this kind of structures.

The contract of the equals method for lists requires a list to be considered equal to another object

if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal.

Source: https://docs.oracle.com/javase/7/docs/api/java/util/List.html#equals(java.lang.Object)

Specifically, this means that having a class designed as a list of itself may make equality comparisons expensive (and hash calculations as well if the lists are mutable), and if the class has some instance fields, well these must be ignored in the equality comparison.

  • 1
    This is an excellent reason to remove this from my code aside of bad practice. :P – Addison Crump Nov 4 '16 at 21:27
3

Regarding memory:

I'd say this is a matter of perfectionism. The default-constructor of ArrayList looks like this:

public ArrayList(int initialCapacity) {
     super();

     if (initialCapacity < 0)
         throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);

     this.elementData = new Object[initialCapacity];
 }

public ArrayList() {
     this(10);
}

Source. This constructor is also used in the Oracle-JDK.

Now consider constructing a singly-linked List with your code. You've just successfully bloated your memory-consumption by the factor 10x (to be precise even marginally higher). For trees this can easily get pretty bad as well without any special requirements on the structure of the tree. Using a LinkedList or other class alternatively should solve this issue.

To be honest, in most cases this is nothing but mere perfectionism, even if we ignore the amount of available memory. A LinkedList would slow down the code a bit as an alternative, so it's a trade-off between performance and memory-consumption either way. Still my personal opinion on this would be to not waste that much memory in way that can be as easily circumvented as this one.

EDIT: clarification regarding the comments (@amon to be precise). This section of the answer does not deal with the issue of inheritance. The comparison of memory usage is made against a singly-linked List and with best memory-usage (in actual implementations the factor might change a bit, but it's still sufficiently large to sum up to quite a bit of wasted memory).

Regarding "Bad practice":

Definitely. This is not the standard-way of implementing a graph for a simple reason: A Graph-Node has child-nodes, not it is as list of child-nodes. Precisely expressing what you mean in code is a major skill. Be it in variable-names or expressing structures like this one. Next point: keeping interfaces minimal: You've made every method of ArrayList available to the user of the class via inheritance. There's no way to alter this without breaking the entire structure of the code. Instead store the List as internal variable and make required methods available via an adapter-method. This way you can easily add and remove functionality from the class without messing everything up.

  • 1
    10x higher compared to what? If I have a default-constructed ArrayList as an instance field (instead of inheriting from it), I'm actually using slightly more memory since I need to store an additional pointer-to-ArrayList in my object. Even if we are comparing apples with oranges and compare inheriting from ArrayList to not using any ArrayList, note that in Java we always deal with pointers to objects, never objects by value as C++ would do. Assuming an new Object[0] uses 4 words total, a new Object[10] would only use 14 words of memory. – amon Nov 4 '16 at 5:55
  • @amon I haven't stated it explicitly, sry for that. Though the context would should be sufficient to see that I'm comparing to a LinkedList. And it's called reference, not pointer btw. And the point with memory wasn't about whether the class is used via inheritance or not, but simply the fact that (nearly) unused ArrayLists are waisting quite a bit of memory. – Paul Nov 4 '16 at 8:17
-2

This seems to look like the semantic of the composite pattern. It is used to model recursive datastructures.

  • 13
    I won't downvote this, but this is why I really hate the GoF book. It's a bleedin' tree! Why did we need to invent the term "composite pattern" to describe a tree? – David Arno Nov 2 '16 at 21:13
  • 3
    @DavidArno I believe it's the whole polymorphic-node aspect that defines it as "composite pattern", the usage of a tree data structure is just part of it. – JAB Nov 2 '16 at 21:16
  • 2
    @RobertHarvey, I disagree (with both your comments to your answer and here). public class Node extends ArrayList<Node> { public string Item; } is the inheritance version of your answer. Yours is simpler to reason, but both achieve the some thing: they define non-binary trees. – David Arno Nov 2 '16 at 21:22
  • 2
    @DavidArno: I never said it wouldn't work, I just said that it's probably not ideal. – Robert Harvey Nov 2 '16 at 21:22
  • 1
    @DavidArno it's not about feelings and taste here, but it's about facts. A tree is made of nodes and every node has potential children. A given node is a leaf node only at a given moment in time. In a composite, a leaf node is leaf by construction, and its nature won't change. – Christophe Nov 2 '16 at 21:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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